第03課 算法設(shè)計(jì) 課件

對(duì)象數(shù)字關(guān)系C+C+A=C+10B+A+1=B+10B+1=AC+A=10A+1=10B+1=AA=9B=8C=1ABC未知未知未知？（5+6-3）×3=246×（5-3÷3）=246×（3×3-5）=24（6-3）×（5+3）=243×5+3+6=245×6-3-3=24怎么樣才能把所有解法都找出來(lái)呢？獲得所有可能的答案算法執(zhí)教者：要在手機(jī)聯(lián)系人里找到某個(gè)人，通常情況下，你會(huì)怎么做？w分治法（分而治之）把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或n個(gè)相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題，直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解就是子問(wèn)題的解的合并。分治法（分而治之）首字母分類查找從30張面值不等的鈔票中抽出10張，怎樣才能獲得最多的價(jià)值？貪心算法做出當(dāng)前的最優(yōu)選擇。就是通過(guò)局部的最優(yōu)選擇獲得整體的最優(yōu)選擇。每次都選擇現(xiàn)下的鈔票中面值最大的，最后拿到的就是最優(yōu)解。解析法枚舉法分治法貪心算法動(dòng)態(tài)規(guī)劃算法經(jīng)過(guò)大量的實(shí)踐，人們發(fā)現(xiàn)了算法某些共性的規(guī)律，總結(jié)了經(jīng)典的算法思想。合理地選擇經(jīng)典算法思想，可以為具體問(wèn)題的解決設(shè)計(jì)出更加精妙的算法?！半u兔同籠”問(wèn)題需要在一定范圍內(nèi)尋找正確解，可以使用枚舉法。枚舉法的思想是

，如果滿足正確解的條件就采納，否則繼續(xù)枚舉，做到不遺漏、不重復(fù)。在班級(jí)名單中查找符合條件的名字，通常我們會(huì)怎么做？認(rèn)識(shí)枚舉法一有序地嘗試每一種可能的解9○13

○

7=100填上合適的＋－×÷使得等式成立。玩24點(diǎn)游戲時(shí)在頭腦中羅列各種可能的算式在一篇文章中摘錄好詞好句用一串沒(méi)有標(biāo)記的鑰匙打開(kāi)教室的門，通常你會(huì)怎么做？認(rèn)識(shí)枚舉法一如果讓計(jì)算機(jī)通過(guò)枚舉法，從一串鑰匙中找到打開(kāi)教室對(duì)應(yīng)的那一把鑰匙，我們需要告訴計(jì)算機(jī)什么信息它才能停止查找？如果這把鑰匙能打開(kāi)教室門，就不用再往下嘗試了。正確解的判斷條件一共有幾把鑰匙【這樣，計(jì)算機(jī)就知道一共要試幾次了】確定枚舉的范圍枚舉法的關(guān)鍵否否是是是枚舉法流程圖認(rèn)識(shí)枚舉法一為什么在登錄網(wǎng)站、APP、ATM自動(dòng)柜員機(jī)時(shí)，系統(tǒng)要限制用戶輸入密碼的次數(shù)？認(rèn)識(shí)枚舉法一為什么在登錄網(wǎng)站、APP、ATM自動(dòng)柜員機(jī)時(shí)，系統(tǒng)要限制用戶輸入密碼的次數(shù)？為了保護(hù)財(cái)產(chǎn)安全，防止犯罪分子利用枚舉法的思想破解密碼。算法框架的確定二在明確枚舉法算法思想的基礎(chǔ)上，使用具體的計(jì)算模型，合理選擇控制結(jié)構(gòu)，可以得到解決具體問(wèn)題的算法框架，最終解決問(wèn)題，找到答案。雞兔同籠計(jì)算模型ji+tu=35ji×2+tu×4=940≤ji≤350≤tu≤35確定枚舉的范圍正確解的判斷條件使用循環(huán)結(jié)構(gòu)在0-35之間枚舉ji或tu。使用分支結(jié)構(gòu)判斷是否滿足正確解的條件如果……那么……重復(fù)執(zhí)行……兔的只數(shù)（tu）雞的只數(shù)（ji）總腳數(shù)是否滿足正確解條件兔的只數(shù)（tu）0123535-035-135-20≤ji≤350≤tu≤35枚舉兔的數(shù)量，完成表格的填寫(xiě)。ji+tu=35ji×2+tu×4=94確定枚舉的范圍正確解的判斷條件……12……35-1235-35…………707274……94……140×××……√××雞兔同籠算法的描述三

描述算法時(shí)，要精準(zhǔn)地描述算法的每一步驟，明確算法的輸入和輸出。對(duì)于大部分算法來(lái)說(shuō)，輸入數(shù)據(jù)是必要的，但是有的算法不需要輸入數(shù)據(jù)或者算法本身給定了初始條件。比如雞兔同籠的問(wèn)題，就可以把tu的值初始化為0，因?yàn)槭菑?開(kāi)始羅列的。枚舉兔的數(shù)量，“雞兔同籠”算法描述：1.兔子只數(shù)從0開(kāi)始羅列。2.確定枚舉范圍：兔子是在羅列范圍內(nèi)嗎？3.如果超出羅列范圍，那么結(jié)束；如果沒(méi)有超出羅列范圍，那么計(jì)算雞的數(shù)量。4.正確解的判斷條件：兔子和雞的只數(shù)符合條件嗎？5.如果符合條件，那么輸出兔子和雞的只數(shù)；6.如果不符合條件，那么羅列下一個(gè)。算法的描述三

除了枚舉兔的數(shù)量，還可以枚舉哪些數(shù)量？兔的腳數(shù)48……48……92雞的腳數(shù)（94-4）÷2（94-8）÷2……（94-48）÷2……（94-92）÷2總只數(shù)4645……35……23是否滿足正確解條件××……√……×枚舉法1.枚舉法的思想是

地嘗試

的解。2.枚舉法的關(guān)鍵是①

。