当前位置:首页 » Project Euler » 详细页

Optimum polynomial 题号:101 难度: 35 中英对照

If we are presented with the first k terms of a sequence it is impossible to say with certainty the value of the next term, as there are infinitely many polynomial functions that can model the sequence.

As an example, let us consider the sequence of cube numbers. This is defined by the generating function,
un = n3: 1, 8, 27, 64, 125, 216, ...

Suppose we were only given the first two terms of this sequence. Working on the principle that "simple is best" we should assume a linear relationship and predict the next term to be 15 (common difference 7). Even if we were presented with the first three terms, by the same principle of simplicity, a quadratic relationship should be assumed.

We shall define OP(k, n) to be the nth term of the optimum polynomial generating function for the first k terms of a sequence. It should be clear that OP(k, n) will accurately generate the terms of the sequence for nk, and potentially the first incorrect term (FIT) will be OP(k, k+1); in which case we shall call it a bad OP (BOP).

As a basis, if we were only given the first term of sequence, it would be most sensible to assume constancy; that is, for n ≥ 2, OP(1, n) = u1.

Hence we obtain the following OPs for the cubic sequence:

OP(1, n) = 1 1, 1, 1, 1, ...
OP(2, n) = 7n−6 1, 8, 15, ...
OP(3, n) = 6n2−11n+6      1, 8, 27, 58, ...
OP(4, n) = n3 1, 8, 27, 64, 125, ...

Solution

已知过点${(x_i,y_i)}_{i=1,...,k}$的多项式,利用拉格朗日插值法可以得到: 令 $$L_i(x)=y_i \times \prod_{j=1,...,k;j\neq i} \left( \frac{x-x_j}{x_j-x_i} \right)$$ 显然可以得到$L_i(x_j)=0,\forall j\neq i$,并且$L_i(x_i)=y_i$。 进而得到拉格朗日插值多项式: $$f(x)=\sum_{i=1}^k L_i(x)$$ 带入本题,可以得到对于$k=1,...,n$所求的值为: $$f(k+1)=\sum_{i=1}^k \left[ y(i) \times \prod_{j=1,...,k;j \neq i} \left( \frac{k+1-j}{j-i} \right) \right]$$ 其中$y(i)$为题目给出的多项式带入$i$的值

Code


public final class p101 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	
    static public String run(){
    	long y[]=new long [11];
    	for(int i=1;i<=10;i++){
    		long x=i;
    		y[i]=1-x+pow(x,2)-pow(x,3)+pow(x,4)-pow(x,5)+pow(x,6)-pow(x,7)+pow(x,8)-pow(x,9)+pow(x,10);
    	}
    	long ans=0;
    	for(int t=1;t<=10;t++){
    		long res=0;
    		for(int i=1;i<=t;i++){
				long cnt=1;
				for(int j=1;j<=t;j++) if(j!=i)
					cnt*=t+1-j;
				for(int j=1;j<=t;j++) if(j!=i)
					cnt/=i-j;
				res+=y[i]*cnt;
			}
			ans+=res;
    	}
    	return Long.toString(ans);
    }
    static public long pow(long x,int n){
    	long res=1;
    	while(n-->0) res*=x;
    	return res;
    }
}
37076114526
0ms