#2
fall_bernana2019-11-25 09:09
以下是引用wrh100408在2019-11-24 12:02:09的发言: 不知道为什么,这个代码在运行的时候,总是会有“invalid syntax”的错误 #最短加法链问题 m=eval(input("请输入目标数:")) chain=[1,2] best_chain=[] depth=0 found=False #判断是否找到加法链 sumN=1 def back(step): global found global chain global best_chain global depth check=[] for x in range(10000): check.append(0) if step-1==depth: if chain[step-1]==m: found=True #找到加法链 best_chain=chain*1 return for i in range(1,step+1): #遍历子结点 for j in range(1,i+1)[::-1]: if chain+chain[j-1]<=chain[step-1]: #剪枝,下一层结点值必须大于上一层 break if chain+chain[j-1]<=n: #剪枝,只关心比n小的子结点 if check[chain+chain[j-1]==1: continue #就是这里一直有错 check[chain+chain[j-1]]=1 n=chain+chain[j-1] for t in range(step,depth): #计算depth内,以m为根的子树中的最大结点 n=n*2 if n<m:#判断n是否在以m为根的子树中 continue if len(chain)==step: chain.append(chain+chain[j-1]) else: chain[step]=chain+chain[j-1] back(step+1) if found:#找到加法链 return while(sumN<m): depth=depth+1 sumN=sumN*2 if m!=1: while not found: back(2) depth=depth+1 #depth为下界,表示加法链最短可以是depth(从0开始算) print("最短加法链为:{}".format(best_chain)) else: print(1) 在28行你的check[ 没有对应的 ] |
程序代码:
#最短加法链问题
m=eval(input("请输入目标数:"))
chain=[1,2]
best_chain=[]
depth=0
found=False #判断是否找到加法链
sumN=1
def back(step):
global found
global chain
global best_chain
global depth
check=[]
for x in range(10000):
check.append(0)
if step-1==depth:
if chain[step-1]==m:
found=True #找到加法链
best_chain=chain*1
return
for i in range(1,step+1): #遍历子结点
for j in range(1,i+1)[::-1]:
if chain[i-1]+chain[j-1]<=chain[step-1]:
#剪枝,下一层结点值必须大于上一层
break
if chain[i-1]+chain[j-1]<=n:
#剪枝,只关心比n小的子结点
if check[chain[i-1]+chain[j-1]==1:
continue #就是这里一直有错
check[chain[i-1]+chain[j-1]]=1
n=chain[i-1]+chain[j-1]
for t in range(step,depth):
#计算depth内,以m为根的子树中的最大结点
n=n*2
if n<m:#判断n是否在以m为根的子树中
continue
if len(chain)==step:
chain.append(chain[i-1]+chain[j-1])
else:
chain[step]=chain[i-1]+chain[j-1]
back(step+1)
if found:#找到加法链
return
while(sumN<m):
depth=depth+1
sumN=sumN*2
if m!=1:
while not found:
back(2)
depth=depth+1
#depth为下界,表示加法链最短可以是depth(从0开始算)
print("最短加法链为:{}".format(best_chain))
else:
print(1)
m=eval(input("请输入目标数:"))
chain=[1,2]
best_chain=[]
depth=0
found=False #判断是否找到加法链
sumN=1
def back(step):
global found
global chain
global best_chain
global depth
check=[]
for x in range(10000):
check.append(0)
if step-1==depth:
if chain[step-1]==m:
found=True #找到加法链
best_chain=chain*1
return
for i in range(1,step+1): #遍历子结点
for j in range(1,i+1)[::-1]:
if chain[i-1]+chain[j-1]<=chain[step-1]:
#剪枝,下一层结点值必须大于上一层
break
if chain[i-1]+chain[j-1]<=n:
#剪枝,只关心比n小的子结点
if check[chain[i-1]+chain[j-1]==1:
continue #就是这里一直有错
check[chain[i-1]+chain[j-1]]=1
n=chain[i-1]+chain[j-1]
for t in range(step,depth):
#计算depth内,以m为根的子树中的最大结点
n=n*2
if n<m:#判断n是否在以m为根的子树中
continue
if len(chain)==step:
chain.append(chain[i-1]+chain[j-1])
else:
chain[step]=chain[i-1]+chain[j-1]
back(step+1)
if found:#找到加法链
return
while(sumN<m):
depth=depth+1
sumN=sumN*2
if m!=1:
while not found:
back(2)
depth=depth+1
#depth为下界,表示加法链最短可以是depth(从0开始算)
print("最短加法链为:{}".format(best_chain))
else:
print(1)