典型问题迭代法也称辗转

的是直接法（或者称为一次解法，即解决问题。迭代法又分为精确迭代和近似迭代“二分法”和“迭代法”属于近似迭代法迭代算法是用计算机（或一定步骤（或这些步骤）时，都从变量的原值推出它的一个新值 Methodx=Bx+f（x、B、f同为矩阵，任意线性方程组都可以变换成此形式用x(k+1）=Bx(k)+f（括号中为上标，代表迭代kxk=0)逐步带入求近似解的方法称为迭代法（或称一阶定常迭代法。如klimx（k）x*，称此迭代法收敛x*就是此方程组的解，跟迭代法相对应的是直接法（或者称为一次解法即的快速解决问题，例如通数方程没有解析解，参见定理，这时候或以通过迭代法寻求方程（组）的近似最常见的迭代法是法。其他还包括最速下降法、共轭迭代法、变尺度迭代法、最1每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第12个月分析：这是一个典型的递推问题。我们不妨假设第1个月时兔子的只数为u12u23u3，……根据题意，“这种兔u11u2u1u112u3u2u214，……un=u(n－1）×2(n≥对应un和u(n－1，定义两个迭代变量y和x，可将上面的递推转换成如让计算机对这个迭代关系重复执行11次，就可以算出第12fori=2tonextiprinty例2：阿米巴用简单的方式繁殖，它每一次要用3分钟。将若干个阿米放在一个盛满营养参液的容器内，45分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴220,220个。试问，开始的时候往容器内放了多少个阿米巴？请编程序算出。分析：根据题意，阿米巴每3分钟一次，那么从开始的时候将阿米巴放入容器里面，到45分钟后充满容器，需要45/3=15次。而“容器最多可以装阿米巴2^20个”，即阿米巴15次以后得到的个数是2^20。题目要求我们计算之前的阿米巴数，不妨使用倒推的方法，从第15次之后的2^20个，倒推出第15次之前（即第14次之后）的个数，再进一步倒推出第13次之后、第12次之后、……第1次之前的个数。设第1次之前的个数为x0、第1次之后的个数为x1、第2次之后的个数为x2、……第15次之后的个数为x15，则有x14=x15/2x13=x14/2xn-1=xn/2(n因为第15次之后的个数x15是已知的，如果定义迭代变量为x，则可以将上x=x/2（x的初值为第15次之后的个数让这个迭代重复执行15次，就可以倒推出第1次之前的阿米巴个数。因为fori=1to15nextiprintxMath.pow（2,20例3：验证谷角猜想。数学家在研究自然数时发现了一个奇怪现象：对nn2n3，然后再加1。如此经过有限次运算后，总可以得到自然数1。人们把的这一发现叫要求：编写一个程序，由键盘输入一个自然数n，把n经过有限次运算后，最终变成自然数1的全过程打印出来。当nn=n/2；当nn=n*3+1。用QBASIC语言把它描述出来就ifnthenendif迭代变量n最终变成自然数1，这是我们无法计算出来的。因此，还需进一步确定用来n，只要1，就已经完成了验证工作。因此，用来结束迭代过input"Pleaseinputn=";ndountiln=1ifnmod2=0rem如果n为偶数，则调用迭代n=n/2print"—print"—";n;endvoidmain(){doublea,x0,x1;printf("Inputscanf("%f",&a；”？{{}}：x=1/2*x0+a/x0利用迭代求出一个x1。此值与真正的a的平方根值相比，误差很大。⒊利用迭代再求出一个新的x1的值，也就是用新的x0又求出一个新的平方根值x=g(x，然后按以下步骤执行：g(x1x0x1C程序的形式表示为：x0=初始近似根；do{x0=g(x1；while(fabs(x0-x1）>Epsilon%f\n”，x0}迭代算法也常用方程组的根，xi=gi(X)(I=0，1，…，n-{fordo{for(i=0;ifor(i=0;iforif(fabs(y-x)>delta)delta=fabs(y-(delta>Epsilonfor(i=0;i%f”，I，xprintf（“\n”}⑵方程虽然有解，但迭代选择不当，或迭代的初始近似根选择不合理，也会导致N的问题，设法将它分解成N=1时，能直接得解。fib（nfib(n)=fib(n-1）+fib(n-2）（n>1时。intfib(int{if(n==0)return0;if(n==1）return1;if(n>1）returnfib(n-1）+fib(n-}fib(n，把fib(n-1）fib(n-fib(nfib(n-1）fib(n-22fib(0fibn为1和0的情况。fib(n）的结果。进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行例如上例计算那契数列的第n项的函数fib）应采用递推算法，即从那契数列的n项。问题描述：找出从自然数1、2、……、nrn=5，r=3的所有组合为：⑴5、4、3⑵5、4、2⑶5、4、1⑷5、3、2⑸5、3、1⑹5、2、⑺4、3、2⑻4、3、1⑼4、2、voidcomb(intm,intk）为找出从自然数1、2、……、mk个数的所有组合。当组合m-1k-1m个aka[k]中，当##defineMAXN100inta[MAXN];voidcomb(intm,int{intfor(i=m;i>=k;i--{a[k]=i;if(k>1）{for(j=a[0];j>0;j--)printf（“\n”}}}void{comb（5,3}nn件物品中选取一部分物品的方案于数组option[]，该方案的总价值存于变量maxv。当前正在新方案，其物品选择cop[i-1i件物品；当前方案已包含的物品的重量之和为tw；至此，若其余物品都选择是可能的话，本方案能达到tvtv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，继续当前方案变成无意义的工作，应终止当前方案，立即去下一个方案。因为当方案的总价值不比maxv大时，该方案不会被再，这同时保证函数后i⑴考虑物品iii也有可能会找到价值更大的方/*i包含在当前方案中的可能性*/if（包含物品i是可以接受的）{iiftry(i+1,tw+i的重量，tv);i不包含状态；}/*i不包含在当前方案中的可能性*/if（i仅是可男考虑的）if}物品0123重量532价值443##defineNintoption[N],cop[N];struct{doubleweight;doublevalue;intvoidfind(inti,doubletw,double{int/*i包含在当前方案中的可能性*/if(tw+a.weight<=limitW){cop=1;if(i{for(k=0;k}}/*i不包含在当前方案中的可能性*/if(tv-a.value>maxV)if(i{for(k=0;k}}void{intk;\n”scanf（“%d”，&n);\n”for(totv=0.0,k=0;k{scanf（“%1f%1f”，&w,&v);}\n”for(k=0;kfind(0,0.0,totV);for(k=0;kif(option[k])printf（“%4d”，k+1printf（“\n总价值为}##defineN100doublelimitW;intcop[N];structele{doubleweight;doublevalue;}intk,n;struct{int;doubletw;doubletv;voidnext(inti,doubletw,double{twv.=1;twvtw=tw;twvtv=tv;}doublefind(structele*a,int{intfor(totv=0.0,k=0;kWhile{f=twv.;tw=twvtw;tv=twvtv;{case1:if(tw+a.weight<=limitW)if(i{next(i+1,tw+a.weight,tv);}{maxv=tv;for(k=0;k}case0:i--;default:if(tv-a.value>maxv)if(i}{max