資源簡介

(共13張PPT)
第3課 算法設(shè)計
學(xué)習(xí)內(nèi)容
使用經(jīng)典算法思想進(jìn)行算法設(shè)計
探 索
解決下圖中的問題時，主要的方法與步驟是怎樣的
建 構(gòu)
經(jīng)過大量的實(shí)踐，人們發(fā)現(xiàn)了一些共性的規(guī)律，將其總結(jié)成了經(jīng)典的算法，如解析法、枚舉法等。合理選擇經(jīng)典算法，可為具體問題的解決設(shè)計出更加精妙的方法，如“雞兔同籠”問題要在一定范圍內(nèi)尋找正確解，可使用枚舉法。
一、認(rèn)識枚舉法
枚舉法的思想是有序地嘗試每一種可能的解如果滿足正確解的條件就采納，否則繼續(xù)枚舉，做到不遺漏、不重復(fù)。它在生活中有著廣泛的應(yīng)用如玩24點(diǎn)游戲時在頭腦中羅列各種可能的算式，在一篇文章中摘錄好詞好句......
使用枚舉法的關(guān)鍵是確定枚舉的范圍和正確解的判斷條件
想一想
請同學(xué)們想一想在登錄網(wǎng)站、APP或ATM機(jī)時，為什么系統(tǒng)要限制用戶輸入密碼的次數(shù)
二、算法框架的確定
在明確算法思想的基礎(chǔ)上，使用具體的計算模型，合理選擇控制結(jié)構(gòu)，可以得到解決具體問題的算法框架。在枚舉“雞兔同籠”問題的解時，使用循環(huán)結(jié)構(gòu)在0-35之間枚舉ji或tu，使用分支結(jié)構(gòu)判斷是否滿足正確解條件ji×2+tu×4=94。為了方便計算，可以只枚舉其中一種動物的只數(shù)，另一種動物的只數(shù)為35減去該動物的只數(shù)。
二、算法框架的確定
三、算法的描述
描述算法時，要精準(zhǔn)描述算法的每一步驟，明確算法的輸入、輸出。對于大部分算法來說，輸入數(shù)據(jù)是必要的，但有的算法不需要輸入數(shù)據(jù)或者算法本身給定了初始條件，如“雞兔同籠”問題中將tu的值初始化賦為0。“雞兔同籠”問題輸出的結(jié)果是雞與兔的只數(shù)，即變量ji和tu的值。最后根據(jù)設(shè)計好的算法框架，用流程圖將算法完整地描述出來。“雞兔同籠”問題的算法可描述如下:
三、算法的描述
試一試
除枚舉免的數(shù)量外，還可以枚舉哪些數(shù)量
練 習(xí)
利用枚舉法設(shè)計“百錢買百雞”問題的算法，并用流程圖描述。
謝謝！

展開更多......

收起↑