news 2026/10/25 16:35:27

（新卷）产品模块算法检验（Java、Js、c\c++、python）

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
（新卷）产品模块算法检验（Java、Js、c\c++、python）

产品模块算法检验


在产品配置中，一个配置产品是由多个产品模块(CM)构成，每个CM有自身的算法，且模块间可能存在算法依赖。例如电脑产品是由主板、CPU日、显卡等CM构成。CPU模块(CM1)算法依赖主板模块(CM2)算法，记作CM2<-CM1,算法引擎会通过算法依赖确保此前后CM执行的顺序。如果存在模块算法循环依赖的场景，那么算法引擎会报警。

输入描述 输入的第一行为模块列表，例如CM2，CM3，CM4; 输入的第二行为依赖情况,例如CM3<-CM2 输出描述 计算出循环依赖的CM数量 示例1： 输入： CM1,CM2,CM3,CM4,CM5,CM6 CM5<-CM3,CM4<-CM5,CM6<-CM4,CM6<-CM1,CM5<-CM6 输出： 3 示例2： 输入： CM1,CM2,CM3,CM4,CM5,CM6 CM5<-CM3,CM3<-CM6,CM6<-CM4,CM3<-CM4,CM4<-CM1 输出： 0

问题分析

该问题需要检测模块间的循环依赖关系，并计算参与循环依赖的模块数量。可以通过构建有向图并检测图中是否存在环来解决。

解决思路

  1. 构建有向图：将每个模块表示为图的节点，依赖关系表示为有向边（如CM3<-CM2表示从CM2指向CM3的边）。
  2. 检测环：使用深度优先搜索（DFS）或拓扑排序来检测图中是否存在环。
  3. 统计环中的节点：如果存在环，统计环中涉及的模块数量。

算法实现

以下是基于拓扑排序的实现方法：

