[蓝桥杯python] 数字游戏：给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的 *** 作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。 例如:

   [蓝桥杯python] 数字游戏

问题描述

1、资源限制

2、输入格式

3、输出格式

4、样式输入及输出

5、代码及解析

大功告成！编写不易，大家成功后点个关注or赞谢谢~~

---

问题描述

　　给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的 *** 作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。

　　例如:
　　3 1 2 4
　　4 3 6
　　7 9
　　16
　　现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。

若有多种答案，则输出字典序最小的那一个。

数据保证有解。

---

1、资源限制

资源限制

时间限制：1.0s   内存限制：256.0MB

2、输入格式

第1行为两个正整数n，sum

3、输出格式

一个1～N的一个排列

4、样式输入及输出

样例输入

4 16

样例输出

3 1 2 4

5、代码及解析

具体解析请大家自己看一下代码中的备注，在此不多做解释。

注意：真的真的尽力了，答案确实可以算出来但是运算超时只有30分，顶不住了.....

           代码里面很冗长，有些步骤可能没有必要，但是我不知道怎么优化。

           如果大家想到了解决方法请在评论区说下，大家一起努力

In = input().split()
n = int(In[0]) #行数
num = int(In[1]) #最终总数
rect = [] #记录最终的排序
#计算三角函数第n行的每个数
def trangle(x):
    trangle_rect = [[1],[1,1]]
    for i in range(2,x):
        mid = []
        for j in range(0,i+1):
            if j==0 or j==i:
                mid.append(1)
            else:
                mid.append(trangle_rect[i-1][j] + trangle_rect[i-1][j-1])
        trangle_rect.append(mid)
    return trangle_rect[-1]

trangle_n = trangle(n)
mid = [] #记录过程中的数组
def trackback(n,s): #n=几行，starIndex=起始位置
    #判断是否成功
    if len(mid) > n:
        return
    game_over(s)
    #回溯
    for j in range(1,n+1):
        mid.append(j)
        trackback(n,j)
        mid.pop()

#代码冗长单独写一个判断是否成功的函数
def game_over(s):
    all_num = 0
    #判断如果长度不同直接返回
    if len(mid) == n:
        for i in range(0,n):
            all_num += int(trangle_n[i]) * int( mid[i])
        if all_num == num:
            mid_set = set(mid)
            #判断是否有重复的数
            if len(mid_set) != len(mid):
                return
            else:
                rect.append(mid[:])
                return

trackback(n,0)

for i in range(0,n):
    print(rect[0][i],end=" ")

结果：

 

 

 但是可以看出，代码还是有缺陷，但是可以解决问题 

希望有大神可以在评论区提提优化意见，大家一起努力 ！！！

---

自己写的所以有点复杂，但是至少能完成嘿嘿。

如果各位有优化欢迎评论区讨论！！

大功告成！编写不易，大家成功后点个关注or赞谢谢~~

---