蓝桥杯——数字游戏

题目来源:蓝桥杯算法训练
知识点:全排列(穷举)

问题描述
  给定一个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;
}
上一篇:Android应用中如何保护JAVA代码


下一篇:《Python程学设计基础》【第四章】习题