C/C++教程

Complete the Sequence!

本文主要是介绍Complete the Sequence!,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Complete the Sequence!

给定一个数列 P(n),这个数列的通项公式可表示为: P(n)=a_{i}i \cdot⋅ n^{i}n**i+a_{i-1}i−1 \cdot⋅ n^{i−1}n**i−1+ ... +a_{1}1 \cdot⋅ n+a_{0}0。 现在给出这个数列的前S个数, 求这个数列接下来的后C项。 注意:输出可能的数中最小的。 输入:第一行数据组数t,之后每组数据分别有S,C和数列的前S项。 输出:对于每一组数据,输出接下来的C项。 t<=5000,S<=100,C<=100,S+C<=100。

输入:

4
6 3
1 2 3 4 5 6
8 2
1 2 4 7 11 16 22 29
10 2
1 1 1 1 1 1 1 1 1 2
1 10
3

输出:

7 8 9
37 46
11 56
3 3 3 3 3 3 3 3 3 3

方法:牛顿插值法

每次 求两项之间的差,形成一个新序列,不断向下求,知道序列公差为0的时候,再倒推回去,就可以的到完整序列

#include<iostream>
#include<iomanip>


using namespace std;

int nums[100][100];

int main(){
    int i,j;

    int time;
    scanf("%d",&time);
    while(time--){
        int s,c;
        for(i=0;i<100;i++){
            for(j=0;j<100;j++){
                nums[i][j]=0;
            }
        }
        scanf("%d%d",&s,&c);
        for(i=0;i<s;i++){
            scanf("%d",&nums[0][i]);
        }
        for(i=1;i<s;i++){
            for(j=0;j<s+c;j++){
                nums[i][j] = nums[i-1][j+1]-nums[i-1][j];
            }
        }

        for(i=s-1;i>=0;i--){
            for(j=1;j<s+c;j++){
                nums[i][j]=nums[i][j-1]+nums[i+1][j-1];
            }
        }

        for(i=s;i<s+c;i++){
            printf("%d ",nums[0][i]);
        }

        cout<<endl;

    }

    system("pause");
}
这篇关于Complete the Sequence!的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!