页面加载中…
K0000. 圈复杂度计算
中等通过率 18% · 提交 559 · 通过 101
可信DFS回溯图论记忆化搜索
华为可信认证科目一方向改编 · 聚焦「可信 / DFS」 · 难度：中等
请直接输出如下三份代码的。 第1份代码：
def find_paths(maze, x, y, path=None, visited=None):
if path is None:
path = []
if visited is None:
visited = set()
rows, cols = len(maze), len(maze[0])
# 检查是否到达终点
if x == rows - 1 and y == cols - 1:
return [path + [(x, y)]]
# 标记当前点为已访问
visited.add((x, y))
path.append((x, y))
# 定义方向：右、下、左、上
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
paths = []
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and (nx, ny) not in visited and maze[nx][ny] == 0:
paths.extend(find_paths(maze, nx, ny, path[:], visited.copy()))
return paths第2份代码：
def coin_change(coins, amount):
# dp[i] 表示组成金额 i 所需的最少硬币数
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 组成金额 0 不需要任何硬币
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1第3份代码：
def validate_and_process_parentheses(s):
stack = [] # 用于存储索引
matched = [-1] * len(s) # 标记每个位置是否匹配
for i, char in enumerate(s):
if char == '(':
stack.append(i)
elif char == ')' and stack:
match_index = stack.pop()
matched[match_index] = i # 记录匹配的位置
matched[i] = match_index
is_balanced = all(matched[i] != -1 for i in range(len(s)) if s[i] in "()")
# 寻找最长的有效括号子串
max_length = 0
current_length = 0
max_substring = ""
current_substring = []这类题属于华为可信认证科目一方向中「可信 / DFS」方向的高频题型，通常考察对「可信 / DFS」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
提示：带虚线的词点一下有通俗解释。
输入描述
无
输出描述
打印三行整数分别表示它们的圈复杂度，例如：
100
1000
10000
对于这道题目，如果使用python代码打印那就是：
print(100)
print(1000)
print(10000)
时间限制 1000 ms · 内存限制 128 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
基础知识：圈复杂度
圈复杂度（Cyclomatic Complexity） 是一种用来衡量一个程序的复杂度和逻辑结构的指标，最初由托马斯·麦凯布（Thomas McCabe）在1976年提出。它通过计算程序的独立路径数量，反映代码中决策结构的复杂程度，从而帮助开发者了解代码的可读性、可维护性和测试难度。也可理解为覆盖所有的可能情况最少使用的测试用例数。
圈复杂度的统计主体是一个函数。
点边计算法
圈复杂度的计算基于程序的控制流图（Control Flow Graph），其中：
- 节点表示程序中的基本代码块（没有分支或决策点的连续代码段）。
- 边表示控制流的路径（从一个代码块到另一个代码块的转移）。
圈复杂度的公式为：
其中：
M是圈复杂度。E是控制流图中的边数。N是控制流图中的节点数。
所有节点都通过边链接。
节点判定法
圈复杂度的计算有一种更为直观的方法，因为它反映的是代码中“判定条件”的数量。本质上，圈复杂度等于判定节点的数量加 1，也即控制流图的区域数，其计算公式为：
其中，D 表示判定节点的数量。以下是一些常见的判定节点示例：
if语句while语句for语句case语句catch语句and和or布尔操作?:三元运算符（在Python中则是expr if bool_expr else expr）
对于多分支结构，如 case 语句或 if-elif-else 结构，需要特别注意统计所有实际的判定节点。例如，每个 elif 语句或 case 分支都应被视为一个判定节点。
以下是一个 Python 函数示例，其圈复杂度的计算过程如下：
判定节点包括：
for num in numbersif num > 0elif num < 0if num % 2 == 0if max_even is Noneor num > max_evenif max_even is not None
因此该代码的判定节点的数量为 7 个，其圈复杂度为 8。
练习：下列这份代码的圈复杂度是？
典型值及意义
以下是详细描述的表格，包含圈复杂度范围、代码状况、可测性、维护成本及额外的内容说明。
| 圈复杂度范围 | 代码状况 | 可测性 | 维护成本 | 说明 |
|---|---|---|---|---|
| 1-10 | 良好 | 高 | 低 | 代码简单清晰 |
| 11-20 | 中等 | 中 | 中 | 需要关注 |
| 21-30 | 复杂 | 低 | 高 | 建议重构 |
| 30+ | 非常复杂 | 极低 | 极高 | 必须重构 |
在部分场景中，圈复杂度在 15 也是可以接受的。
应用场景
- 代码质量评估：高圈复杂度的代码往往更难理解和维护。
- 测试覆盖率评估：圈复杂度直接反映了程序中的独立路径数量，因此也是最低测试用例数的下限。
- 重构建议：通过降低圈复杂度，可以提升代码的可读性和可维护性。
降低圈复杂度的做法
提炼函数
提炼函数是一种常见的代码重构技巧。通过将程序的一部分逻辑提取到单独的函数中，可以更清晰地表达代码意图，尽管这并不会降低程序整体的复杂度。然而，这种方式将复杂性转移到了更细粒度的模块中，便于管理和维护。提炼函数的主要目标是减少在开发过程中需要同时关注的细节数量，从而提高代码的可读性和易维护性。
重构前：
重构后：
替换算法
通过替换算法，将分支逻辑（如一系列 if-else 或 switch-case）替换为更简洁、高效的数据结构或算法。此技巧的优势在于简化代码逻辑，提高可读性和可维护性，特别是当逻辑分支较多时。
重构前：
重构后：
使用更高层次的抽象
通过使用高层次抽象工具处理可能的 null 值或异常情况，可以减少显式的条件检查，简化代码，提高可读性和流畅性。
重构前：
重构后：
逻辑优化
逻辑优化是一种通过重新整理布尔表达式或条件判断逻辑以提高代码简洁性和可读性的方法。通过化简逻辑表达式，可以减少冗余判断，提升执行效率，同时让代码更加直观。
重构前：
重构后：
合并条件
合并条件是一种通过将多个相似的条件检查逻辑提取到一个独立的函数或方法中，以减少重复代码并提升代码可读性和可维护性的方法。该技巧适用于逻辑上有共性或相似性的判断语句，可以通过函数抽象统一处理，避免代码重复和分散。
重构前：
重构后：
输出一份代码的圈复杂度
以Python为例，我们可以使用 radon 库，它是一个简单的工具，专门用于计算 Python 函数的圈复杂度。
首先，确保安装了 radon：
以下是完整代码，用于计算给定函数的圈复杂度：
打卡题目：https://www.algomooc.com/problem/K0000
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
