Python的：code找了好几个，其中前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整除等等...
我的递归解决方案正常工作，同时将进入递归，但有问题时，堆栈解绕（即我不知道具体如何原路返回，或采取在路上走了出来。
ARR = [0] * 10
ARR [0] = 1 #dummy条目
高清numSeq（POS，NUM）：
如果所有（ARR）：
打印张数
返回True
如果（POS＆GT; 0）和（NUM％POS）= 0！
返回False
对我的xrange（1,10）：
如果ARR [我] == 1：
继续
new_num = NUM * 10 + I
如果new_num％（POS + 1）== 0：
ARR [I] = 1
numSeq（POS + 1，new_num）
本code这个问题似乎是它沿用了数生成正确而进入递归......所以正确生成数123654这是整除6，遵循前N个数字是被n整除，但未能找到从7-8或9的7分任何进一步的数字后，我没有得到下一组步骤，复位全球ARR和索引2，即开始尝试24xxxx，并最终获得到3816547290
在此先感谢您的帮助！
修改：我忘了提一个条件是，每个数字必须使用一次（即数字重复是不允许的）
第二次修改
我能够最后应用适当的回溯来解决问题......这code的工作原理是。
ARR = [0] * 10
高清numDivisibile（NUM，POS）：
如果所有（ARR）：
打印张数
返回True
对我的xrange（0,10）：
如果ARR [我] == 1：
继续
new_num = NUM * 10 + I
#check为有效的情况下，
如果new_num％（POS + 1）== 0：
ARR [I] = 1
如果numDivisibile（new_num，POS + 1）：
返回True
#backtrack
ARR [I] = 0
返回False
打印numDivisibile（0，0）
要生成所有10位数的整数，其中第一 N 数字是整除 ñ每个 N 从 1 到 10 包括：
＃！的/ usr / bin中/ env的python3
高清generate_ints_nth_digit_divisible_by_n（n = 1的号= 0）：
数* = 10
如果n == 10：
产量是＃被10整除
其他：
用于数位在范围（未编号，10）：
候选=数字+数字
如果候选人％N == 0：＃被n整除
从generate_ints_nth_digit_divisible_by_n收益率（N + 1，候选人）
打印（\ N。加入（图（STR，generate_ints_nth_digit_divisible_by_n（））））
输出
1020005640
1020061620
1020068010
...
9876062430
9876069630
9876545640
要获得数字，每个数字只出现一次，即找到了满足条件整除的数字的排列：
高清divisibility_ predicate（数字）：
位数= STR（数字）
对于n的范围（1，LEN（位数）+ 1）：
如果INT（数字[：n]）的％N = 0！
返回N - 1
返回否
高清generate_digits_permutation（n = 1的号= 0，位= frozenset（范围（1，10）））：
＃precondition：数有n-1个数字
断言的len（集（STR（数）））==（正 - 1）或（数== 0且n == 1）
＃和可分性条件成立的N-1
断言divisibility_ predicate（号码）==（正 - 1）或（数== 0且n == 1）
数* = 10
如果n == 10：
断言没有数字和divisibility_ predicate（数量）== 10
产量是＃被10整除
其他：
对于数字的位数：
候选=数字+数字
如果候选人％N == 0：＃被n整除
从generate_digits_permutation收益率（N + 1，候选人，数字 - {}位数）
从字符串的进口数字
打印（[N对N的generate_ints_nth_digit_divisible_by_n（）
如果设置（STR（N））==集（数字）]）
打印（列表（generate_digits_permutation（）））
输出
[3816547290]
[3816547290]
I've been trying to write a recursive solution to a program to find a number where first N digits are divisible by N.
As an example: 3816547290, 3 is divisible by 1, 38 is divisible by 2, 381 is divisible by 3 and so on...
My recursive solution works fine while going "into" the recursion, but has issues when the stack unwinds (i.e. I don't specifically know how to backtrack or take steps on the way out
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)
The problem with this code seems to be that it follows the number generation correctly while going into the recursion...so it correctly generates the number 123654 which is divisible by 6 and follows first N digits being divisible by N, but after it fails to find any further digits from 7-8 or 9 that divide 7, i don't get the next set of steps to "reset" the global ARR and begin from index 2, i.e. try 24xxxx,and eventually get to 3816547290
Thanks in Advance for your help!
EDIT: One condition I'd forgotten to mention is that each digit must be used exactly once (i.e. repetition of digits is disallowed)
2nd EDIT:
I was able to finally apply proper backtracking to solve the problem...this code works as is.
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)
To generate all 10 digits integers where the first n digits are divisible by n for each n from 1 to 10 inclusive:
#!/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())))
Output
1020005640
1020061620
1020068010
...
9876062430
9876069630
9876545640
To get numbers where each digit occurs only once i.e., to find the permutations of the digits that satisfy the divisibility condition:
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()))
Output
[3816547290]
[3816547290]
这篇关于Python的：code找了好几个，其中前N个数字是整除N（0-9）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
