poj3187-Backward Digit Sums(枚举全排列)

一,题意:
输入n,sum,求1~n的数,如何排列之后,相邻两列相加,直到得出最后的结果等于sum,输出1~n的排列(杨辉三角)
    3 1 2 4 //1~n 全排列中的一个排列

    4 3 6

    7 9

sum = 16
二,思路:
枚举1~n的所有排列,直至有一种排列使得最后结果为sum就结束。next_permutation()全排列函数的运用

 #include<iostream>
#include<algorithm>
using namespace std;
int main() {
int n, sum;
while (cin >> n >> sum) {
int a[], b[];
for (int i = ; i < n; i++) {
a[i] = i + ;
}
do {
for (int i = ; i < n; i++) {
b[i] = a[i]; //不能改变a[]中的值,用b[]代替a[]
}
int i;
for (i = n; i > ; i--) { //第一次n个数相加,第二次n-1个数相加...直到只剩2个数相加
for (int j = ; j < i - ; j++) {
b[j] = b[j] + b[j + ]; //后面的每一个数往前一位加,最后都加到a[0]上
}
}
if (b[] == sum)break;
} while (next_permutation(a, a + n));
for (int i = ; i < n ; i++) {
cout << a[i] << " ";
}
cout << endl;
}
return ;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

上一篇:pascal矩阵 分类: 数学 2015-07-31 23:01 3人阅读 评论(0) 收藏


下一篇:正则匹配 去掉 多余的js和html标签