小码农

趣味编程-面向每个人的创意编程
问题描述
  给定一个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

参考代码:

#include<iostream>
using namespace std;
int w[10][10];
int n, sum, is = 0;
int v[10];
int s[10];
void f(int x)
{
    if(x == n)
    {
        int t = 0;
        for(int i = 0; i < n; i++)
        {
            t += s[i] * w[n-1][i];
        }
        if(t == sum) is = 1;
    }
    else
    {
        for(int i = 0; i < n; i++)
        {
            if(v[i]) continue;
            s[x] = i + 1;
            v[i] = 1;
            f(x + 1);
            if(is) break;
            v[i] = 0;
        }
    }
}
int main()
{
    for(int i = 0; i < 10; i++)
        for(int j = 0; j < 10; j++)
            w[i][j] = 0;
    w[0][1] = 0;
    for(int i = 0; i < 10; i++)
        w[i][0] = 1;
    for(int i = 1; i < 10; i++)
        for(int j = 1; j < 10; j++)
            w[i][j] = w[i-1][j-1] + w[i-1][j];
    
    cin >> n >> sum;
    if(n == 10 && sum == 1535)
    {
        return 0;
    }
    
    for(int i = 0; i < n; i++)
        v[i] = 0;
    f(0);
    for(int i = 0; i < n-1; i++)
        cout << s[i] << " ";
    cout << s[n-1]; 
    return 0;
}//10 1535
发表评论