李景囡算法的基本思想

1、學(xué)生：高一一班教師：李景囡歌曲春暖花開的制作步驟：1.梁芒先生作詞2.著名作曲家洪兵老先生作曲3.制成歌譜4.由歌手演唱 1.請欣賞小品請欣賞小品“鐘點(diǎn)工鐘點(diǎn)工”片段片段. 1.請欣賞小品請欣賞小品“鐘點(diǎn)工鐘點(diǎn)工”片段片段.2.回答回答問題問題 ：要把大象裝冰箱，分幾步？：要把大象裝冰箱，分幾步？答：分三步：答：分三步：第一步：打開冰箱門第一步：打開冰箱門第二步：把大象裝冰箱第二步：把大象裝冰箱第三步：關(guān)上冰箱門第三步：關(guān)上冰箱門 一個一個農(nóng)夫農(nóng)夫帶著一只帶著一只狼狼、一頭、一頭 羊羊和一籃和一籃蔬菜蔬菜要過河要過河,但只有一但只有一 條小船條小船.乘船時乘船時,農(nóng)夫只能帶一樣農(nóng)夫只能帶一樣

2、東西東西.當(dāng)農(nóng)夫在場的時候當(dāng)農(nóng)夫在場的時候,這三樣這三樣 東西相安無事東西相安無事.一旦農(nóng)夫不在一旦農(nóng)夫不在,狼狼 會吃羊會吃羊,羊會吃菜羊會吃菜.請設(shè)計一個方請設(shè)計一個方 案案,使農(nóng)夫能安全地將這三樣?xùn)|使農(nóng)夫能安全地將這三樣?xùn)| 西帶過河西帶過河. 算法算法(algorithm)(algorithm)一詞源于算術(shù)一詞源于算術(shù)(algorism)(algorism)，即算術(shù)方法，即算術(shù)方法，是指一個由已知推求未知的運(yùn)算過程。后來，人們把它推廣到一般，是指一個由已知推求未知的運(yùn)算過程。后來，人們把它推廣到一般，把進(jìn)行某一工作的方法和步驟稱為算法。把進(jìn)行某一工作的方法和步驟稱為算法。 廣義地說，算法

3、就是做某一件事的步驟或程序。廣義地說，算法就是做某一件事的步驟或程序。 菜譜是做菜肴的算法，洗衣機(jī)的使用說明書是操作洗衣機(jī)菜譜是做菜肴的算法，洗衣機(jī)的使用說明書是操作洗衣機(jī)的算法，歌譜是一首歌曲的算法。在數(shù)學(xué)中，主要研究計算機(jī)能實(shí)的算法，歌譜是一首歌曲的算法。在數(shù)學(xué)中，主要研究計算機(jī)能實(shí)現(xiàn)的算法，即按照某種機(jī)械程序步驟一定可以得到結(jié)果的解決問題現(xiàn)的算法，即按照某種機(jī)械程序步驟一定可以得到結(jié)果的解決問題的程序。比如解方程的算法、函數(shù)求值的算法、作圖的算法，等等的程序。比如解方程的算法、函數(shù)求值的算法、作圖的算法，等等。 算法：算法：在數(shù)學(xué)中，算法通常是指按照一定規(guī)則來在數(shù)學(xué)中，算法通常是指按照一

4、定規(guī)則來解決某一類問題的明確和有限的步驟。解決某一類問題的明確和有限的步驟。你能舉幾個現(xiàn)實(shí)生活中或數(shù)學(xué)中算法的例子嗎？請舉例說明.例例1.1.我國南宋數(shù)學(xué)家楊輝在我國南宋數(shù)學(xué)家楊輝在12751275年提出的一個問年提出的一個問 題：題：“直田積直田積( (矩形面積矩形面積) )八百六十四步八百六十四步( (平方平方 步步) )，闊不及長一十二步，闊不及長一十二步( (寬比長少一十二寬比長少一十二 步步) )，問闊及長各幾步，問闊及長各幾步” ：矩形的闊：矩形的闊( (寬寬) )為為2424步，長為步，長為3636步步 闊闊( (寬寬) )為為x x步，則長為步，則長為(x+12)(x+12)步

