当前位置：首页 > news >正文

华为OD机试 - 处理器问题（Python/JS/C/C++ 2024 E卷 200分）

news 2025/1/20 19:23:50

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

某公司研发了一款高性能AI处理器。每台物理设备Q 具备8颗AI处理器，编号分别为0，1，2，3，4，5，6，7。

编号0-3的处理器处于同一个链路内，编号4-7的处理器处于另外一个链路中，不同链路中的处理器不能通信。

如下图所示。现给定服务器Q 可用的处理器编号数组array，以及任意的处理器申请数量num，找出符合下列亲和性调度原则的芯片组合。

如果不存在符合要求的组合，则返回空列表。

亲和性调度原则：

如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。

如果申请处理器个数为2，则选择同一链路剩余可用的处理器数量为2个的为最佳，其次是剩余4个，最后是剩余3个。

如果申请处理器个数为4，则必须选择同一链路剩余可用的处理器数量为4个。

如果申请处理器个数为8，则申请节点所有8个处理器。

提示：

任各申请的处理器数量只能是1，2，4，8。

编号0-3的处理器处于一个链路，编号4-7的处理器处于另外一个链路。

处理器编号唯一，且不存在任何编号相同的处理器。

二、输入描述

输入包含可用的处理器编号数组 arrayQ，以及任务申请的处理器数量 num 两个部分。

第一行为array，第二行为num。例如：

[0, 1, 4, 5, 6, 7]
1

表示当前编号为0，1，4，5，6，7的处理器可用。任务申请1个处理器。

0 <= array.length <= 8
0 <= array[i] <= 7
num in [1, 2, 4, 8]

三、输出描述

输出为组合列表，当 array = [0, 1, 4, 5, 6, 7]，num = 1时，输出为[[0], [1]]

四、测试用例

测试用例1：

1、输入

[0, 1, 4, 5, 6, 7]
1

2、输出

[[0], [1]]

3、说明

根据第一条亲和性调度原则，在剩余两个处理器的链路(0, 1, 2, 3)中选择处理器。由于只有0和1可用，则返回任意一颗处理器即可。

测试用例2：

1、输入

[0, 1, 4, 5, 6, 7]
4

2、输出

[[4, 5, 6, 7]]

3、说明

根据第三条亲和性调度原则，必须选择同一链路剩余可用的处理器数量为4个的环。

五、解题思路

优先级确定：
- 根据申请的处理器数量 num，确定每个链路的优先级。
- 对于不同的 num，有不同的优先级规则：
  - num = 1：优先选择在一个链路中剩余可用处理器数量为 1 的情况，其次是 3，然后是 2，最后是 4。
  - num = 2：优先选择在一个链路中剩余可用处理器数量为 2 的情况，其次是 4，然后是 3。
  - num = 4：必须选择在一个链路中剩余可用处理器数量为 4 的情况。
  - num = 8：必须选择所有 8 个处理器。
组合生成：
- 根据确定的优先级，从优先级最高的链路中生成所有可能的组合。
- 如果在优先级最高的链路中没有足够的处理器，则考虑下一个优先级。
返回结果：
- 如果找到符合要求的组合，则返回这些组合。
- 否则，返回空列表。

六、Python算法源码