每种语言实现逻辑一致，仅语法和数据结构差异。

  • 计算每个节点的入度（被依赖的次数）。
  • 将入度为0的节点加入队列，进行拓扑排序。
  • 若最终排序的节点数不等于总节点数，则存在环。

  • python实现

  • from collections import defaultdict, deque def count_cyclic_dependencies(modules, dependencies): graph = defaultdict(list) in_degree = defaultdict(int) module_set = set(modules) # 初始化入度为0 for module in module_set: in_degree[module] = 0 # 构建图和入度 for dep in dependencies: dependent, dependee = dep.split('<-') graph[dependee].append(dependent) in_degree[dependent] += 1 # 拓扑排序 queue = deque() for module in module_set: if in_degree[module] == 0: queue.append(module) topo_order = [] while queue: node = queue.popleft() topo_order.append(node) for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) # 检查是否存在环 if len(topo_order) == len(module_set): return 0 else: # 统计环中的节点数 # 通过反向遍历未排序的节点 cyclic_nodes = module_set - set(topo_order) return len(cyclic_nodes) # 示例1 modules = ['CM1', 'CM2', 'CM3', 'CM4', 'CM5', 'CM6'] dependencies = ['CM5<-CM3', 'CM4<-CM5', 'CM6<-CM4', 'CM6<-CM1', 'CM5<-CM6'] print(count_cyclic_dependencies(modules, dependencies)) # 输出3 # 示例2 modules = ['CM1', 'CM2', 'CM3', 'CM4', 'CM5', 'CM6'] dependencies = ['CM5<-CM3', 'CM3<-CM6', 'CM6<-CM4', 'CM3<-CM4', 'CM4<-CM1'] print(count_cyclic_dependencies(modules, dependencies)) # 输出0

    Java实现

    import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String[] modules = scanner.nextLine().split(","); String[] dependencies = scanner.nextLine().split(","); Map<String, List<String>> graph = new HashMap<>(); for (String module : modules) { graph.put(module.trim(), new ArrayList<>()); } for (String dep : dependencies) { String[] parts = dep.trim().split("<-"); String dependent = parts[0].trim(); String dependency = parts[1].trim(); graph.get(dependency).add(dependent); } Set<String> visited = new HashSet<>(); Set<String> recursionStack = new HashSet<>(); List<String> cycleNodes = new ArrayList<>(); for (String module : modules) { if (detectCycle(module, graph, visited, recursionStack, cycleNodes)) { break; } } System.out.println(cycleNodes.size()); } private static boolean detectCycle(String module, Map<String, List<String>> graph, Set<String> visited, Set<String> recursionStack, List<String> cycleNodes) { if (recursionStack.contains(module)) { cycleNodes.add(module); return true; } if (visited.contains(module)) { return false; } visited.add(module); recursionStack.add(module); for (String neighbor : graph.get(module)) { if (detectCycle(neighbor, graph, visited, recursionStack, cycleNodes)) { if (!cycleNodes.contains(module)) { cycleNodes.add(module); } return true; } } recursionStack.remove(module); return false; } }

    C++实现

    #include <iostream> #include <vector> #include <unordered_map> #include <unordered_set> #include <sstream> using namespace std; bool detectCycle(const string& module, unordered_map<string, vector<string>>& graph, unordered_set<string>& visited, unordered_set<string>& recursionStack, vector<string>& cycleNodes) { if (recursionStack.count(module)) { cycleNodes.push_back(module); return true; } if (visited.count(module)) { return false; } visited.insert(module); recursionStack.insert(module); for (const string& neighbor : graph[module]) { if (detectCycle(neighbor, graph, visited, recursionStack, cycleNodes)) { if (find(cycleNodes.begin(), cycleNodes.end(), module) == cycleNodes.end()) { cycleNodes.push_back(module); } return true; } } recursionStack.erase(module); return false; } int main() { string modulesStr, depsStr; getline(cin, modulesStr); getline(cin, depsStr); vector<string> modules; istringstream iss(modulesStr); string module; while (getline(iss, module, ',')) { modules.push_back(module.substr(0, module.find_last_not_of(" \t") + 1)); } unordered_map<string, vector<string>> graph; for (const string& m : modules) { graph[m] = vector<string>(); } istringstream depsIss(depsStr); string dep; while (getline(depsIss, dep, ',')) { size_t pos = dep.find("<-"); string dependent = dep.substr(0, pos); string dependency = dep.substr(pos + 2); dependent = dependent.substr(dependent.find_first_not_of(" \t")); dependency = dependency.substr(dependency.find_first_not_of(" \t")); graph[dependency].push_back(dependent); } unordered_set<string> visited; unordered_set<string> recursionStack; vector<string> cycleNodes; for (const string& m : modules) { if (detectCycle(m, graph, visited, recursionStack, cycleNodes)) { break; } } cout << cycleNodes.size() << endl; return 0; }

    C实现

    #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #define MAX_MODULES 100 typedef struct { char name[10]; int edgeCount; char edges[MAX_MODULES][10]; } Module; Module graph[MAX_MODULES]; int moduleCount = 0; int findModuleIndex(const char* name) { for (int i = 0; i < moduleCount; i++) { if (strcmp(graph[i].name, name) == 0) { return i; } } return -1; } bool detectCycle(int moduleIdx, bool visited[], bool recursionStack[], int* cycleSize) { if (recursionStack[moduleIdx]) { (*cycleSize)++; return true; } if (visited[moduleIdx]) { return false; } visited[moduleIdx] = true; recursionStack[moduleIdx] = true; for (int i = 0; i < graph[moduleIdx].edgeCount; i++) { int neighborIdx = findModuleIndex(graph[moduleIdx].edges[i]); if (detectCycle(neighborIdx, visited, recursionStack, cycleSize)) { if (*cycleSize > 0) { (*cycleSize)++; return true; } } } recursionStack[moduleIdx] = false; return false; } int main() { char modulesStr[1000]; fgets(modulesStr, sizeof(modulesStr), stdin); modulesStr[strcspn(modulesStr, "\n")] = '\0'; char* token = strtok(modulesStr, ","); while (token != NULL) { strcpy(graph[moduleCount].name, token); graph[moduleCount].edgeCount = 0; moduleCount++; token = strtok(NULL, ","); } char depsStr[1000]; fgets(depsStr, sizeof(depsStr), stdin); depsStr[strcspn(depsStr, "\n")] = '\0'; token = strtok(depsStr, ","); while (token != NULL) { char* arrow = strstr(token, "<-"); if (arrow != NULL) { char dependent[10], dependency[10]; strncpy(dependent, token, arrow - token); dependent[arrow - token] = '\0'; strcpy(dependency, arrow + 2); int depIdx = findModuleIndex(dependency); strcpy(graph[depIdx].edges[graph[depIdx].edgeCount], dependent); graph[depIdx].edgeCount++; } token = strtok(NULL, ","); } bool visited[MAX_MODULES] = {false}; bool recursionStack[MAX_MODULES] = {false}; int cycleSize = 0; for (int i = 0; i < moduleCount; i++) { if (detectCycle(i, visited, recursionStack, &cycleSize)) { break; } } printf("%d\n", cycleSize > 0 ? cycleSize - 1 : 0); return 0; }

    JavaScript实现

    const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let modules = []; let dependencies = []; rl.on('line', (line) => { if (modules.length === 0) { modules = line.trim().split(',').map(m => m.trim()); } else { dependencies = line.trim().split(',').map(d => d.trim()); solve(); rl.close(); } }); function solve() { const graph = {}; modules.forEach(m => { graph[m] = []; }); dependencies.forEach(dep => { const [dependent, dependency] = dep.split('<-').map(s => s.trim()); graph[dependency].push(dependent); }); const visited = new Set(); const recursionStack = new Set(); let cycleNodes = []; function detectCycle(module) { if (recursionStack.has(module)) { cycleNodes.push(module); return true; } if (visited.has(module)) { return false; } visited.add(module); recursionStack.add(module); for (const neighbor of graph[module]) { if (detectCycle(neighbor)) { if (!cycleNodes.includes(module)) { cycleNodes.push(module); } return true; } } recursionStack.delete(module); return false; } for (const module of modules) { if (detectCycle(module)) { break; } } console.log(cycleNodes.length); }

    代码说明

  • 输入处理：解析模块列表和依赖关系，构建有向图。
  • 环检测：通过DFS遍历图，利用递归栈判断是否存在环。
  • 结果输出：统计环中模块数量并输出。若不存在环，输出0。
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/10/25 10:05:20

