蓝桥杯——数字游戏

题目来源：蓝桥杯算法训练 知识点：全排列（穷举）

问题描述
　　给定一个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

问题分析

一个 1 ~ N 的整数数列，在特定的排列下相邻数两两相加得到一行新的整数数列，重复两两相加操作，最终得到一个数。显然，我们需要知道 1 ~ N 的所有的排列，即一个数列的全排列。

如何求出一个序列的全排列呢？C++的STL为我们提供了一个十分有用的函数：next_permutation。它能够按照字典序从小到大生成一个序列的全排列，只需要传入这个序列的起始和结束位置即可。注意：使用next_permutation求全排列时，需要首先对数列进行从小到大的排序。

#include #include #include #include using namespace std;int main() {vector range {1,2,3,4};do {// 具体操作}while(next_permutation(begin(range), end(range)));return 0;}

在知道序列的所有排列后，对每个排列都进行两两相加，看看最终的结果是否等于输入的和。由于next_permutation求得的序列是从小到大，所以第一个找到的符合条件的序列就是字典序最小的序列，直接输出即可。

代码

#include using namespace std;int main() {int n, sum;cin >> n >> sum;int* number_1 = new int[n + 1]();for(int i=1; i<=n; i++) {number_1[i] = i;}int** number_2 = new int*[n + 1]();for(int i=1; i<=n; i++) {number_2[i] = new int[n + 1]();}do {for(int i=1; i<=n; i++) {number_2[1][i] = number_1[i];}for(int i=2; i<=n; i++) {for(int j=1; j<=n-i+1; j++) {number_2[i][j] = number_2[i-1][j] + number_2[i-1][j+1];}}if(sum == number_2[n][1]) {for(int i=1; i<=n; i++) {cout << number_2[1][i] << " ";}cout << endl;break;}} while(next_permutation(number_1 + 1, number_1 + n + 1));delete[] number_1;for(int i=1; i<=n; i++) delete[] number_2[i];delete[] number_2;return 0;}