You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
36 lines
1.4 KiB
36 lines
1.4 KiB
# 第五章 作业3
|
|
# 找出所有由1~9组成的9位数，每个数字只能出现一次，且这个9位数由高位到低位前i位能被i整除
|
|
#
|
|
# 1. 使用深度优先搜索（DFS）来查找满足条件的 9 位数。
|
|
#
|
|
# 2. 定义一个 `dfs` 函数，两个参数：
|
|
# - `k`：当前已选择的数字个数，初始值为 0。
|
|
# - `num`：当前已选择的数字组成的整数，初始值为 0。
|
|
#
|
|
# 3. 在 `dfs` 函数中，遍历数字 1 到 9。对于每个数字，检查是否已经使用过（通过 `used` 数组判断）。如果没有使用过，我们尝试将该数字添加到当前的数字组合中。
|
|
#
|
|
# 4. 检查当前数字组合是否满足条件：前 i 位能被 i 整除。如果满足条件，我们继续递归调用 `dfs`，更新 `k` 和 `num`。
|
|
#
|
|
# 5. 当 `k` 等于 9 时，找到了一个满足条件的 9 位数。
|
|
|
|
|
|
def find(k: int, num: int, used: list[bool], resultSet: list[int]):
|
|
if k != 0 and num % k != 0:
|
|
return
|
|
|
|
if k == 9:
|
|
resultSet.append(num)
|
|
return
|
|
|
|
# digit: 1 ~ 9
|
|
for digit in range(1, 10):
|
|
if not used[digit]:
|
|
used[digit] = True
|
|
find(k + 1, num * 10 + digit, used, resultSet)
|
|
# 当前数字撤销使用标记，以便下一个数字的搜索时可用
|
|
used[digit] = False
|
|
|
|
|
|
resultSet = []
|
|
find(0, 0, [False] * 10, resultSet)
|
|
print(resultSet)
|
|
|