3.2.2程序實現(xiàn)

1、用窮舉法解決問題宜昌市外國語高中丁玲教科版算法與程序設計2019-6-06一、情境導入溫馨提示：請尊重和保護他人信息安全。請大家設定一個三位整數(shù)密碼。（范圍：000-999）一、情境導入計算機是如何做到的呢？“一個一個去嘗試”嘗試的數(shù)字=實際密碼破解成功逐一驗證二、講解概念1、窮舉法的定義： 窮舉法又叫枚舉法、列舉法，是將求解對象一一列舉出來，然后逐一加以分析、處理，并驗證結果是否滿足給定的條件，窮舉完所有對象，問題將最終得以解決的方法。二、講解概念2、窮舉法解決問題的要素： 1、明確窮舉對象和范圍2、設計檢測條件、驗證規(guī)則三、在生活中應用忘記門鑰匙后，只能一把一把去嘗試。找不到東西了，把可能

2、的地方都找一遍問題描述：100塊買100只雞，其中公雞5元一只，母雞3元一只，小雞1元三只，一共有多少種買法？我國古代數(shù)學家張邱建在“算經(jīng)”里提出一個數(shù)學史上有名的百雞問題：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，問雞翁、母、雛各幾何？三、在數(shù)學中應用數(shù)學思維解決問題：設未知數(shù)、列方程組、求解。x+y+z=1005x+3y+z/3 =100？1、窮舉對象：2、窮舉范圍：3、驗證條件：分析問題公雞a、母雞b、小雞c0公雞a1000母雞b1000小雞c100a+b+c=1005a+3b+c/3 =100三、編程實現(xiàn)百錢百雞問題算法設計三、編程實現(xiàn)百錢百雞問題1、自然語言：2、流

3、程圖： 3、偽代碼：算法的描述方法：Step1:設定a為公雞，b為母雞，c為小雞；Step2:當a,b,c的取值范圍在0-100之 間時，執(zhí)行第三步；Step3:如果滿足條件a+b+c=100和 5a+3b+c/3=100時，輸出a,b,c；否則轉入第二步；Step4:查找完成，結束程序。算法設計三、編程實現(xiàn)百錢百雞問題1、自然語言：2、流程圖： 3、偽代碼：算法的描述方法：程序設計Dim a,b,c as integerFor a=_ to_ For b=_ to_ For c=_ to_ If_and_ then Print“公雞數(shù)量為：” & a Print“母雞數(shù)量為：”& b Pri

4、nt“小雞數(shù)量為：”& c End if Next c Next bNext a三、編程實現(xiàn)百錢百雞問題a+b+c=1005*a+3*b+c/3=100算法優(yōu)化三、編程實現(xiàn)百錢百雞問題1、時間效率：執(zhí)行程序的計算工作量。2、空間效率：執(zhí)行程序占用的內存空間。100-a-b算法優(yōu)化For a=_ to_ For b=_ to_ For c=_ to_010001001000For a=_ to_ For b=_ to_ c=_01000100For a=_ to_ For b=_ to_ c=100-a-b020033運行次數(shù)=101*101*101=1030301運行次數(shù)=101*101=10

5、201運行次數(shù)=21*34=7141、減少循環(huán)嵌套2、縮小窮舉范圍三、編程實現(xiàn)百錢百雞問題三、編程實現(xiàn)百錢百雞問題窮舉法解決問題的一般過程：分析問題確定窮舉對象、范圍和驗證條件設計算法程序設計四、遷移應用水仙花數(shù)問題1、界面設計：利用VB設計如下界面。二、分析問題四、編寫代碼一、設計界面三、設計算法設計參考水仙花數(shù)： 一個三位數(shù)，它的各位數(shù)的立方之和正好等于該數(shù)本身。如： 153=1+5+3四、遷移應用水仙花數(shù)問題1、界面設計：利用VB設計如下界面。二、分析問題四、編寫代碼一、設計界面三、設計算法設計參考1、窮舉范圍: 100 i 999一、設計界面四、編寫代碼二、分析問題三、設計算法2、窮舉

6、條件：該數(shù)百位數(shù)的立方+該數(shù)十位數(shù)的立方+該數(shù)個位數(shù)的立方=該數(shù) 請同學們找出所有的“水仙花數(shù)”（三位數(shù)）。如：153=1+5+3a+b+c=ia=i100b=i10 Mod10c=i Mod 10“” 表示整除“Mod” 表示取余四、遷移應用水仙花數(shù)問題四、遷移應用水仙花數(shù)問題一、設計界面四、編寫代碼三、設計算法二、分析問題描述算法的三種方法：Step1:輸入i=100； Step2:如果a+b+c=i，輸 出i，否則轉入第三步； Step3:如果i=999，將 i=i+1，否則轉入第二步； Step4:輸出結果，結束程序。 四、遷移應用水仙花數(shù)問題一、設計界面四、編寫代碼三、設計算法二、分

7、析問題輸入i=100For i=_to_ a=_ b=_ c=_ if_ then 輸出i end if i=i+1 next i100999i100i10 Mod10i Mod 10a3+b3+c3=i偽代碼輸入個、十、百位四、遷移應用水仙花數(shù)問題一、設計界面三、設計算法四、編寫代碼二、分析問題輸入i=100For i=_to_ a=_ b=_ c=_ if_ then 輸出i end ifnext i100999i100i10 Mod10i Mod 10請大家根據(jù)所寫的偽代碼，編寫程序，實現(xiàn)對三位水仙花數(shù)的查找。a3+b3+c3=i五、課堂評價請大家打開“學生資源包”-“ 隨堂檢測”中的網(wǎng)址，完成作業(yè)。/jq/10857911.aspx六、課堂小結1、掌握窮舉法的基本思想及要素2、準確寫出窮舉范圍及驗證條