叠代算法是用計算機解決問題的基本方法。它利用計算機運算速度快、適合重復運算的特點，使計算機重復執行壹組指令(或某些步驟)，每執行壹次這組指令(或這些步驟)，就從其原始值中推導出壹個變量的新值。
利用叠代算法解決問題，我們需要做以下三個方面的工作:
首先，確定叠代變量。在叠代算法可以解決的問題中，至少有壹個變量直接或間接地從舊值推導出新值，這個變量就是叠代變量。
第二，建立叠代關系。所謂叠代關系，是指如何從壹個變量的上壹個值推導出下壹個值的公式(或關系)。叠代關系的建立是解決叠代問題的關鍵，通常可以通過遞歸或逆向推導來完成。
第三，控制叠代過程。叠代過程何時結束？這是寫叠代程序時必須考慮的問題。叠代過程不能無休止地重復。叠代過程的控制通常可以分為兩種情況:壹種是所需叠代次數是某個值，可以計算；另壹個是不能確定所需的叠代次數。對於前壹種情況，可以構造固定數量的循環來控制叠代過程；在後壹種情況下，有必要進壹步分析用於結束叠代過程的條件。
壹個新品種的兔子被引進到壹個農場。這種兔子從出生後的第二個月開始，每個月都會生壹只新兔子，新兔子也會以同樣的方式繁殖。如果所有的兔子都沒有死，那麽在12月這個農場有多少只兔子？
分析:這是典型的遞歸問題。我們不妨假設第1個月的兔子數是u 1，第2個月的兔子數是u 2，第3個月的兔子數是u 3...根據問題的意思，“這種兔子從出生的次月開始，每個月生壹只新兔子”。
u 1 = 1，u 2 = u 1 + u 1 × 1 = 2，u 3 = u 2 + u 2 × 1 = 4，…
根據這壹規律，可以總結出以下遞推公式:
u n = u n - 1 × 2 (n ≥ 2)
對應於u n和U n-1，定義了兩個叠代變量Y和X，上述遞推公式可以轉化為如下叠代關系:
y=x*2
x=y
讓計算機重復這個叠代關系11次，就可以算出12月時的兔子數量。參考程序如下:
cls
x=1
對於i=2到12
y=x*2
x=y
接下來我
打印y
結束
例2:變形蟲通過簡單的分裂繁殖，每次分裂需要3分鐘。將幾條阿米巴原蟲放入裝有營養人參液的容器中，45分鐘後容器內將充滿阿米巴原蟲。已知該容器可容納2 20只阿米巴原蟲。壹開始容器裏放了幾條變形蟲？請編程。
解析:根據題意，阿米巴每3分鐘分裂壹次，所以壹開始把阿米巴放進容器，45分鐘後裝滿容器，需要45/3=15次。但“容器最多能裝2 ^ 20個阿米巴”，即除以15次後得到的阿米巴數是2 ^ 20。題目要求我們在除法之前計算出變形蟲的數量。我們不妨用倒推的方法，由15除後的2 ^ 20推導出15除前的數(即14除後的數)，再進壹步推導出13除後的數，12除，...
設第1次拆分前的數為x ^ 0，第1次拆分後的數為x ^ 1，第2次拆分後的數為x ^ 2，...15拆分後的數字是x 15，則有
x 14 =x 15 /2、x 13 =x 14 /2、…… x n-1 =x n /2 (n ≥ 1)
因為第15次拆分後的數是已知的，所以如果叠代變量定義為X，上面的倒推公式就可以轉化為下面的叠代公式:
X = X/2(X的初始值是第15次拆分後的數字2 ^ 20)。
將這個叠代公式重復15次，就可以推算出1除法之前的阿米巴蟲數。因為所需的叠代次數是壹個確定的值，所以我們可以使用固定的循環次數來控制叠代過程。參考程序如下:
cls
x=2^20
對於i=1到15
x=x/2
接下來我
打印x
結束
例3:驗證谷角猜想。日本數學家谷垣禎壹在研究自然數時，發現了壹個奇怪的現象:對於任意自然數n，如果n是偶數，則除以2；如果n是奇數，則乘以3，然後加上1。經過有限次運算，總能得到自然數1。人們把塔納基·左師的這壹發現稱為“塔納基猜想”。
要求:寫壹個程序，通過鍵盤輸入壹個自然數N，經過有限次運算，打印出N變成自然數1的全過程。
解析:定義叠代變量為n，根據谷角猜想的內容，可以得到兩種情況下的叠代關系:當n為偶數時，n = n/2；當n為奇數時，n=n*3+1。用QBASIC語言描述就是:
如果n是偶數，那麽
n=n/2
其他
n=n*3+1
如果…就會結束
這是壹個需要計算機重復的叠代過程。這個叠代過程需要重復多少次才能使叠代變量n最終變成壹個1的自然數，這是我們無法計算的。因此，有必要進壹步確定用於結束叠代過程的條件。仔細分析題目的要求，不難看出，對於任意給定的自然數n，只要經過有限次運算就能得到自然數1，驗證工作就已經完成了。因此，結束叠代過程的條件可以定義為:n=1。參考程序如下:
cls
輸入“請輸入n =”；n
直到n=1
如果n模2=0，則
Rem如果n是偶數，調用叠代公式n=n/2。
n=n/2
打印“”；n；
其他
n=n*3+1
打印“”；n；
如果…就會結束
環
結束
叠代法
叠代法是壹種常用的求方程或方程近似根的算法設計方法。設方程為f(x)=0，用某種數學方法推導出等價形式x=g(x)，然後按照以下步驟:
(1)選擇壹個方程的近似根，賦給變量x0；
(2)將x0的值保存在變量x1中，然後計算g(x1)，將結果保存在變量x0中；
(3)當x0與x1之差的絕對值小於規定的精度要求時，重復步驟(2)的計算。
如果方程有根，且用上述方法計算的近似根序列收斂，則認為用上述方法計算的x0是方程的根。上述算法以C程序的形式表示如下:
求方程根的叠代算法
{x0=初始近似根；
做{
x 1 = x0；
x0 = g(x 1)；/*根據特定等式計算新的近似根*/
} while ( fabs(x0-x1)>ε)；
Printf("方程的近似根是%f\n "，x0)；
}
叠代算法也常用於求方程的根，這樣
X=(x0，x1，…，xn-1)
讓方程式成為:
xi=gi(X) (I=0，1，…，n-1)
尋找方程根的叠代算法可以描述如下:
求方程根的叠代算法
{ for(I = 0；我
X=初始近似根；
做{
for(I = 0；我
y = x；
for(I = 0；我
X = gi(X)；
for(δ= 0.0，I = 0；我
if (fabs(y-x)>delta)delta = fabs(y-x)；
} while(delta & gt；ε)；
for(I = 0；我
Printf("變量x[%d]的近似根是%f "，I，x)；
printf(" \ n ")；
}
在用叠代法求根時，要註意以下兩種可能的情況:
(1)如果方程無解，算法得到的近似根序列將不收斂，叠代過程成為無限循環。所以在使用叠代算法之前，要檢查方程是否有解，並限制程序中的叠代次數。
(2)雖然方程有解，但叠代公式選擇不當或初始近似根選擇不合理也會導致叠代失敗。
遞歸
遞歸是設計和描述算法的強大工具。因為它經常用於復雜算法的描述，所以在介紹其他算法設計方法之前，我們應該先討論壹下。
可以遞歸描述的算法通常具有以下特點:為了解決規模為n的問題，盡量將其分解為更小的問題，然後方便地由這些小問題的解構造大問題的解，這些更小的問題也可以用同樣的分解合成方法分解為更小的問題，由這些更小問題的解構造更大問題的解。特別地，當標度N=1時，可以直接得到解。
問題是寫出並計算斐波那契數列的第n個函數fib(n)。
斐波那契數列是:0，1，1，2，3，...，即:
fib(0)= 0；
fib(1)= 1；
Fib(n)=fib(n-1)+fib(n-2)(當n >時；1).
寫為遞歸函數的有:
中間纖維(中間纖維)
{ if (n==0)返回0；
if (n==1)返回1；
如果(n & gt1)返回光纖(n-1)+光纖(n-2)；
}
遞歸算法的實現過程分為遞歸和回歸兩個階段。在遞歸階段，壹個更復雜的問題(規模n)的解被推到壹個比原問題更簡單的問題(規模小於n)的解。比如上面的例子，求解fib(n)並推求出fib(n-1)和fib(n-2)。也就是說，為了計算fib(n-1)和fib(n- 2)，必須先計算fib(n-1)和fib(n-2)，必須先計算fib(n-3)和fib(n-4)。依此類推，直到計算出fib(1)和fib(0)，立即可以分別得到1和0的結果。在遞歸階段，必須有終止遞歸的情況。比如在函數fib中，當n為1和0時。
在回歸階段，當得到最簡單情況的解時，它壹步壹步返回得到稍微復雜的問題的解，比如得到fib(1)和fib(0)後，它返回得到fib(2)的結果，...，在獲得fib(n-1)和fib(n-2)之後。
編寫遞歸函數時，要註意函數中局部變量和參數的知識僅限於當前調用層。當它被推到“簡單問題”層時，原始層中的參數和局部變量被隱藏。在壹系列“簡單問題”層中，它們都有自己的參數和局部變量。
因為遞歸引起壹系列的函數調用，而且可能有壹系列的重復計算，所以遞歸算法的執行效率比較低。當遞歸算法可以很容易地轉換成遞歸算法時，程序通常是根據遞歸算法編寫的。比如上面例子中要用遞歸算法計算斐波那契數列第n項的函數fib(n ),即從斐波那契數列的前兩項開始，從前兩項開始逐壹計算下壹項，直到計算出所需的第n項。
問題組合問題
問題描述:從自然數1，2，中求R數的所有組合，...例如，n=5和r=3的所有組合是:(1)5，4，3 (2)5，4，2 (3)5，4和1。
(4)5、3、2 (5)5、3、1 (6)5、2、1
(7)4、3、2 (8)4、3、1 (9)4、2、1
(10)3、2、1
通過分析列出的10個組合，我們可以用這種遞歸的思想來考慮求組合函數的算法。設函數void comb(int m，int k)用於從自然數1，2，...當組合的第壹個號碼被選中時，後面的號碼是剩余的m-1個號碼中的k-1個號碼的組合。這就把從m的數中求k的數的組合問題轉化為從m-1的數中求k-1的數的組合問題。設函數引入工作數組a[]存儲求解出的組合數，約定函數將確定的k個數組合的第壹個數放入a[k]中。求解壹個組合時，輸出[]中的壹個組合。第壹個數字可以是m，m-1，...在函數將確定的組合的第壹個數字放入數組後，有兩種可能的選擇。因為組合的剩余元素沒有被移除，所以它將被遞歸地確定。或者因為已經確定了組合的所有元素，所以輸出該組合。詳見下面程序中的函數梳。
程序
#包括
#定義MAXN 100
int a[MAXN]；
空梳(整數m，整數k)
{ int i，j；
for(I = m；我& gt= k；我-)
{ a[k]= I；
if(k & gt；1)
梳子(i-1，k-1)；
其他
{ for(j = a[0]；j & gt0;j -)
printf("%4d "，a[j])；
printf(" \ n ")；
}
}
}
void main()
{ a[0]= 3；
梳子(5，3)；
}
背包問題
問題描述:有n個不同值和權重的項目，求這n個項目中部分項目的選擇方案，使所選項目的總權重不超過規定的極限權重，但所選項目的值之和最大。
設n項的權重分別為w0，w1，…，wn-1，項的值分別為v0，v1，…，vn-1。采用遞歸搜索條目的選擇方案。假設備選方案有很多，總值最大的方案保存在數組option[]中，這個方案的總值保存在變量maxv中。目前正在考察壹個新的方案，其項目選擇保存在數組cop[]中。假設當前方案已經考慮了第i-1項，現在應該考慮第I項；當前方案中已經包含的項目權重之和為TW；到目前為止，如果其他項目都可以選擇的話，這個方案所能達到的總價值的期望值就是電視。在算法中引入tv時，壹旦當前方案總值的期望值小於上壹個方案總值，那麽繼續考察當前方案就變得沒有意義，因此應該終止當前方案，立即考察下壹個方案。因為當方案的總值不大於maxv時，就不會再檢查該方案，這也保證了函數後找到的方案會優於之前的方案。
對於第I條的選擇有兩種可能性:
(1)考慮到第壹項被選中，這種可能性只有在不超過方案總重量限制的情況下才是可行的。選擇完成後，繼續遞歸考慮其他項的選擇。
(2)考慮I項未被選中，這種可能性只有在沒有I項的情況下有可能找到更有價值的方案時才有..
按照上面的思路寫遞歸算法如下:
Try(第壹項，當前選擇達到的權重之和，以及該方案可能的總值tv)
{/*考慮第壹項被納入當前方案的可能性*/
如果(包括第壹項是可以接受的)
{在當前方案中包含項目I；
如果(我
試試(i+1，tw+文章I的重量，TV)；
其他
/*另壹個完整的方案，因為它比前壹個方案更好，而且是最佳方案*/
將當前方案保存為臨時最佳方案；
恢復項目I不包含的狀態；
}
/*考慮第壹項不包括在當前方案中的可能性*/
如果(排除第壹項只能考慮男性)
如果(我
Try(i+1，tw，tv-第I項的值)；
其他
/*另壹個完整的方案，因為它比前壹個方案更好，而且是最佳方案*/
將當前方案保存為臨時最佳方案；
}
為了理解上述算法，下面給出幾個例子。有四個項目，它們的權重和值如表所示:
項目0 1 2 3
重量5 3 2 1
數值4 4 3 1
並將限制重量設置為7。然後根據上面的算法，下圖是求解過程。從圖中可以看出，壹旦找到壹個解，算法會進壹步找到壹個更好的。如果可以確定壹個搜索分支不會找到更好的解，則算法不會繼續在該分支中搜索，而是立即終止該分支並調查下壹個分支。
根據上述算法編寫的函數和程序如下:
程序
#包括
#定義編號100
雙limitW，totV，maxV
int option[N]，COP[N]；
struct {雙倍權重；
雙值；
} a[N]；
int n；
void find(int i，double tw，double tv)
{ int k；
/*考慮第壹項被納入現行方案的可能性*/
if(tw+a . weight & lt；=limitW)
{ COP = 1；
如果(我
其他
{ for(k = 0；k
option[k]= COP[k]；
maxv =電視；
}
COP = 0；
}
/*考慮第壹項不包括在當前方案中的可能性*/
if(TV-a . value & gt；maxV)
如果(我
其他
{ for(k = 0；k
option[k]= COP[k]；
maxv = TV-a . value；
}
}
void main()
{ int k；
雙w，v；
Printf("輸入項目數\ n ")；
scanf(("%d "，& ampn)；
Printf("輸入每件物品的重量和價值\ n ")；
for (totv=0.0，k = 0；k
{ scanf("%1f%1f "，& ampw & amp；五)；
a[k]。重量= w；
a[k]。值= v；
totV+= V；
}
Printf("輸入限制重量\ n ")；
scanf("%1f "，& amplimitV)；
maxv = 0.0
for(k = 0；k find(0，0.0，totV)；
for(k = 0；k
if (option[k]) printf("%4d "，k+1)；
printf(" \ n總值為% .2f \ n "，maxv)；
}
作為對比，我們將以同樣的解題思路來考慮非遞歸的程序解法。為了提高尋找解的速度，程序並不是簡單地逐個生成所有的候選解，而是從每壹項對候選解的影響中形成壹個值得進壹步考慮的候選解。通過依次檢查每個項目，形成候選解決方案。對第壹條的考察有幾種情況:當該條被納入候選方案且仍滿足方案總重量限制時，如果被納入候選方案則應繼續考慮；相反，該項目不應包含在當前正在形成的候選解決方案中。同樣，只有當某項不包含在候選解中，並且有可能找到比當前臨時最優解更好的候選解時，才會認為該項不包含在候選解中；另壹方面，該項目不包括在當前候選方案中的方案不應被進壹步考慮。對於任何值得進壹步考慮的方案，程序將進壹步考慮下壹項。
程序
#包括
#定義編號100
雙重限制w；
int COP[N]；
結構元素{雙倍重量；
雙值；
} a[N]；
int k，n；
struct { int
雙tw；
雙電視；
} twv[N]；
下壹個無效(int i，double tw，double tv)
{ twv。=1;
twv.tw = tw
twv.tv = tv
}
雙查找(struct ele *a，int n)
{ int i，k，f；
雙maxv，tw，tv，totv
maxv = 0；
for (totv=0.0，k = 0；k
totv+=a[k]。價值；
下壹個(0，0.0，totv)；
I = 0；
while(I & gt；=0)
{ f=twv。；
tw = twv . tw；
TV = twv . TV；
開關(f)
{案例1: twv。++;
if(tw+a . weight & lt；=limitW)
如果(我
{下壹個(i+1，tw+a.weight，TV)；
i++；
}
其他
{ maxv = tv
for(k = 0；k
cop[k]=twv[k]。！=0;
}
打破；
案例0:I-；
打破；
默認:twv。=0;
if(TV-a . value & gt；maxv)
如果(我
{ next(i+1，tw，TV-a . value)；
i++；
}
其他
{ maxv = TV-a . value；
for(k = 0；k
cop[k]=twv[k]。！=0;
}
打破；
}
}
返回maxv
}
void main()
{ double maxv
Printf("輸入項目數\ n ")；
scanf(("%d "，& ampn)；
Printf("輸入限制重量\ n ")；
scanf("%1f "，& amplimitW)；
Printf("輸入每件物品的重量和價值\ n ")；
for(k = 0；k
scanf("%1f%1f "，& ampa[k]。重量& ampa[k]。值)；
maxv=find(a，n)；
printf(" \ n所選項目是\ n ")；
for(k = 0；k
if (option[k]) printf("%4d "，k+1)；
printf(" \ n總值為% .2f \ n "，maxv)；
}
遞歸的基本概念和特征
程序調用自身的編程技巧叫做遞歸。
過程或函數在其定義或描述中直接或間接調用自己的方法。它通常將壹個大而復雜的問題轉化為壹個與原問題相似的小問題來解決。遞歸策略可以用很少的程序描述解題過程中所需的重復計算，大大減少了程序的代碼量。遞歸的能力在於用有限的語句定義無限的對象集合。用遞歸思想編寫的程序往往非常簡潔易懂。
壹般來說，遞歸需要邊界條件，遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸推進；當滿足邊界條件時，它遞歸返回。
註意:
(1)遞歸是在過程或函數中調用自身；
(2)使用增量歸約策略時，必須有明確的遞歸結束條件，稱為遞歸退出。