Linux内核实时调度：从基础到实战的终极指南

Linux内核实时调度&#xff1a;从基础到实战的终极指南 【免费下载链接】linux-insides-zh Linux 内核揭秘 项目地址: https://gitcode.com/gh_mirrors/li/linux-insides-zh 在当今的嵌入式系统和工业自动化领域&#xff0c;实时性已成为系统设计的核心考量。你是否曾面…

作者头像 李华
网站建设 2026/10/25 11:47:00

大数据领域数据治理的核心要点与实践策略

大数据领域数据治理的核心要点与实践策略 1. 引入与连接 1.1 引人入胜的开场 在当今数字化时代&#xff0c;数据就如同石油一般&#xff0c;是企业和社会发展的重要资源。想象一下&#xff0c;一家大型电商企业&#xff0c;每天都能收集到海量的数据&#xff0c;包括用户的浏览…

作者头像 李华
网站建设 2026/10/25 7:03:38

2026毕设ssm+vue基于渐进式网页应用的大众社交软件论文+程序

本系统&#xff08;程序源码&#xff09;带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容一、选题背景 关于“动漫内容聚合与社区化传播”问题的研究&#xff0c;现有研究主要以“短视频平台推荐算法”“泛二次元社区运营”或“弹…

作者头像 李华
网站建设 2026/10/25 11:08:14

MechJeb2终极指南：KSP太空飞行自动化解决方案

MechJeb2终极指南&#xff1a;KSP太空飞行自动化解决方案 【免费下载链接】MechJeb2 MechJeb2 - KSP mod 项目地址: https://gitcode.com/gh_mirrors/me/MechJeb2 MechJeb2是Kerbal Space Program游戏中备受推崇的自动驾驶模组&#xff0c;它为玩家提供了完整的飞行自动…

作者头像 李华
网站建设 2026/10/25 10:44:51

终极指南：AI框架统一工具Ivy如何重塑机器学习开发

Ivy统一AI框架正在彻底改变机器学习开发者的工作方式&#xff0c;让代码在不同框架间实现无缝流转。这个革命性的工具解决了长期困扰AI开发者的框架碎片化问题&#xff0c;真正实现了"一次编码&#xff0c;处处运行"的开发理念。 【免费下载链接】ivy The Unified AI…

作者头像 李华
网站建设 2026/10/25 9:09:28

2026毕设ssm+vue基于兼职信息系统设计与实现论文+程序

本系统&#xff08;程序源码&#xff09;带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容一、选题背景关于动漫内容管理与展示系统的研究&#xff0c;现有研究主要以传统的内容管理系统&#xff08;CMS&#xff09;为主&#xff0…

作者头像 李华