迭代算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）進行重復執行，在每次執行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。 利用迭代算法解決問題，需要做好以下三個方面的工作： 一、確定迭代變量。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。 二、建立迭代關系式。所謂迭代關系式，指如何從變量的前一個值推出其下一個值的公式（或關系）。迭代關系式的建立是解決迭代問題的要害，通常可以使用遞推或倒推的方法來完成。 三、對迭代過程進行控制。在什么時候結束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復執行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定。對于前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對于后一種情況，需要進一步分析出用來結束迭代過程的條件。 例 1 ： 一個飼養場引進一只剛出生的新品種兔子，這種兔子從出生的下一個月開始，每月新生一只兔子，新生的兔子也如此繁殖。假如所有的兔子都不死去，問到第 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 for i=2 to 12 y=x*2 x=y next i PRint y end 例 2 ： 阿米巴用簡單分裂的方式繁殖，它每分裂一次要用 3 分鐘。將若干個阿米巴放在一個盛滿營養參液的容器內， 45 分鐘后容器內布滿了阿米巴。已知容器最多可以裝阿米巴 2 20 個。試問，開始的時候往容器內放了多少個阿米巴？請編程序算出。 分析： 根據題意，阿米巴每 3 分鐘分裂一次，那么從開始的時候將阿米巴放入容器里面，到 45 分鐘后布滿容器，需要分裂 45/3=15 次。而“容器最多可以裝阿米巴 2 20 個”，即阿米巴分裂 15 次以后得到的個數是 2 20 。題目要求我們計算分裂之前的阿米巴數，不妨使用倒推的方法，從第 15 次分裂之后的 2 20 個，倒推出第 15 次分裂之前（即第 14 次分裂之后）的個數，再進一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的個數。 設第 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 15 是已知的，假如定義迭代變量為 x ，則可以將上面的倒推公式轉換成如下的迭代公式： x=x/2 （ x 的初值為第 15 次分裂之后的個數 2 20 ） 讓這個迭代公式重復執行 15 次，就可以倒推出第 1 次分裂之前的阿米巴個數。因為所需的迭代次數是個確定的值，我們可以使用一個固定次數的循環來實現對迭代過程的控制。參考程序如下： cls x=2^20 for i=1 to 15 x=x/2 next i print x end 例 3 ： 驗證谷角猜想。日本數學家谷角靜夫在研究自然數時發現了一個希奇現象：對于任意一個自然數 n ，若 n 為偶數，則將其除以 2 ；若 n 為奇數，則將其乘以 3 ，然后再加 1 。如此經過有限次運算后，總可以得到自然數 1 。人們把谷角靜夫的這一發現叫做“谷角猜想”。 要求：編寫一個程序，由鍵盤輸入一個自然數 n ，把 n 經過有限次運算后，最終變成自然數 1 的全過程打印出來。 分析： 定義迭代變量為 n ，按照谷角猜想的內容，可以得到兩種情況下的迭代關系式：當 n 為偶數時， n=n/2 ；當 n 為奇數時， n=n*3+1 。用 QBASIC 語言把它描述出來就是： if n 為偶數 then n=n/2 else n=n*3+1 end if 這就是需要計算機重復執行的迭代過程。這個迭代過程需要重復執行多少次，才能使迭代變量 n 最終變成自然數 1 ，這是我們無法計算出來的。因此，還需進一步確定用來結束迭代過程的條件。仔細分析題目要求，不難看出，對任意給定的一個自然數 n ，只要經過有限次運算后，能夠得到自然數 1 ，就已經完成了驗證工作。因此，用來結束迭代過程的條件可以定義為： n=1 。參考程序如下： cls input "Please input n=";n do until n=1 if n mod 2=0 then rem 假如 n 為偶數，則調用迭代公式 n=n/2 n=n/2 print "—";n; else n=n*3+1 print "—";n; end if loop end
