NYOJ 178 找规律(Lagrange插值公式)

NYOJ 178 找规律(Lagrange插值公式)

链接： ​​click here​​

题意：

描述

大家一定见过这种题目：给你一些数请找出这些数之间的规律，写出下一个满足该规律的数。 比如：2 5 10 17 26，则可以看出这些数符合n*n+1这个通项公式，则下一个数为37。 这种通项公式不只一个，所以答案是不唯一的。但如果已知了N个数，且已知其通项公式是一个次数小于N的多项式，则答案就唯一确定了。 现在给你一个数列，请找出规律并求出其下一个数为多少？

第一行是一个整数T表示测试数据的组数(T<=20)

每组测试数据的第一行是一个整数N（1<=N<=5)

随后的一行有N个整数,表示该数列已知了的N个整数(这N个整数的值都不大于1000)。

输出 输出符合规律的下一个数

样例输入

2 2 1 2 5 2 5 10 17 26

样例输出

3 37

思路：Lagrange插值公式的运用., 一种离散数学上的方法： Lagrange插值法和Newton插值法解决实际问题中关于只提供复杂的离散数据的函数求值问题， 通过将所考察的函数简单化，构造关于离散数据实际函数f（x）的近似函数P（x），从而可以计算未知点出的函数值，是插值法的基本思路。

代码:

#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};const double eps = 1e-6;const double Pi = acos(-1.0);static const int inf= ~0U>>2;static const int maxn =110;int in[100],out[100],Map[200];int T,i,j,n;double lagrange(double x,int n) //函数定义{ double xy[5][5]; for(int i=0; i>xy[i][1]; } double lag=0.0; for(int i=0; i>T; while(T--) { cin>>n; cout<

When you want to give up, think of why you persist until now!

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。