蓝桥杯 ALGO-1005 数字游戏 python

试题 算法训练 数字游戏

问题描述

例如:
3 1 2 4
4 3 6
7 9
16
现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。

样例输入

``````4 16
``````

样例输出

``````3 1 2 4
``````

数据规模和约定

``````0<n<=10
``````

解题思路

内置库运用70分

``````import itertools
a = list(range(1,n+1))
n,sum = map(int,input().split())
for l in itertools.permutations(a,n):
l = list(l)
# print(l)
l2 = l[:]
for i in range(n-1):
for j in range(n-1-i):
l[j] += l[j+1]

if l[0] == sum:
for i in l2:
print(i,end=' ')
break
``````

DFS 70分

``````s = [0]*n
d = [0]*n
vis = [0]*n
n,sum = map(int,input().split())
def dfs(step):
if step == n:
s = d[:]
for i in range(n-1):
for j in range(n-1-i):
s[j] += s[j+1]
if s[0] == sum:
print(' '.join(str(i) for i in d))
return True
else:
return False

for i in range(0,n):
if vis[i] == 1:
continue
vis[i] = 1
d[step] = i + 1
if dfs(step+1):
return True
vis[i] = 0
return False

dfs(0)
``````

改进的90分代码

``````# return 杨辉三角的最后一行
def yh(num):
if num == 1:
res = [1]
else:
res = [[0]*num for i in range(num)]
for i in range(num):
for j in range(num):
res[i][0] = 1
if i == j:
res[i][j] = 1
for i in range(2,num):
for j in range(1,i):
res[i][j] = res[i-1][j-1] + res[i-1][j]
return res[num-1]

n,sum = map(int,input().split())
yh = yh(n)

d = [0]*n
vis = [0]*n

def dfs(step):
if step == n:
s = 0
for i in range(n):
s += d[i]*yh[i]
if s == sum:
print(' '.join(str(i) for i in d))
return True
else:
return False

for i in range(0,n):
if vis[i] == 1:
continue
vis[i] = 1
d[step] = i + 1
if dfs(step+1):
return True
vis[i] = 0
return False
if n == 1:
print(sum)
else:
dfs(0)
``````

完美的100分代码

``````# return 杨辉三角的最后一行
def yh(num):
if num == 1:
res = [1]
else:
res = [[0]*num for i in range(num)]
for i in range(num):
for j in range(num):
res[i][0] = 1
if i == j:
res[i][j] = 1
for i in range(2,num):
for j in range(1,i):
res[i][j] = res[i-1][j-1] + res[i-1][j]
return res[num-1]

n,sum = map(int,input().split())
yh = yh(n)

d = []
vis = [0]*(n+1)

def dfs(step,s):
if s > sum:
return False
if step == n:
if s == sum:
print(' '.join(str(i) for i in d))
return True
else:
return False

for i in range(1,n + 1 ):
if vis[i] == 0:
vis[i] = 1
d.append(i)
if dfs(step+1,s+yh[step]*i):
return True
vis[i] = 0
d.pop()
return False
if n == 1:
print(sum)
else:
dfs(0,0)
``````

What doesn’t kill you makes you stronger.

THE END