python每个数都可由集合中的某两个数相加而得
问题表述
有一个自然数集合,其中最小的数是1,最大的数是100。这个集合中的数除了1之外,每个数都可由集合中的某两个数相加而得(这两个数可以相同)。利用回溯法编写程序,求符合上述条件的、元素个数为10的所有集合。
思路
这个集合中最小数1,最大数为100,为了便于计算,设这个集合是有序的且有小到大排列,max
表示当前满足要求的最大数,n
表示还剩需要寻找元素的个数,
‘sum’表示组合的个数,result
表示一个结果集合,令result[0]=1
,result[99]=100
当’n==0’,则找到一组满足条件的结果,输出结果,并’sum+1’
当’n>0’,则表明当前在寻找第(10-n)个元素,
从’i=max+1’开始寻找,直到找到i满足条件,将i添加到结果数组中result[10-n]=i
如果i递增到100还不满足条件,则回到上一个元素,n-1,取result[10-n-1]=result[10-n-1] +1
,进行回溯
代码
result = ['' for i in range(10)]
N = 100
sum = 0
result[0] = 1
def print_set(result):
global sum
if result[9]!=N:
return
else:
print(result)
sum +=1
def judge(x,l):
for i in range(0,l):
for j in range(0,l):
if x==result[i]+result[j]:return True
return False
def fun(max,n):
if n>0:
for i in range(max+1,N+1):
if judge(i,10-n):
result[10-n] = i
max = result[10-n]
fun(max,n-1)
else:
print_set(result)
fun(1,9)
print(sum)
运行结果
共2215种组合