素材網(wǎng)站哪個好,柯林建站程序,網(wǎng)站外鏈建設(shè)可以提升網(wǎng)站權(quán)重對還是錯,仿it資訊類網(wǎng)站源碼產(chǎn)品模塊算法檢驗 在產(chǎn)品配置中#xff0c;一個配置產(chǎn)品是由多個產(chǎn)品模塊(CM)構(gòu)成#xff0c;每個CM有自身的算法#xff0c;且模塊間可能存在算法依賴。例如電腦產(chǎn)品是由主板、CPU日、顯卡等CM構(gòu)成。CPU模塊(CM1)算法依賴主板模塊(CM2)算法#xff0c;記作CM2-CM1,算法…產(chǎn)品模塊算法檢驗在產(chǎn)品配置中一個配置產(chǎn)品是由多個產(chǎn)品模塊(CM)構(gòu)成每個CM有自身的算法且模塊間可能存在算法依賴。例如電腦產(chǎn)品是由主板、CPU日、顯卡等CM構(gòu)成。CPU模塊(CM1)算法依賴主板模塊(CM2)算法記作CM2-CM1,算法引擎會通過算法依賴確保此前后CM執(zhí)行的順序。如果存在模塊算法循環(huán)依賴的場景那么算法引擎會報警。輸入描述 輸入的第一行為模塊列表例如CM2CM3CM4; 輸入的第二行為依賴情況,例如CM3-CM2 輸出描述 計算出循環(huán)依賴的CM數(shù)量 示例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問題分析該問題需要檢測模塊間的循環(huán)依賴關(guān)系并計算參與循環(huán)依賴的模塊數(shù)量?？梢酝ㄟ^構(gòu)建有向圖并檢測圖中是否存在環(huán)來解決。解決思路構(gòu)建有向圖將每個模塊表示為圖的節(jié)點依賴關(guān)系表示為有向邊如CM3-CM2表示從CM2指向CM3的邊。檢測環(huán)使用深度優(yōu)先搜索DFS或拓?fù)渑判騺頇z測圖中是否存在環(huán)。統(tǒng)計環(huán)中的節(jié)點如果存在環(huán)統(tǒng)計環(huán)中涉及的模塊數(shù)量。算法實現(xiàn)以下是基于拓?fù)渑判虻膶崿F(xiàn)方法每種語言實現(xiàn)邏輯一致僅語法和數(shù)據(jù)結(jié)構(gòu)差異。計算每個節(jié)點的入度被依賴的次數(shù)。將入度為0的節(jié)點加入隊列進(jìn)行拓?fù)渑判?。若最終排序的節(jié)點數(shù)不等于總節(jié)點數(shù)則存在環(huán)。python實現(xiàn)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 # 構(gòu)建圖和入度 for dep in dependencies: dependent, dependee dep.split(-) graph[dependee].append(dependent) in_degree[dependent] 1 # 拓?fù)渑判?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) # 檢查是否存在環(huán) if len(topo_order) len(module_set): return 0 else: # 統(tǒng)計環(huán)中的節(jié)點數(shù) # 通過反向遍歷未排序的節(jié)點 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)) # 輸出0Java實現(xiàn)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(,); MapString, ListString 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); } SetString visited new HashSet(); SetString recursionStack new HashSet(); ListString 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, MapString, ListString graph, SetString visited, SetString recursionStack, ListString 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實現(xiàn)#include iostream #include vector #include unordered_map #include unordered_set #include sstream using namespace std; bool detectCycle(const string module, unordered_mapstring, vectorstring graph, unordered_setstring visited, unordered_setstring recursionStack, vectorstring 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); vectorstring modules; istringstream iss(modulesStr); string module; while (getline(iss, module, ,)) { modules.push_back(module.substr(0, module.find_last_not_of( ) 1)); } unordered_mapstring, vectorstring graph; for (const string m : modules) { graph[m] vectorstring(); } 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( )); dependency dependency.substr(dependency.find_first_not_of( )); graph[dependency].push_back(dependent); } unordered_setstring visited; unordered_setstring recursionStack; vectorstring cycleNodes; for (const string m : modules) { if (detectCycle(m, graph, visited, recursionStack, cycleNodes)) { break; } } cout cycleNodes.size() endl; return 0; }C實現(xiàn)#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, )] ; 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, )] ; 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] ; 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 , cycleSize 0 ? cycleSize - 1 : 0); return 0; }JavaScript實現(xiàn)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); }代碼說明輸入處理解析模塊列表和依賴關(guān)系構(gòu)建有向圖。環(huán)檢測通過DFS遍歷圖利用遞歸棧判斷是否存在環(huán)。結(jié)果輸出統(tǒng)計環(huán)中模塊數(shù)量并輸出。若不存在環(huán)輸出0。