第十二章迭代算法內(nèi)容目標：迭代算法基本概念。遞推算法案例分析倒推算法案例分析迭代算法求解方程案例分析重難點：各種迭代算法設(shè)計思想1.遞歸算法的基本概念迭代法（Iteration）也稱為“碾轉(zhuǎn)法”，是一種不斷用變量的舊值遞推出新值的解決問題的一種方法。迭代算法一般用于數(shù)值計算。迭代法應(yīng)該是早已熟悉的算法策略。利用迭代算法策略求解問題，設(shè)計工作主要3步：確定迭代模型根據(jù)問題的描述，分析得出前一個（或幾個）值與其下一個值的迭代關(guān)系數(shù)學模型。當然這樣的迭代關(guān)系，最終會迭代出解的目標。建立迭代關(guān)系遞推數(shù)學模型一般是帶下標的字母，算法設(shè)計中要將其轉(zhuǎn)化為“循環(huán)不變式”----迭代關(guān)系式，迭代關(guān)系式就是一個直接或間接地不斷由舊值推出新值的表達式，存儲新值的變量稱為迭代變量。迭代關(guān)系式的建立是迭代算法設(shè)計的主要工作。對迭代過程進行控制確定在什么時候結(jié)束迭代過程，是設(shè)計迭代算法時必須考慮的問題。迭代過程的控制通常可分為兩種情況：一種是一致或可以計算處理所迭代次數(shù)，這時可以構(gòu)建一個固定次數(shù)的循環(huán)來實現(xiàn)對迭代過程的控制。另一種是所須的迭代次數(shù)無法確定，需要分析出迭代構(gòu)成的結(jié)束條件。2.1遞推法案例分析遞推法概念：遞推（Recursion）算法是迭代算法的最基本的表現(xiàn)形式。一般來講，一種簡單的遞推方法，是從小規(guī)模的問題推解出大規(guī)模問題的一種方法，也稱為“正推”。如：累加過程就是在求出前n-1項和的基礎(chǔ)上推出前n項和的，遞推公式是Sn=Sn-1+An。由于無須保存每次的累加結(jié)果，所以用一個迭代變量s存儲每次累加的結(jié)果，累加對象存儲在變量a中，這樣遞推公式就抽象成“循環(huán)不變”的累加式s=s+a。2.2遞推法案例分析問題描述：一對兔子從出生后第三個月開始，每月生一對兔子。小兔子到第三個月又開始生下一代兔子。假如兔子只生不死，一月份抱來一對剛出生的小兔子，問一年中每個月各有多少只兔子。2.3遞推法案例分析問題分析：尋找問題的規(guī)律性，需要通過對現(xiàn)實問題的具體實例進行分析，從而抽象出其中的規(guī)律。最基本的分析方法之一是“枚舉”，也就是將問題的求解過程及各種可能情況一一枚舉出來，從中發(fā)現(xiàn)解決問題的方法，下面就分析兔子繁殖的過程。一對兔子從出生后第三個月開始每月生一對兔子，第三個月后每月除了有上一個月的兔子外，還有新下小兔子，在下表中用斜體數(shù)字表示。則第三各月以后兔子的對數(shù)就是前兩個月兔子對數(shù)的和。繁殖過程如下。

1月2月3月 4月 5月 6月……1 11+1=22+1=33+2=55+3=8……從上面的分析，我們可以得到如下的數(shù)學模型：

y1=y2=1，yn=yn-1+yn-2,n=3,4,5……2.4遞推法案例分析代碼實現(xiàn)：publicvoidtzfy(){inti,a=1,b=1;//初始化第1、2個月的兔子對數(shù)intc;Console.WriteLine("第{0}月,有{1}對兔子",1,a);//打印第一個月的兔子數(shù)Console.WriteLine("第{0}月,有{1}對兔子",2,b);//打印第二個月的兔子數(shù)

for(i=1;i<=10;i++)//循環(huán)遞推求其他個月的兔子數(shù)

{ c=a+b; Console.WriteLine("第{0}月,有{1}對兔子",i+2,c);//打印第i+2月的兔子數(shù)

a=b; b=c; }}

3.1推到法案例分析推到法的基本概念：所謂的倒推法（InvertedRecursion）是對某些特殊問題所采用的違反通常習慣的，從后向前推解問題的方法。在不知前提條件的情況下，經(jīng)過從后向前遞推，來求解問題的初始數(shù)據(jù)，即由結(jié)果倒過來推解它的前提條件。另外在對一些進行分析或建立數(shù)學模型時，從前向后分析問題感到比較棘手，而采用倒推法，則問題很容易理解和解決。3.2推到法案例分析問題描述： 猴子吃桃子問題：一只小猴子摘下若干個桃子，每天吃現(xiàn)有的一半多一個，到第10天時就只有一個桃子了，求原有多少個桃子。問題分析：每天的桃子數(shù)為：

a10=1; a9=1+a10*2; a8=1+a9*2;……

遞推公式為：

ai=1+ai+1*2i=9,8,7,…,13.3推到法案例分析代碼實現(xiàn)： publicvoidhzwt() { inti,a; a=1; for(i=9;i>=1;i--) { a=1+a*2; } Console.WriteLine("總的桃子個數(shù)為：{0}",a); }

4.1迭代法求解方程的解迭代法求解方程：在科學計算領(lǐng)域，人們時常會遇到求解方程f（x）=0或微分方程的數(shù)值解計算問題?？墒侨藗兒茈y或無法找到類似一元二次方程的求根公式那樣的解析法（又稱直接求解法）去求解任意多項式方程。例如，一般的一元五次或更高次方程，其解都無法用解析方法表達出來。為此，已發(fā)明了很多數(shù)值算法（也稱數(shù)值計算方法），用來求解問題的近似解，這是一門專門的學科。這里僅對迭代法進行介紹。迭代法可分為精確迭代和近似迭代。前面的例子屬于精確迭代，而迭代法解方程一般屬于近似迭代。4.2推到法案例分析問題描述：用二分法求解一元非線性方程f（x）=1/2x3+2x2-8=0在【0，2】的近似根r，精確到0.0001。問題分析：可以用數(shù)學方法證明在0到2之間是單調(diào)遞增的。又x=0時，f（x）=-8；x=2時，f（x）=4，因此曲線f(x)在【0，2】間必與x軸有交點，則交點即是該問題的解。該問題的解可能是個無理數(shù)，無法通過計算機得到精確的解，我們只可能得到近似解，根據(jù)題意精確到0.0001，即是利用迭代法求得某個x0，使得|f（x0）|<0.0001，我們可認為x0就是該問題的解。4.3迭代法求解方程的解代碼實現(xiàn)：publicvoidfx(){floatx,x1=0,x2=2,f1,f2,f;//定義用以計算的局部變量

f1=x1*x1*x1/2+2*x1*x1-8;//計算f（0）的值保存到f1中

f2=x2*x2*x2/2+2*x2*x2-8;//計算f（2）的值保存到f2中

if((f1*f2)>0) //如果f1和f2同號無解

{Console.WriteLine("無解"); return; }do{ x=(x1+x2)/2; //計算x1和x2的中點x f=x*x*x/2+2*x*x-8;//計算中點x所對應(yīng)的f（x）的值

if(f==0) //如果f（x）=0問題得解

break; if(f1*f>0.0) //f（x）與f（0）同號，迭代右半?yún)^(qū)【x