蓝桥杯算法训练：数字游戏（python）_试题 算法训练 数字游戏

问题描述

　　给定一个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

 参考代码：

import itertools
n,m=map(int,input().split())
dp=[i+1 for i in range(n)]#生成一行n列的数组，初始值为i+1
sp=[]
for x in itertools.permutations(dp,n):
    dp=list(x) #因为itertools.permutations出来的结果是以元组的形式，这里要把他们转换成列表的形式，方便在后面使用下标进行访问
    sp=dp.copy()#数组的深拷贝和浅拷贝。将排列好的数组复制给sp，用sp进行计算，保留原始的dp，如果最后sp算的结果满足要求，则输出dp里的内容
    for j in range(n-1):
        for i in range(n-1):
                sp[i]=sp[i]+sp[i+1]
                #print(dp)
    #print("此时的sp为:",dp)#可以用这句话进行测试，观看效果
    if sp[0]==m:#每将一种情况算完就进行比较一次，如果发现是想要的值，就输出并且结束循环
        for f in dp:#直接遍历并输出数组，也就是列表里的内容
            print(f,end=' ')
        break

代码解释：

执着于自己的思路：

3 1 2 4
4 3 6
7 9
16

因为下面每一行的数据是由上一行的数据相加得到的，这么看示例直观的看可以以二维数组的形式存储，但是考虑到要有不同的序列，每一种情况都要算的话容易超时，所以方便计算就采取一维数组计算覆盖的方法，用计算的新的数值覆盖掉以前的值：sp[i]=sp[i]+sp[i+1]，另外发现计算的次数是n-1次，所以j的取值为0~n-2。其他可结合代码注释理解。

知识补充：

字典序，也就是全排列：

介绍什么是全排列：

经典算法：字典序排列_Espresso Macchiato的博客-CSDN博客杂谈：经典算法之字典序排列0. 引言1. 字典序排序2. 获取字典序排列的邻接元素1. 获取字典序排序的次小字符串2. 获取字典序排序的次大字符串3. 参考链接0. 引言最近连着两周打比赛都遇到了字符串字典序的相关问题，然后还连着两周都在这个坑里面摔死，简直了……因此，就趁着这个假期来整理一下字典序相关的内容，省的后面再在同一个问题上摔倒了……1. 字典序排序我们首先来看一下字典序排序的定义。考察两个字符串s以及s'，s字典序在s'之前的判断条件为：def is..https://blog.csdn.net/codename_cys/article/details/116721756介绍可以用来求全排列的函数：itertools库里的permutations函数

Python学习：itertools库 combinations() 和 permutations()_combinations 库_Carol.Carol的博客-CSDN博客@[TOC](itertools库 combinations() 和 permutations())欢迎使用Markdown编辑器你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。新的改变我们对Markdown编辑器进行了一些功能拓展与语法支持，除了标准的Markdown编辑器功能，我们增加了如下几点新功能，帮助你用它写博客：全新的界面设计 ，将会带来全新的写作体验；在创https://blog.csdn.net/sinat_37960022/article/details/110434470数组定义并初始化：

一维数组：dp=[i+1 for i in range(n)]#生成一行n列的数组，初始值为i+1

二维数组：dp=[[0 for i in range(n)]for j in range(m)]#生成m行n列的二维数组，初始值全为0

最后得分为90，有待改进......