《算法的概念》PPT課件.ppt

1.1.1 算法的概念,普通高中課程標(biāo)準(zhǔn)實(shí)驗(yàn)教科書 人教A版數(shù)學(xué)必修3 第一章 算法初步,在中央電視臺(tái)幸運(yùn)52節(jié)目中,有一個(gè)猜商品價(jià)格的環(huán)節(jié),竟猜者如在規(guī)定的時(shí)間內(nèi)大體猜出某種商品的價(jià)格,就可獲得該件商品.現(xiàn)有一商品,價(jià)格在0-8000元之間,采取怎樣的策略才能在短時(shí)間內(nèi)說出正確(大體上)的答案呢?,在中央電視臺(tái)幸運(yùn)52節(jié)目中,有一個(gè)猜商品價(jià)格的環(huán)節(jié),竟猜者如在規(guī)定的時(shí)間內(nèi)大體猜出某種商品的價(jià)格,就可獲得該件商品.現(xiàn)有一商品,價(jià)格在0-8000元之間,采取怎樣的策略才能在短時(shí)間內(nèi)說出正確(大體上)的答案呢?,第一步:報(bào)“4000”；,第二步:若主持人說高了(說明答案在04000之間),就報(bào)“2000”,否則(答數(shù)在40008000之間)報(bào)“6000”；,第三步:重復(fù)第二步的報(bào)數(shù)方法取中間數(shù),直至得到正確結(jié)果.,兩個(gè)男孩和兩個(gè)女孩一起渡河，渡口只有一條小船每次只能渡1 個(gè)男孩或兩個(gè)女孩，他們四人都會(huì)劃船，但都不會(huì)游泳,試問他們?cè)鯓佣珊?？?qǐng)寫出一個(gè)渡河方案。,S1 兩個(gè)女孩同船過河；,S2 一個(gè)女孩劃船回來；,S3 一個(gè)男孩劃船過河；,S4 對(duì)岸的女孩劃船回來；,S5 兩個(gè)女孩同船渡河；,S6 一個(gè)女孩劃船回來；,S7 余下的一個(gè)男孩獨(dú)自劃船渡河；對(duì)岸的女孩劃船回來；,S8 兩個(gè)女孩再同時(shí)劃船渡河。,智力大比拼,算法的概念： 一般地, 按照一定規(guī)則解決某一類問題的明確和有限的步驟稱為算法(algorithm)。,所謂 “算法”就是解題方法的精確描述.從更廣義的角度來看,并不是只有“計(jì)算”的問題才有算法,日常生活中處處都有.如樂譜是樂隊(duì)演奏的算法,菜譜是做菜肴的算法,珠算口訣是使用算盤的算法.,它是解決某一類問題的程序或步驟.,什么是算法呢？,第一步：,第二步：,第三步：,解，得 ,將帶入得,解得,-,第二步：計(jì)算,第三步：給出運(yùn)算結(jié)果。,第一步: 取,你對(duì)以下的“算法”如何理解？,要把大象裝冰箱，分幾步？,答：分三步：,第一步：打開冰箱門,第二步：把大象裝冰箱,第三步：關(guān)上冰箱門,問：,顯然有個(gè)問題：大象可以裝進(jìn)冰箱里嗎？這個(gè)算法有效嗎？,一位商人有9枚銀元，其中有1枚略輕的是假銀元。你能用天平（不用砝碼）將假銀元找出來嗎？,解: 1.把銀元分成3組，每組3枚。,2先將兩組分別放在天平的兩邊。如果天平不平衡，那邊假銀元就放在輕的那一組；如果天平左右平衡，則假銀元就在末稱的第3組里。,3取出含假銀元的那一組，從中任取兩枚放在天平的兩邊。如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡，則末稱的那一枚就是假銀元。,演示,有人對(duì)歌德巴赫猜想“任何大于4的偶數(shù)都能寫成兩個(gè)奇質(zhì)數(shù)之和”設(shè)計(jì)了如下操作步驟：,第一步：檢驗(yàn)6=3+3,第二步：檢驗(yàn)8=3+5,。,利用計(jì)算機(jī)無窮地進(jìn)行下去！,請(qǐng)問，利用這種程序能夠證明猜想的正確性嗎？,第三步：檢驗(yàn)10=5+5,這是一種算法嗎？,2.算法的特點(diǎn): 思路簡單清晰,敘述復(fù)雜,步驟繁瑣,計(jì)算量大,完全依靠人力難以完成.而這些恰恰就是計(jì)算機(jī)的特長,它能不厭其煩地完成枯燥的、重復(fù)的繁瑣的工作. 正因?yàn)檫@些,現(xiàn)代算法的作用之一就是使計(jì)算機(jī)代替人完成某些工作,這也是我們學(xué)習(xí)算法的重要原因之一.,1.算法的特征： 確定性、有限性、有效性 、不唯一性,結(jié)論：,例1.任意給定一個(gè)大于1的整數(shù)n,試設(shè)計(jì)一個(gè)程序或步驟對(duì)n是否為質(zhì)數(shù)做出判定.（課本p3）,第一步：判斷n是否等于2.若n=2，則n是質(zhì)數(shù)；若n2，則執(zhí)行第二步.,第二步:依次從2（n1）檢驗(yàn)是不是n的因數(shù)，即整除n的數(shù),若有這樣的數(shù)，則n不是質(zhì)數(shù)；若沒有這樣的數(shù)，則n是質(zhì)數(shù).,評(píng)析:這是判斷一個(gè)大于1的整數(shù)n是否為質(zhì)數(shù)的最基本算法.,例題講解,算法1：,第二步：計(jì)算10150；,第三步：寫出運(yùn)算結(jié)果,算法2：,第一步：取n=100；,第二步：計(jì)算,第三步：寫出運(yùn)算結(jié)果,寫出求1+2+3+ +100的一個(gè)算法,(1+100)+(2+99)+ +(50+51)；,第一步：將原式變形為,你會(huì)了嗎？,現(xiàn)有有限個(gè)實(shí)數(shù)，怎樣從中找出最大值？,先假定這些實(shí)數(shù)中的第一個(gè)數(shù)為“最大值”。,將這些實(shí)數(shù)中的下一個(gè)數(shù)與“最大值”比較，如果它大于此“最大值”，這時(shí)就假定“最大值”是這個(gè)實(shí)數(shù)。,如果還有其他實(shí)數(shù)，重復(fù)第二步。,一直到?jīng)]有可比的數(shù)為止，這時(shí)假定的“最大值”就是這有限個(gè)實(shí)數(shù)的最大值。,第一步:,第二步:,第三步:,第四步:,思 考,終端框,處理框,輸入輸出框,判斷框,流程線,2、常用流程圖符號(hào),表示一個(gè)算法的起始和結(jié)束,表示一個(gè)算法輸入和輸出的信息,判斷某一條件是否成立，成立時(shí)在 出口處標(biāo)明“是”或“Y”；不成立時(shí) 標(biāo)明“否”或“N”.,賦值、計(jì)算,表示流程的路徑和方向,連接點(diǎn),連接程序框圖的兩部分,課堂小結(jié),設(shè)計(jì)算法 的注意事項(xiàng): (1)認(rèn)真分析問題,聯(lián)系解決此問題的一般數(shù)學(xué)方法; (2)綜合考慮此類問題中可能涉及的各種情況; (3)借助有關(guān)的變量或參數(shù)對(duì)算法加以表達(dá); (4)將解決問題的過程劃分為若干個(gè)步驟; (5)然后用簡練的語言將各個(gè)步驟表示出來.,1.知識(shí)結(jié)構(gòu),算法的概念,算法的步驟,算法的特點(diǎn),算法,課堂小結(jié),2.算法的特點(diǎn):思路簡單清晰,敘述復(fù)雜,步驟繁瑣,計(jì)算量大,完全依靠人力難以完成.而這些恰恰就是計(jì)算機(jī)的特長,它能不厭其煩地完成枯燥的、重復(fù)的繁瑣的工作. 正因?yàn)檫@些,現(xiàn)代算法的作用之一就是使計(jì)算機(jī)代替人完成某些工作,這也是我們學(xué)習(xí)算法的重要原因之一.,