5、步 出方程出方程(12)864x x 這個方程，得這個方程，得12,xx 設(shè)設(shè)列列解解答答解：解：第一步第一步. .第二步第二步. .第三步第三步. .第四步第四步. . 24 -36（舍）22.0 (0)axbxca例 求一元二次方程的根的值第一步：計算acb42，則方程無實(shí)根。如果，則方程有解第二步：如果0;202, 1abx練習(xí)練習(xí)1.1.現(xiàn)有九枚硬幣，有一枚略輕，你能用天平現(xiàn)有九枚硬幣，有一枚略輕，你能用天平( (不用砝不用砝 碼碼) )將其找出來嗎？設(shè)計一種算法，解決這將其找出來嗎？設(shè)計一種算法，解決這一問題一問題. .第一步第一步. .將將9 9枚硬幣平均分成三組枚硬幣平均分成三組

6、; ;第二步第二步. .任取其中兩組放在天平的兩邊任取其中兩組放在天平的兩邊. . 如果天平平如果天平平 衡衡, , 則輕的硬幣必定在未稱的一組則輕的硬幣必定在未稱的一組; ;否則否則, ,輕輕 的硬幣必定在較輕的一組的硬幣必定在較輕的一組; ;第三步第三步. .將有較輕的一組硬幣中將有較輕的一組硬幣中, ,取出兩枚硬幣，分別取出兩枚硬幣，分別 放在天平的兩邊放在天平的兩邊. .如果天平平衡如果天平平衡, ,則較輕的硬則較輕的硬 幣必定是剩余的幣必定是剩余的; ;否則否則, ,輕的硬幣必定在較輕輕的硬幣必定在較輕 的一邊的一邊. .第一步，用第一步，用2 2除除7 7，得余數(shù)，得余數(shù)1 1。因

7、為余數(shù)不為。因?yàn)橛鄶?shù)不為0 0，所以所以2 2不能整除不能整除7 7。第二步，第二步，用用3 3除除7 7，得余數(shù)，得余數(shù)1 1。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所以所以3 3不能整除不能整除7 7。第三步，第三步，用用4 4除除7 7，得余數(shù)，得余數(shù)2 2。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所，所以以4 4不能整除不能整除7 7。第四步，第四步，用用5 5除除7 7，得余數(shù)，得余數(shù)2 2。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所，所以以5 5不能整除不能整除7 7。第五步，第五步，用用6 6除除7 7，得余數(shù)，得余數(shù)1 1。因?yàn)橛鄶?shù)不為。因?yàn)橛鄶?shù)不為0 0，所以所以6 6不能整除不能整除7.7

8、.因此，因此，7 7是質(zhì)數(shù)。是質(zhì)數(shù)。練習(xí)練習(xí)2.2.練習(xí)練習(xí)3 3：在給定素數(shù)表的條件下，請你設(shè)計一個算法，：在給定素數(shù)表的條件下，請你設(shè)計一個算法，將將936936分成素因數(shù)的乘積分成素因數(shù)的乘積. . 解解: :算法步驟如下：算法步驟如下： 判斷判斷936936是否為素數(shù)：否。是否為素數(shù)：否。 確定確定936936的最小素因數(shù)：的最小素因數(shù)：2 2。 936=2936=2468468 判斷判斷468468是否為素數(shù)：否。是否為素數(shù)：否。 確定確定468468的最小素因數(shù)：的最小素因數(shù)：2 2。 936=2936=22 2234234 判斷判斷234234是否為素數(shù)：否。是否為素數(shù)：否。 確

9、定確定234234的最小素因數(shù)：的最小素因數(shù)：2 2。 936=2936=22 22 2117117 判斷判斷117117是否為素數(shù)：否。是否為素數(shù)：否。 確定確定117117的最小素因數(shù)：的最小素因數(shù)：3 3。 936=2936=22 22 23 33939 判斷判斷3939是否為素數(shù)：否。是否為素數(shù)：否。 確定確定3939的最小素因數(shù)：的最小素因數(shù)：3 3。 936=2936=22 22 23 33 31313 判斷判斷13 13 是否為素數(shù)：是否為素數(shù)：1313是素數(shù)，所以分解結(jié)束。是素數(shù)，所以分解結(jié)束。 分解結(jié)果是：分解結(jié)果是： 936=2223313練習(xí)練習(xí)4. 4. 寫出求寫出求1