# Python版本
import sys
import itertoolsdef parse_array(array_line):# 移除方括号和空格array_line = array_line.strip().replace('[', '').replace(']', '').replace(' ', '')if not array_line:return []# 分割字符串并转换为整数列表return list(map(int, array_line.split(',')))def get_priority(remaining, priorities):# 获取剩余处理器数量的优先级，索引越小优先级越高try:return priorities.index(remaining)except ValueError:return len(priorities)def combine(lst, size):# 生成给定列表中所有可能的指定大小的组合return [sorted(list(c)) for c in itertools.combinations(lst, size)]def find_combinations(link1, link2, num, priorities):result = []best_priority = float('inf')# 检查链路1remaining1 = len(link1) - numif remaining1 >= 0:priority1 = get_priority(remaining1, priorities)if priority1 < best_priority:best_priority = priority1result = []if priority1 == best_priority:result += combine(link1, num)# 检查链路2remaining2 = len(link2) - numif remaining2 >= 0:priority2 = get_priority(remaining2, priorities)if priority2 < best_priority:best_priority = priority2result = []if priority2 == best_priority:result += combine(link2, num)return resultdef main():# 读取输入array_line = sys.stdin.readline()available = parse_array(array_line)num_line = sys.stdin.readline()num = int(num_line.strip())# 分离处理器到两个链路link1 = [proc for proc in available if 0 <= proc <= 3]link2 = [proc for proc in available if 4 <= proc <= 7]result = []# 根据申请数量选择组合if num == 1:result = find_combinations(link1, link2, num, [1,3,2,4])elif num == 2:result = find_combinations(link1, link2, num, [2,4,3])elif num == 4:if len(link1) == 4:result.append(sorted(link1))if len(link2) == 4:result.append(sorted(link2))elif num == 8:if len(available) == 8:result.append(sorted(available))# 打印结果print(result)if __name__ == "__main__":main()

七、JavaScript算法源码

// JavaScript版本
const readline = require('readline');// 创建接口读取输入
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});// 读取所有输入行
let input = [];
rl.on('line', (line) => {input.push(line.trim());if (input.length === 2) {rl.close();}
}).on('close', () => {// 解析输入数组let arrayLine = input[0].replace(/\[|\]|\s/g, '');let available = arrayLine ? arrayLine.split(',').map(Number) : [];// 解析申请数量let num = parseInt(input[1]);// 分离到两个链路let link1 = available.filter(proc => proc >=0 && proc <=3);let link2 = available.filter(proc => proc >=4 && proc <=7);let result = [];// 定义优先级const prioritiesMap = {1: [1,3,2,4],2: [2,4,3]};// 组合生成函数function combine(lst, size) {let res = [];function backtrack(start, path) {if (path.length === size) {res.push([...path].sort((a,b) => a - b));return;}for (let i = start; i < lst.length; i++) {path.push(lst[i]);backtrack(i+1, path);path.pop();}}backtrack(0, []);return res;}// 获取优先级function getPriority(remaining, priorities) {let index = priorities.indexOf(remaining);return index !== -1 ? index : priorities.length;}// 查找组合function findCombinations(link1, link2, num, priorities) {let bestPriority = Infinity;let bestResult = [];// 检查链路1let remaining1 = link1.length - num;if (remaining1 >=0 ) {let priority1 = getPriority(remaining1, priorities);if (priority1 < bestPriority) {bestPriority = priority1;bestResult = [];}if (priority1 === bestPriority) {bestResult = bestResult.concat(combine(link1, num));}}// 检查链路2let remaining2 = link2.length - num;if (remaining2 >=0 ) {let priority2 = getPriority(remaining2, priorities);if (priority2 < bestPriority) {bestPriority = priority2;bestResult = [];}if (priority2 === bestPriority) {bestResult = bestResult.concat(combine(link2, num));}}return bestResult;}// 根据num选择组合if (num ===1) {result = findCombinations(link1, link2, num, prioritiesMap[1]);}else if (num ===2) {result = findCombinations(link1, link2, num, prioritiesMap[2]);}else if (num ===4) {if (link1.length ===4) {result.push([...link1].sort((a,b)=>a-b));}if (link2.length ===4) {result.push([...link2].sort((a,b)=>a-b));}}else if (num ===8) {if (available.length ===8) {let all = [...available].sort((a,b)=>a-b);result.push(all);}}// 打印结果console.log(result);
});

八、C算法源码

