【华为OD-E卷-30 AI处理器组合100分（python、java、c++、js、c）】

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为OD-E卷-AI处理器组合100分（python、java、c++、js、c）】

题目

某公司研发了一款高性能AI处理器。每台物理设备具备8颗AI处理器，编号分别为0、1、2、3、4、5、6、7。
编号0-3的处理器处于同一个链路中，编号4-7的处理器处于另外一个链路中，不通链路中的处理器不能通信。如下图所示：
现给定服务器可用的处理器编号数组array，以及任务申请的处理器数量num，找出符合下列亲和性调度原则的芯片组合。
如果不存在符合要求的组合，则返回空列表。
亲和性调度原则：
如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。 如果申请处理器个数为2，则选择同一链路剩余可用的处理器数量2个的为最佳，其次是剩余4个，最后是剩余3个。 如果申请处理器个数为4，则必须选择同一链路剩余可用的处理器数量为4个。 如果申请处理器个数为8，则申请节点所有8个处理器。 提示：
任务申请的处理器数量只能是1、2、4、8。 编号0-3的处理器处于一个链路，编号4-7的处理器处于另外一个链路。 处理器编号唯一，且不存在相同编号处理器。

输入描述

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

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

[0, 1, 4, 5, 6, 7]
1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2

表示当前编号为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]]。

用例

用例一：
输入：
[0, 1, 4, 5, 6, 7]
1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
输出：
[[0], [1]]
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
用例二：
输入：
[0, 1, 4, 5, 6, 7]
4
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
输出：
[[4, 5, 6, 7]]
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

说明

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

python解法

初始化与分组：首先将输入数组 arr 排序，然后将数组中的元素分成两个子列表 link1 和 link2，其中 link1 包含所有小于4的元素，link2 包含所有大于等于4的元素。

调度规则：根据输入的 num 值，决定如何处理这两个子列表：

num = 1：选择长度为 1、2、3 或 4 的组合进行调度。
num = 2：选择长度为 2、3 或 4 的组合进行调度。
num = 4：只调度长度为 4 的子列表。
num = 8：如果 link1 和 link2 都有长度为 4 的元素，将它们合并并进行调度。
深度优先搜索（DFS）：使用递归的 DFS 方法来枚举 link1 和 link2 中所有可能的子集组合，根据 num 的值来决定每次深度遍历的层数。每次递归都会生成不同长度的组合，并最终返回所有可能的调度结果。

class ProcessorScheduler:
    def __init__(self, arr, num):
        # 初始化，arr是输入的数组，num是调度的规则
        self.arr = sorted(arr)  # 排序输入数组
        self.num = num  # 设定调度规则
        self.link1 = []  # 小于4的元素
        self.link2 = []  # 大于等于4的元素
        self.result = []  # 存储调度结果

    def split_links(self):
        # 根据元素大小将arr分成两个子列表
        for e in self.arr:
            if e < 4:
                self.link1.append(e)
            else:
                self.link2.append(e)

    def schedule(self):
        # 根据num值来选择调度方式
        self.split_links()  # 先分组
        len1 = len(self.link1)
        len2 = len(self.link2)

        if self.num == 1:
            self._schedule_one(len1, len2)
        elif self.num == 2:
            self._schedule_two(len1, len2)
        elif self.num == 4:
            self._schedule_four(len1, len2)
        elif self.num == 8:
            self._schedule_eight(len1, len2)
        return self.result

    def _schedule_one(self, len1, len2):
        # 处理num为1的情况，根据长度分别递归调度
        if len1 == 1 or len2 == 1:
            if len1 == 1:
                self._dfs(self.link1, 1)
            if len2 == 1:
                self._dfs(self.link2, 1)
        elif len1 == 3 or len2 == 3:
            if len1 == 3:
                self._dfs(self.link1, 1)
            if len2 == 3:
                self._dfs(self.link2, 1)
        elif len1 == 2 or len2 == 2:
            if len1 == 2:
                self._dfs(self.link1, 1)
            if len2 == 2:
                self._dfs(self.link2, 1)
        elif len1 == 4 or len2 == 4:
            if len1 == 4:
                self._dfs(self.link1, 1)
            if len2 == 4:
                self._dfs(self.link2, 1)

    def _schedule_two(self, len1, len2):
        # 处理num为2的情况，根据长度分别递归调度
        if len1 == 2 or len2 == 2:
            if len1 == 2:
                self._dfs(self.link1, 2)
            if len2 == 2:
                self._dfs(self.link2, 2)
        elif len1 == 4 or len2 == 4:
            if len1 == 4:
                self._dfs(self.link1, 2)
            if len2 == 4:
                self._dfs(self.link2, 2)
        elif len1 == 3 or len2 == 3:
            if len1 == 3:
                self._dfs(self.link1, 2)
            if len2 == 3:
                self._dfs(self.link2, 2)

    def _schedule_four(self, len1, len2):
        # 处理num为4的情况，只调度长度为4的子列表
        if len1 == 4:
            self.result.append(self.link1)
        if len2 == 4:
            self.result.append(self.link2)

    def _schedule_eight(self, len1, len2):
        # 处理num为8的情况，如果link1和link2都有长度为4的元素，合并调度
        if len1 == 4 and len2 == 4:
            self.result.append(self.link1 + self.link2)

    def _dfs(self, arr, level):
        # 通过深度优先搜索枚举所有可能的组合
        path = []
        self._dfs_helper(arr, 0, level, path)

    def _dfs_helper(self, arr, index, level, path):
        # 递归函数，生成长度为level的子集
        if len(path) == level:
            self.result.append(path[:])  # 如果路径长度符合条件，保存该组合
            return
        for i in range(index, len(arr)):
            path.append(arr[i])  # 选择当前元素
            self._dfs_helper(arr, i + 1, level, path)  # 递归选择下一个元素
            path.pop()  # 回溯，移除当前元素

