Python：用于查找前 N 位数字可被 N（从 0-9）整除的数字的代码
Python: Code to find a number where first N digits are divisible by N (from 0-9)
我一直在尝试为程序编写一个递归解决方案，以查找前 N 位数字可被 N 整除的数字。
举个例子：3816547290，3能被1整除，38能被2整除，381能被3整除等等...
我的递归解决方案在 "into" 递归时工作正常，但在堆栈展开时出现问题（即我不知道如何回溯或采取措施退出
ARR = [0]*10
ARR[0] = 1 #dummy entry
def numSeq(pos, num):
if all(ARR):
print num
return True
if (pos>0) and (num%pos) != 0:
return False
for i in xrange(1,10):
if ARR[i] == 1:
continue
new_num = num*10 + i
if new_num%(pos+1) == 0:
ARR[i] = 1
numSeq(pos+1,new_num)
这段代码的问题似乎是它在进入递归时正确地遵循了数字生成...因此它正确地生成了可以被 6 整除的数字 123654 并且跟随前 N 个数字可以被 N 整除，但是在它找不到 7-8 或 9 中除以 7 的任何进一步数字之后，我没有得到下一组 "reset" 全局 ARR 的步骤并从索引 2 开始，即尝试 24xxxx，并最终前往 3816547290
预先感谢您的帮助！
编辑：我忘记提及的一个条件是每个数字必须恰好使用一次（即不允许重复数字）
第二次编辑:
我能够最终应用适当的回溯来解决问题...此代码按原样工作。
ARR = [0]*10
def numDivisibile(num,pos):
if all(ARR):
print num
return True
for i in xrange(0,10):
if ARR[i] == 1:
continue
new_num = num*10+i
#check for valid case
if new_num%(pos+1) == 0:
ARR[i] = 1
if numDivisibile(new_num, pos+1):
return True
#backtrack
ARR[i] = 0
return False
print numDivisibile(0, 0)
在您的函数中，您从不执行 return numSeq(...)，这似乎是导致问题的原因。
如果你想有一个迭代的解决方案，你可以检查以下内容：
def getN(number):
strNum = str(number)
for i in range(1, len(strNum)+1):
if int(strNum[:i]) % i != 0:
return i-1
return i
print getN(3816)
print getN(3817)
print getN(38165)
输出：
4
3
5
要生成所有 10 位整数，其中前 n 位可被 n 整除，对于从 1 到 10 的每个 n（含）：
#!/usr/bin/env python3
def generate_ints_nth_digit_divisible_by_n(n=1, number=0):
number *= 10
if n == 10:
yield number # divisible by 10
else:
for digit in range(not number, 10):
candidate = number + digit
if candidate % n == 0: # divisible by n
yield from generate_ints_nth_digit_divisible_by_n(n + 1, candidate)
print("\n".join(map(str, generate_ints_nth_digit_divisible_by_n())))
输出
1020005640
1020061620
1020068010
...
9876062430
9876069630
9876545640
获取每个数字只出现一次的数字，即找到满足整除条件的数字排列：
def divisibility_predicate(number):
digits = str(number)
for n in range(1, len(digits) + 1):
if int(digits[:n]) % n != 0:
return n - 1
return n
def generate_digits_permutation(n=1, number=0, digits=frozenset(range(1, 10))):
# precondition: number has n-1 digits
assert len(set(str(number))) == (n - 1) or (number == 0 and n == 1)
# and the divisibility condition holds for n-1
assert divisibility_predicate(number) == (n - 1) or (number == 0 and n == 1)
number *= 10
if n == 10:
assert not digits and divisibility_predicate(number) == 10
yield number # divisible by 10
else:
for digit in digits:
candidate = number + digit
if candidate % n == 0: # divisible by n
yield from generate_digits_permutation(n + 1, candidate, digits - {digit})
from string import digits
print([n for n in generate_ints_nth_digit_divisible_by_n()
if set(str(n)) == set(digits)])
print(list(generate_digits_permutation()))
输出
[3816547290]
[3816547290]
我们可以稍微修改一下你的递归函数来尝试不同的可能性。递归的每个线程将拥有自己的 hash 已用数字，而不是拥有已用位置的全局记录 (ARR)：
def numSeq(pos, num, hash):
if pos != 1 and num % (pos - 1) != 0: # number does not pass the test
return
elif pos == 11: # number passed all the tests
print num
elif pos == 5:
numSeq(pos + 1,10 * num + 5,hash) # digit is 5 at position 5
elif pos == 10:
numSeq(pos + 1,10 * num,hash) # digit is 0 at position 10
else:
k = 2 if pos % 2 == 0 else 1 # digit is even at even positions
for i in xrange(k,10,2):
if hash & (1 << i): # digit has already been used, skip it
continue
numSeq(pos + 1,10 * num + i,hash | (1 << i))
numSeq(1,0,0) # 3816547290
我一直在尝试为程序编写一个递归解决方案，以查找前 N 位数字可被 N 整除的数字。
举个例子：3816547290，3能被1整除，38能被2整除，381能被3整除等等...
我的递归解决方案在 "into" 递归时工作正常，但在堆栈展开时出现问题（即我不知道如何回溯或采取措施退出
ARR = [0]*10
ARR[0] = 1 #dummy entry
def numSeq(pos, num):
if all(ARR):
print num
return True
if (pos>0) and (num%pos) != 0:
return False
for i in xrange(1,10):
if ARR[i] == 1:
continue
new_num = num*10 + i
if new_num%(pos+1) == 0:
ARR[i] = 1
numSeq(pos+1,new_num)
这段代码的问题似乎是它在进入递归时正确地遵循了数字生成...因此它正确地生成了可以被 6 整除的数字 123654 并且跟随前 N 个数字可以被 N 整除，但是在它找不到 7-8 或 9 中除以 7 的任何进一步数字之后，我没有得到下一组 "reset" 全局 ARR 的步骤并从索引 2 开始，即尝试 24xxxx，并最终前往 3816547290
预先感谢您的帮助！
编辑：我忘记提及的一个条件是每个数字必须恰好使用一次（即不允许重复数字）
第二次编辑:
我能够最终应用适当的回溯来解决问题...此代码按原样工作。
ARR = [0]*10
def numDivisibile(num,pos):
if all(ARR):
print num
return True
for i in xrange(0,10):
if ARR[i] == 1:
continue
new_num = num*10+i
#check for valid case
if new_num%(pos+1) == 0:
ARR[i] = 1
if numDivisibile(new_num, pos+1):
return True
#backtrack
ARR[i] = 0
return False
print numDivisibile(0, 0)
在您的函数中，您从不执行 return numSeq(...)，这似乎是导致问题的原因。
如果你想有一个迭代的解决方案，你可以检查以下内容：
def getN(number):
strNum = str(number)
for i in range(1, len(strNum)+1):
if int(strNum[:i]) % i != 0:
return i-1
return i
print getN(3816)
print getN(3817)
print getN(38165)
输出：
4
3
5
要生成所有 10 位整数，其中前 n 位可被 n 整除，对于从 1 到 10 的每个 n（含）：
#!/usr/bin/env python3
def generate_ints_nth_digit_divisible_by_n(n=1, number=0):
number *= 10
if n == 10:
yield number # divisible by 10
else:
for digit in range(not number, 10):
candidate = number + digit
if candidate % n == 0: # divisible by n
yield from generate_ints_nth_digit_divisible_by_n(n + 1, candidate)
print("\n".join(map(str, generate_ints_nth_digit_divisible_by_n())))
输出
1020005640
1020061620
1020068010
...
9876062430
9876069630
9876545640
获取每个数字只出现一次的数字，即找到满足整除条件的数字排列：
def divisibility_predicate(number):
digits = str(number)
for n in range(1, len(digits) + 1):
if int(digits[:n]) % n != 0:
return n - 1
return n
def generate_digits_permutation(n=1, number=0, digits=frozenset(range(1, 10))):
# precondition: number has n-1 digits
assert len(set(str(number))) == (n - 1) or (number == 0 and n == 1)
# and the divisibility condition holds for n-1
assert divisibility_predicate(number) == (n - 1) or (number == 0 and n == 1)
number *= 10
if n == 10:
assert not digits and divisibility_predicate(number) == 10
yield number # divisible by 10
else:
for digit in digits:
candidate = number + digit
if candidate % n == 0: # divisible by n
yield from generate_digits_permutation(n + 1, candidate, digits - {digit})
from string import digits
print([n for n in generate_ints_nth_digit_divisible_by_n()
if set(str(n)) == set(digits)])
print(list(generate_digits_permutation()))
输出
[3816547290]
[3816547290]
我们可以稍微修改一下你的递归函数来尝试不同的可能性。递归的每个线程将拥有自己的 hash 已用数字，而不是拥有已用位置的全局记录 (ARR)：
def numSeq(pos, num, hash):
if pos != 1 and num % (pos - 1) != 0: # number does not pass the test
return
elif pos == 11: # number passed all the tests
print num
elif pos == 5:
numSeq(pos + 1,10 * num + 5,hash) # digit is 5 at position 5
elif pos == 10:
numSeq(pos + 1,10 * num,hash) # digit is 0 at position 10
else:
k = 2 if pos % 2 == 0 else 1 # digit is even at even positions
for i in xrange(k,10,2):
if hash & (1 << i): # digit has already been used, skip it
continue
numSeq(pos + 1,10 * num + i,hash | (1 << i))
numSeq(1,0,0) # 3816547290