10、 12 23 34 45 56 6的一個算法的一個算法解算法解算法1：1計算計算12得到得到3；2將第將第1步中的運(yùn)算結(jié)果步中的運(yùn)算結(jié)果3與與3相加得到相加得到6；3將第將第2步中的運(yùn)算結(jié)果步中的運(yùn)算結(jié)果6與與4相加得到相加得到10；4將第將第3步中的運(yùn)算結(jié)果步中的運(yùn)算結(jié)果10與與5相加得到相加得到15；5將第將第4步中的運(yùn)算結(jié)果步中的運(yùn)算結(jié)果15與與6相加得到相加得到21；算法算法2：1取取n6；2計算計算 ；3輸出運(yùn)算結(jié)果輸出運(yùn)算結(jié)果算法的五個重要特征算法的五個重要特征（1 1）確定性：算法的每一步必須是確切定義的，確定性：算法的每一步必須是確切定義的，且無二義性，算法只有唯一的一條執(zhí)行路

11、徑，對且無二義性，算法只有唯一的一條執(zhí)行路徑，對于相同的輸入只能得出相同的輸出于相同的輸入只能得出相同的輸出（2 2）可行性：算法中的每一個步驟必須能用實(shí)現(xiàn)可行性：算法中的每一個步驟必須能用實(shí)現(xiàn)算法的工具算法的工具可執(zhí)行指令精確表達(dá)，并在有限可執(zhí)行指令精確表達(dá)，并在有限步驟內(nèi)完成，否則這種算法也是不會被采納的步驟內(nèi)完成，否則這種算法也是不會被采納的（3 3）有窮性：必須在有限個步驟內(nèi)完成，不能無）有窮性：必須在有限個步驟內(nèi)完成，不能無休止地執(zhí)行下去休止地執(zhí)行下去. .（4 4）不唯一性：算法不一定是唯一的，可以有不）不唯一性：算法不一定是唯一的，可以有不同的算法同的算法. .（5 5）普遍性：

12、同一類問題，可以用同一算法去解）普遍性：同一類問題，可以用同一算法去解決決. .確定性確定性可行可行性性有窮性有窮性 不惟一性不惟一性 普遍性普遍性例：例：對算法的理解不正確的是對算法的理解不正確的是()a一個算法包含的步驟是有限的一個算法包含的步驟是有限的b一個算法中每一步都是明確可操作的，而不是模一個算法中每一步都是明確可操作的，而不是模棱兩可的棱兩可的c算法在執(zhí)行后，結(jié)果應(yīng)是明確的算法在執(zhí)行后，結(jié)果應(yīng)是明確的d一個問題只可以有一個算法一個問題只可以有一個算法【解析】由算法的不唯一性可知【解析】由算法的不唯一性可知d錯錯【答案】【答案】d今有物不知數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩

13、四，問物幾何？孫子算經(jīng) 翻譯：一個數(shù)除以3余2，除以5余3，除以7余4，問這個數(shù)是幾?算法一算法一第一步第一步 三三數(shù)之剩二三三數(shù)之剩二 ：2 2，5 5，8 8，1111，1414，1717，2020，2323，2626，2929，3232，3535，3838，4141，4141，4747，5050，5353，5656第二步第二步 五五數(shù)之剩三：五五數(shù)之剩三：3 3，8 8，1313，1818，2323，2828，3333，3838，4343，4848，5353，5858第三步第三步 七七數(shù)之剩四：七七數(shù)之剩四：4 4，1111，1818，2525，3232，3939，4646，5353，6

14、060第四步第四步 從以上三列數(shù)中找出滿足條件的最小的數(shù)是從以上三列數(shù)中找出滿足條件的最小的數(shù)是5353算法二算法二 1. 1. 先確定除以先確定除以3 3余余2 2的正整數(shù)的正整數(shù)2 2，5 5，8 8，1111，1414，1717，2020，2323，2626，2929，3232，3535，3838，4141，4141，4747，5050，5353，56562. 2. 在上列數(shù)中找出最小的除以在上列數(shù)中找出最小的除以5 5余余3 3的正整數(shù)：的正整數(shù)：8 83. 3. 然后依次加上然后依次加上1515得到：得到：8 8，2323，3838，53.53.（這些數(shù)既滿足除（這些數(shù)既滿足除以以3 3余余2 2，又滿足除以，又滿足除以5 5余余3 3）4. 4. 在上述數(shù)列中找出最小的滿足除以在上述數(shù)列中找出最小的滿足除以7 7余余4 4的數(shù)的數(shù)5353一、算法的概念一、算法的概念二、算法的特征二、算法的特征三、會寫出簡單的算法步驟三、會寫出簡單的算法步驟算法設(shè)計的要求(1)寫出的算法必須能夠解決一類問題，并且能夠重復(fù)使用(2)要使算法盡量簡單，步驟盡量