if __name__ == "__main__":
    arr = eval(input())  # 输入数组
    num = int(input())  # 输入调度规则
    scheduler = ProcessorScheduler(arr, num)
    print(scheduler.schedule())  # 输出调度结果

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

java解法

调度级别为 1 或 2：

从 link1 和 link2 中分别生成大小为 num 的所有组合。
调度级别为 4：

如果 link1 或 link2 中有正好 4 个元素，将其加入结果。
调度级别为 8：

如果 link1 和 link2 都有 4 个元素，则将两者合并，并将合并后的结果加入到结果中。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入数组并将其转换为 Integer 数组
        Integer[] arr = Arrays.stream(sc.nextLine().split("[\\[\\]\\,\\s]"))
                .filter(str -> !"".equals(str))  // 去除空字符串
                .map(Integer::parseInt)  // 转换为整数
                .toArray(Integer[]::new);  // 转换为 Integer 数组

        // 读取调度级别 num
        int num = sc.nextInt();
        
        // 调用 findProcessorCombinations 方法计算并打印结果
        System.out.println(findProcessorCombinations(arr, num));
    }

    // 主计算方法：根据调度级别生成符合条件的组合
    public static List<List<Integer>> findProcessorCombinations(Integer[] arr, int num) {
        List<List<Integer>> result = new ArrayList<>();  // 存储最终结果
        List<Integer> link1 = new ArrayList<>();  // 存储小于4的元素
        List<Integer> link2 = new ArrayList<>();  // 存储大于等于4的元素

        // 遍历数组，将元素根据大小分配到 link1 或 link2 中
        for (int p : arr) {
            if (p < 4) {
                link1.add(p);  // 小于4的元素加入 link1
            } else {
                link2.add(p);  // 大于等于4的元素加入 link2
            }
        }

        // 根据调度级别调用不同的生成组合的方法
        if (num == 1 || num == 2) {
            findCombinations(link1, num, result);  // 从 link1 中找大小为 num 的组合
            findCombinations(link2, num, result);  // 从 link2 中找大小为 num 的组合
        } else if (num == 4) {
            // 如果 link1 或 link2 有正好 4 个元素，将其加入结果
            if (link1.size() == 4) result.add(new ArrayList<>(link1));
            if (link2.size() == 4) result.add(new ArrayList<>(link2));
        } else if (num == 8 && link1.size() == 4 && link2.size() == 4) {
            // 如果 link1 和 link2 都有 4 个元素，合并它们
            List<Integer> combined = new ArrayList<>(link1);
            combined.addAll(link2);
            result.add(combined);
        }

        return result;  // 返回最终的组合结果
    }

    // 找到从 link 中选取 num 个元素的所有组合
    private static void findCombinations(List<Integer> link, int num, List<List<Integer>> result) {
        if (link.size() >= num) {
            // 如果 link 中的元素数量大于或等于 num，调用回溯算法生成所有组合
            backtrack(link, new ArrayList<>(), 0, num, result);
        }
    }

    // 回溯算法：生成所有符合条件的组合
    private static void backtrack(List<Integer> link, List<Integer> current, int start, int num, List<List<Integer>> result) {
        if (current.size() == num) {
            // 如果当前组合的大小等于 num，将其加入结果
            result.add(new ArrayList<>(current));
            return;
        }
        // 遍历 link 中的元素，生成组合
        for (int i = start; i < link.size(); i++) {
            current.add(link.get(i));  // 将当前元素加入组合
            backtrack(link, current, i + 1, num, result);  // 递归生成剩余的组合
            current.remove(current.size() - 1);  // 回溯，移除最后一个元素
        }
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

JS解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
题目整理、思路解题不易，如对您有帮助，欢迎点赞/收藏 O(∩_∩)O

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/144502720"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！