链接：http://blog.csdn.net/walkandthink/article/details/42683729
http://blog.csdn.net/u013050857/article/details/43929087
http://tieba.baidu.com/p/3807276796
http://www.guokr.com/post/456777/
fft学习笔记：http://www.gatevin.moe/category/acm/
* Codeforces 622F http://blog.csdn.net/liangzhaoyang1/article/details/53574708

include <cmath>  
using namespace std;  
double PointsInsert(int n,double xi,double *x,double *y)  
{  
    //n为插值点的个数 
    //N=2为两点高斯插值，即线性插值 
    //N=3为三点高斯插值，即二次插值 
    //xi为目标点的坐标，x和y为插值点的坐标值和数值 
    int i,j;  
    double *L;  
    double up,low,result;  
    L=new double[n+1];  
    for (i=1;i<=n;i++)  
    {  
        up=1.0;low=1.0;  
        for (j=1;j<=n;j++)  
        {  
            if (j!=i)  
            {  
                up=up*(xi-x[j]);  
                low=low*(x[i]-x[j]);  
            }  
        }  
        L[i]=up/low;  
    }  
    result=0.0;  
    for (i=1;i<=n;i++)  
    {  
        result=result+L[i]*y[i];  
    }  
    delete[] L;  
    return result;  
}  

int main()  
{  
    int n,i;  
    double *x,*y,xi;  
    n=2;  
    while (n>1)  
    {  
        cout<<"请输入插值点的个数(-1结束运算):";  
        cin>>n;  
        if (n>1)  
        {  
            cout<<"您要求"<<n<<<<endl;  
            x=new double[n+1];  
            y=new double[n+1];  
            cout<<"请输入"<<n<<"个点的x,y值:"<<endl;  
            for (i=1;i<=n;i++)  
            {  
                cin>>x[i]>>y[i];  
            }  
            cout<<"请输入需要插值的点的x:";  
            cin>>xi;  
            cout<<"插值计算结果为:"<<PointsInsert(n,xi,x,y)<<endl;  
            cout<<"插值计算完成！"<<endl;  
            cout<<"********************"<<endl;  
            delete[] x;  
            delete[] y;  
        }  
    }  
    return 0;  
}
2：
大家一定见过这种题目：给你一些数请找出这些数之间的规律，写出下一个满足该规律的数。
比如：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），从而可以计算未知点出的函数值，是插值法的基本思路。
代码:

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<n; i++)                  //录入插值点 
    {  
        xy[i][0]=i+1;  
        cin>>xy[i][1];  
    }  
    double lag=0.0;  
    for(int i=0; i<n; i++)  
    {  
        double ji=1.0;  
        for(int j=0; j<n; j++)  
        {  
            if(i!=j)  
                ji=ji*((x-xy[j][0])/(xy[i][0]-xy[j][0])); //基函数 
        }  
        lag=lag +ji* xy[i][1];                         //函数值 

    }  
    return lag;  
}  
int  main()  
{  
    //freopen("Intput.txt","r",stdin); 
    //freopen("Output(2).txt","w",stdout); 
    cin>>T;  
    while(T--)  
    {  
        cin>>n;  
        cout<<lagrange(n+1,n)<<endl;  
    }  
    return 0;  
}