// C语言版本
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 最大组合数量
#define MAX_COMB 1000// 组合结构体
typedef struct {int combination[8];int size;
} Combination;// 解析数组字符串
int parse_array(char *array_line, int *available) {int count =0;char *token = strtok(array_line, "[], ");while(token != NULL && count <8){available[count++] = atoi(token);token = strtok(NULL, "[], ");}return count;
}// 生成组合
void combine(int *list, int size, int start, int n, int *current, int index, Combination *combs, int *count) {if(index == n){for(int i=0;i<n;i++) {combs[*count].combination[i] = current[i];}combs[*count].size = n;(*count)++;return;}for(int i=start;i<size;i++) {current[index] = list[i];combine(list, size, i+1, n, current, index+1, combs, count);}
}// 获取优先级
int get_priority(int remaining, int *priorities, int p_size){for(int i=0;i<p_size;i++) {if(priorities[i] == remaining){return i;}}return p_size;
}int main(){char array_line[100];int available[8];int total =0;// 读取第一行fgets(array_line, sizeof(array_line), stdin);total = parse_array(array_line, available);// 读取第二行int num;scanf("%d", &num);// 分离链路int link1[4], link2[4];int l1=0, l2=0;for(int i=0;i<total;i++) {if(available[i]>=0 && available[i]<=3){link1[l1++] = available[i];}else if(available[i]>=4 && available[i]<=7){link2[l2++] = available[i];}}Combination combs1[MAX_COMB];int count1 =0;Combination combs2[MAX_COMB];int count2 =0;Combination final_combs[MAX_COMB];int final_count=0;if(num ==1){int priorities1[] = {1,3,2,4};int p_size1 = sizeof(priorities1)/sizeof(int);// 链路1int remaining1 = l1 - num;if(remaining1 >=0){int priority1 = get_priority(remaining1, priorities1, p_size1);// 链路2int priorities2[] = {1,3,2,4};int priority2 = get_priority(l2 - num, priorities2, p_size1);if(priority1 < priority2){// 处理链路1int current[1];combine(link1, l1, 0, l1, current, 0, combs1, &count1);for(int i=0;i<count1;i++) {final_combs[final_count++] = combs1[i];}}else if(priority2 < priority1){// 处理链路2int current[1];combine(link2, l2, 0, l2, current, 0, combs2, &count2);for(int i=0;i<count2;i++) {final_combs[final_count++] = combs2[i];}}else{// 相同优先级，合并int current[1];combine(link1, l1, 0, l1, current, 0, combs1, &count1);combine(link2, l2, 0, l2, current, 0, combs2, &count2);for(int i=0;i<count1;i++) {final_combs[final_count++] = combs1[i];}for(int i=0;i<count2;i++) {final_combs[final_count++] = combs2[i];}}}}else if(num ==2){int priorities1[] = {2,4,3};int p_size1 = sizeof(priorities1)/sizeof(int);// 链路1int remaining1 = l1 - num;if(remaining1 >=0){int priority1 = get_priority(remaining1, priorities1, p_size1);// 链路2int priorities2[] = {2,4,3};int priority2 = get_priority(l2 - num, priorities2, p_size1);if(priority1 < priority2){// 处理链路1int current[2];combine(link1, l1, 0, l1, current, 0, combs1, &count1);for(int i=0;i<count1;i++) {final_combs[final_count++] = combs1[i];}}else if(priority2 < priority1){// 处理链路2int current[2];combine(link2, l2, 0, l2, current, 0, combs2, &count2);for(int i=0;i<count2;i++) {final_combs[final_count++] = combs2[i];}}else{// 相同优先级，合并int current[2];combine(link1, l1, 0, l1, current, 0, combs1, &count1);combine(link2, l2, 0, l2, current, 0, combs2, &count2);for(int i=0;i<count1;i++) {final_combs[final_count++] = combs1[i];}for(int i=0;i<count2;i++) {final_combs[final_count++] = combs2[i];}}}}else if(num ==4){if(l1 ==4){Combination comb;for(int i=0;i<4;i++) comb.combination[i] = link1[i];comb.size =4;final_combs[final_count++] = comb;}if(l2 ==4){Combination comb;for(int i=0;i<4;i++) comb.combination[i] = link2[i];comb.size =4;final_combs[final_count++] = comb;}}else if(num ==8){if(total ==8){Combination comb;for(int i=0;i<8;i++) comb.combination[i] = available[i];comb.size =8;final_combs[final_count++] = comb;}}// 打印结果printf("[");for(int i=0;i<final_count;i++){printf("[");for(int j=0;j<final_combs[i].size;j++){printf("%d", final_combs[i].combination[j]);if(j != final_combs[i].size -1) printf(", ");}printf("]");if(i != final_count -1) printf(", ");}printf("]\n");return 0;
}

