蓝桥杯 ALGO-1005 数字游戏 python
试题 算法训练 数字游戏
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
例如:
3 1 2 4
4 3 6
7 9
16
现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。
输入格式
第1行为两个正整数n，sum
输出格式
一个1～N的一个排列
样例输入
4 16
样例输出
3 1 2 4
数据规模和约定
0<n<=10
解题思路
其实这道题，我真的是跌宕起伏，如果是C++我可能早就写出来了吧，但是由于是python，很多解就不能暴力搜索了，要不然1-10的暴力搜索也不是不可以，孩子快哭了，不过无所谓，就当锻炼算法吧
首先给出两个70分的代码，在这两个code之中，都有一些比较好的思想，第一个就是可以直接利用我们内置库函数，对我们给出的数组进行一个全排列，然后我们直接累加迭代发现sum一样不就可以了么，这多么简单啊，还要搞什么呀哈哈哈，结果70分，有些案例就是过不了，时间直接TLE，让人绝望啊，先给出代码，代码思想很简单，就是得到全排列然后累加求和
内置库运用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
结果只有70分
然后行吧，用点算法吧，用搜索咯，那肯定是比较常见又简单的DFS咯，很简单的想法，我们可以在本身的数组上进行一个累加，这样最后得到的结果元素1也就是我们的s[0] 如果是sum的时候，我们就可以直接打印出结果了。
然后后面一段就是用dfs思想了，如果visit过了就换一个的，不断的迭代，直到有n个数据，我们才进行判断
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)
但是结果还是差强人意，虽然会比上面的时间复杂度低一点，但是还是70分啊，还有样例还是过不了，我差点绝望了，我就看啊看，到底有什么算法可以解决。其实对于我们的程序来说，最耗时间的一部分第一个是我们的赋值，我们的d赋值可以利用append,pop这些时间比较少的，其次就是我们求和那一部分是一个二重循环，时间复杂度比较高。
然后我就思前想去，突然，我在想，每一行中的数据求和与我们最后得到的和有什么关系么，后面，我终于悟到了，杨辉三角！！！
这不就是一个典型的杨辉三角么，按样例来看，杨辉三角的底层是1 3 3 1，求和就是3x1 + 1x3+ 2x3 + 4x1 = 16，哇，这么说的话，其实我并不用算太多，我可以直接进行一个计算杨辉三角的底层，只有一个循环，这就简单了
所以首先小小改进了一下
改进的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)
结果还是大意了，只有80，所以其实在我们的DFS中，我们还需要一些剪枝之类的操作才可以得到比较好的结果，所以用同样的想法进行一个改进，最后终于圆满了，我们可以在本身要计算的时候，传入的就是求和的结果，如果大于我们需要的sum就直接break，也就是剪枝了，这样可能就比较好，减少了循环的计算。
完美的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)
所以最后终于AC了，结束了，good，还好成功了，没有放弃
每日一句
What doesn’t kill you makes you stronger.
没能摧毁你的，必使你强大。