问题：设多项式 $A(x) = a_0 + a_1x + ...+a_{n-1}x^{n-1}$，求多项式在某点的值。
分析：
将多项式按奇偶分类：
设 $A_{even}(x)$ 为偶数项系数构造的多项式，$A_{odd}(x)$ 为奇数项系数的多项式
$egin{aligned}
A(x) &= a_0 + a_1x + ...+a_{n-1}x^{n-1} \
&= A_{even}(x^2) + x*A_{odd}(x^2) \
&= (a_0+a_2x^2+a_4x^3+...+a_{n-2}x^{n-2}) + x*(a_1+a_3x^2 + a_5x^3+...+a_{n-1}x^{n-2})
end{aligned}$
例如：
设 $A_{even}(x) = 1+3x$，$A_{odd}(x) = 2+x$
$egin{aligned}
A(x) &= 1+2x+3x^2+x^3 \
&= A_{even}(x^2) + x*A_{even}(x^2) \
&= (1+3x^2) + x*(2+x^2)
end{aligned}$
容易写出如下的递归程序：
int a[100] = {1, 3, 2, 1}; int f(int* a, int siz, int x) { if(siz == 1) return a[0]; int b[100],c[100]; int b_cnt = 0, c_cnt = 0; for(int i = 0;i < siz;i++) { if(i&1) c[c_cnt++] = a[i]; else b[b_cnt++] = a[i]; } return f(b, b_cnt, x*x) + x*f(c, c_cnt, x*x); } //f(a, 4, 2) //x=2时的值
进一步思考，可以发现b、c数组并不是必须的，
我们只是按间隔取a数组，递归层次增加，间隔也随之增加即可。
int ff(int start, int end, int siz, int x) { int len = (1<<siz) - 1; //间隔长度 if(start+len >= end && start <= end) return a[start]; //只有一项时 return ff(start, end-len-1, siz+1, x*x) + x*ff(start+len+1, end, siz+1, x*x); }
根据规律，例如蝴蝶效应，也可以写成非递归形式。
完整代码：
#include<bits/stdc++.h> using namespace std; int a[100] = {1, 3, 2, 1}; int f(int* a, int siz, int x) { if(siz == 1) return a[0]; int b[100],c[100]; int b_cnt = 0, c_cnt = 0; for(int i = 0;i < siz;i++) { if(i&1) c[c_cnt++] = a[i]; else b[b_cnt++] = a[i]; } return f(b, b_cnt, x*x) + x*f(c, c_cnt, x*x); } int ff(int start, int end, int siz, int x) { // for(int i = start;i < end;i += (1 << siz)) printf("%d ", a[i]); // printf(" "); int len = (1<<siz) - 1; //间隔长度 if(start+len >= end && start <= end) return a[start]; return ff(start, end-len-1, siz+1, x*x) + x*ff(start+len+1, end, siz+1, x*x); } int main() { printf("%d ", f(a, 4, 2)); printf("%d ", ff(0, 4, 0, 2)); }