题目来源:蓝桥杯算法训练
知识点:全排列(穷举)
问题描述
给定一个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
问题分析
一个 1 ~ N 的整数数列,在特定的排列下相邻数两两相加得到一行新的整数数列,重复两两相加操作,最终得到一个数。显然,我们需要知道 1 ~ N 的所有的排列,即一个数列的全排列。
如何求出一个序列的全排列呢?C++的STL为我们提供了一个十分有用的函数:next_permutation。它能够按照字典序从小到大生成一个序列的全排列,只需要传入这个序列的起始和结束位置即可。
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> range {1,2,3,4};
do {
// 具体操作
}while(next_permutation(begin(range), end(range)));
return 0;
}
在知道序列的所有排列后,对每个排列都进行两两相加,看看最终的结果是否等于输入的和。由于next_permutation
求得的序列是从小到大,所以第一个找到的符合条件的序列就是字典序最小的序列,直接输出即可。
代码
#include <bits/stdc++.h>
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;
delete[] number_2;
return 0;
}