算法数字游戏：给定一个1～N的排列a[i]，每次将相邻两个数相加

2023-01-11 11:19 689次浏览 0 条评论 C++

问题描述

　　给定一个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

赞助网站

<< · Back Index ·>>

小码农

算法数字游戏：给定一个1～N的排列a[i]，每次将相邻两个数相加

发表评论

取消回复

小码农

算法数字游戏：给定一个1～N的排列a[i]，每次将相邻两个数相加

相关文章

发表评论

取消回复