是否存在一个由1~9组成的九位数,每个数字只能出现一次,且这个九位数由高位到低位前i位能被i整除
时间: 2023-06-11 14:07:35 浏览: 144
这个问题可以使用回溯算法来解决。首先,我们可以确定第一个数字,因为它只有一种选择。然后,我们可以依次确定后面的数字,每次检查当前数字与前面的数字是否符合条件,如果符合,则继续递归处理下一个数字,否则回溯到上一个数字进行尝试。如果所有数字都已经确定,则得到了一个符合条件的九位数。
下面是 Python 代码实现:
```python
def is_divisible(n, i):
return n % i == 0
def backtrack(nums, i):
if i == 10:
return int(''.join(map(str, nums)))
for j in range(1, 10):
if j not in nums and is_divisible(int(''.join(map(str, nums[-(i-1):]))), i):
nums.append(j)
res = backtrack(nums, i+1)
if res:
return res
nums.pop()
return None
res = backtrack([9], 2)
print(res)
```
在这里,我们从数字 9 开始,因为它是最高位,只能是 9。然后我们递归处理剩余的数字,每次检查当前数字是否符合条件。如果找到了符合条件的九位数,则返回它,否则返回 None。
阅读全文