九、C++算法源码

// C++版本
#include <bits/stdc++.h>
using namespace std;// 组合生成函数
vector<vector<int>> combine(const vector<int>& list, int size){vector<vector<int>> combinations;vector<int> current;int n = list.size();// 使用位掩码生成所有组合for(int mask=0; mask<(1<<n); mask++){if(__builtin_popcount(mask) == size){vector<int> comb;for(int i=0;i<n;i++) if(mask & (1<<i)) comb.push_back(list[i]);sort(comb.begin(), comb.end());combinations.push_back(comb);}}return combinations;
}// 获取优先级
int get_priority(int remaining, const vector<int>& priorities){auto it = find(priorities.begin(), priorities.end(), remaining);if(it != priorities.end()) return distance(priorities.begin(), it);return priorities.size();
}// 查找组合
vector<vector<int>> find_combinations(const vector<int>& link1, const vector<int>& link2, int num, const vector<int>& priorities){vector<vector<int>> result;int best_priority = INT32_MAX;// 链路1int remaining1 = link1.size() - num;if(remaining1 >=0 ){int priority1 = get_priority(remaining1, priorities);if(priority1 < best_priority){best_priority = priority1;result.clear();}if(priority1 == best_priority){vector<vector<int>> combs = combine(link1, num);result.insert(result.end(), combs.begin(), combs.end());}}// 链路2int remaining2 = link2.size() - num;if(remaining2 >=0 ){int priority2 = get_priority(remaining2, priorities);if(priority2 < best_priority){best_priority = priority2;result.clear();}if(priority2 == best_priority){vector<vector<int>> combs = combine(link2, num);result.insert(result.end(), combs.begin(), combs.end());}}return result;
}int main(){string array_line;getline(cin, array_line);// 解析数组vector<int> available;array_line.erase(remove(array_line.begin(), array_line.end(), '['), array_line.end());array_line.erase(remove(array_line.begin(), array_line.end(), ']'), array_line.end());array_line.erase(remove(array_line.begin(), array_line.end(), ' '), array_line.end());if(!array_line.empty()){stringstream ss(array_line);string num_str;while(getline(ss, num_str, ',')){available.push_back(stoi(num_str));}}// 读取申请数量int num;cin >> num;// 分离链路vector<int> link1, link2;for(auto proc: available){if(proc >=0 && proc <=3) link1.push_back(proc);else if(proc >=4 && proc <=7) link2.push_back(proc);}vector<vector<int>> result;if(num ==1){vector<int> priorities = {1,3,2,4};result = find_combinations(link1, link2, num, priorities);}else if(num ==2){vector<int> priorities = {2,4,3};result = find_combinations(link1, link2, num, priorities);}else if(num ==4){if(link1.size() ==4){vector<int> comb = link1;sort(comb.begin(), comb.end());result.push_back(comb);}if(link2.size() ==4){vector<int> comb = link2;sort(comb.begin(), comb.end());result.push_back(comb);}}else if(num ==8){if(available.size() ==8){vector<int> comb = available;sort(comb.begin(), comb.end());result.push_back(comb);}}// 打印结果cout << "[";for(int i=0;i<result.size();i++){cout << "[";for(int j=0;j<result[i].size();j++){cout << result[i][j];if(j != result[i].size()-1) cout << ", ";}cout << "]";if(i != result.size()-1) cout << ", ";}cout << "]\n";return 0;
}