倒推法
所谓的倒推法，是对某些特殊问题所采用的违反通常习惯的，从后向前推解问题的方法，正向推理比较麻烦时，反而在逆向推理中更加巧妙地解决问题。
Case1猴子吃桃问题
一只小猴子摘了若干个桃子，每天吃总数的一半多一个，到第十天的时候就剩一个桃子，请问原来有多少桃子？
建立数学模型：
每天的桃子总数为
a10=1， a9=(1+a10)*2, a8=(1+a9)*2, .....
算法设计：
由于每天的桃子数只依赖前一天的桃子数，所以用一个迭代变量代表桃子个数就可以了
ai=（1+ai）*2 i 取值为9，8，7，6，5，4....1
main(){ int i,a; a=1; for(i=9;i>=1;i--){ a=(a+1)*2; cout<<a; } } 复制代码
由一个简单的小case对倒推法有一个简单的了解，让我们来看一个比较有趣的数学问题--“杨辉三角”
Case2杨辉三角（使用一维数组）:
关于杨辉三角问题，具体我就不进行过多的阐述了，因为想必你们的体育老师应该也讲过吧。
算法分析：
第i层有i列需要求解的i个数据，若从第一列开向后计算求i行时，由于用一个一维数组存储，每求出一个数将覆盖掉第i-1行对应的存储的值。这 将导致下一个数无法计算。而倒推法却不会，因此迭代表达式为：
A[1]= A[i]=1
A[j]=A[j]+A[j-1] j=i-1 ,i-2, i-3.....2
i行 i-1行 i-1行
为输出方便可以转化一下格式：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
算法如下：
main(){ int n,i,j, a[100]; cin>>n; cout<<"1";cout<<"/n"; a[1]=a[2]=1; cout<<a[1]<<a[2]; for(i=3;i<=n;i++){ a[1]=a[i]=1; for(j=i-1;j>1;j--){ a[j]=a[j]+a[j-1]; } for(j=1;j<=i;j++){ cout<<a[j]; } } cout<<"/n"; } 复制代码
迭代法解方程
Case1:求ax^3+bx^2+cx+d=0方程根的算法，系数a，b，c，d的值依次是1，2，3，4，由主函数输入。求x在1附近的一个实根并输出。
拓展：牛顿迭代法
牛顿迭代法又称切线法，它比一般的迭代法有更高的收敛速度。首先选择一个接近的函数f（x）零点的x0，计算对应的f（x0）和切线斜率f'（x） （f'(x)表示是函数的导数，求导是高数的内容不具体详细讲解，不懂的可以百度）然后计算穿过点（x0，f（x0））且斜率f'(x)的直线方程：
y=f（x0）+f'（x）（x-x0）
和x轴的交点的x坐标，也就是求如下方程的解：
0=f（x0）+f'（x）（x-x0）
迭代公式可以简化成：xn+1=xn-f（xn）/f'（n）
这就是有名的牛顿迭代公式，已经证明了，如果f'连续的，并且待求的零点x是孤立的，那么在零点x周围存在一个区域，只要初始值x0位于这个临近区域内，那么牛顿法必定收敛（关于收敛性也是高数的内容，就不详细讲解）
因此看完关于牛顿迭代，可得出算法如下：
main(){ float a,b,c,d,fx; cout<<'系数a,b,c,d：' cout>>a>>b>>c>>d; fx=f(a,b,c,d); cout<<'方程的根'<<fx; } float a,b,c,d; fx=f(a,b,c,d); { float x1=1,x0,f0,f1; do{ x0=x1; f0=((a*x0+b)*x0+c)*x0+d; f1=(3*a*x0+2*b)*x0+c; x1=x0-f0/f1; }while(fabs(x1-x0)>=1e-4){ return(x1); } }
