導航:首頁 > 源碼編譯 > 梯形迭代式演算法

梯形迭代式演算法

發布時間:2024-05-23 10:06:44

❶ 什麼是迭代演算法

迭代演算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點,讓計算機對一組指令(或一定步驟)進行重復執行,在每次執行這組指令(或這些步驟)時,都從變數的原值推出它的一個新值。

利用迭代演算法解決問題,需要做好以下三個方面的工作:

一、確定迭代變數。在可以用迭代演算法解決的問題中,至少存在一個直接或間接地不斷由舊值遞推出新值的變數,這個變數就是迭代變數。

二、建立迭代關系式。所謂迭代關系式,指如何從變數的前一個值推出其下一個值的公式(或關系)。迭代關系式的建立是解決迭代問題的關鍵,通常可以使用遞推或倒推的方法來完成。

三、對迭代過程進行控制。在什麼時候結束迭代過程?這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復執行下去。迭代過程的控制通常可分為兩種情況:一種是所需的迭代次數是個確定的值,可以計算出來;另一種是所需的迭代次數無法確定。對於前一種情況,可以構建一個固定次數的循環來實現對迭代過程的控制;對於後一種情況,需要進一步分析出用來結束迭代過程的條件。

例 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

閱讀全文

與梯形迭代式演算法相關的資料

熱點內容
python選擇哪種方式的安裝 瀏覽:811
滁州市app是什麼 瀏覽:265
英雄聯盟手游國服伺服器爆滿怎麼辦 瀏覽:752
linux內存管理命令 瀏覽:710
三及大片有哪些 瀏覽:667
什麼是伺服器什麼是pc機 瀏覽:425
大學內的課用什麼app看 瀏覽:228
app安裝器停止運行怎麼辦 瀏覽:131
如何修改pdf內容 瀏覽:145
王者榮耀怎麼把ios的切到安卓 瀏覽:713
cms源碼免費版 瀏覽:43
雲伺服器如何開分機 瀏覽:448
電視劇vip免費觀看 瀏覽:108
電視tv免費影視軟體 瀏覽:275
如何查看惠普伺服器有沒做磁碟陣列 瀏覽:516
程序員賺錢的網站 瀏覽:842
日本和韓國的免費高分電影 瀏覽:829
高清電影免費觀看 瀏覽:400
韓國經典愛情電影推薦 瀏覽:207
pgptray私鑰加密 瀏覽:930