蓝桥杯 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.
没能摧毁你的,必使你强大。