李景囡算法的基本思想

《李景囡算法的基本思想》由会员分享，可在线阅读，更多相关《李景囡算法的基本思想（36页珍藏版）》请在装配图网上搜索。

1、学生：高一一班教师：李景囡歌曲春暖花开的制作步骤：1.梁芒先生作词2.著名作曲家洪兵老先生作曲3.制成歌谱4.由歌手演唱 1.请欣赏小品请欣赏小品“钟点工钟点工”片段片段. 1.请欣赏小品请欣赏小品“钟点工钟点工”片段片段.2.回答回答问题问题 ：要把大象装冰箱，分几步？：要把大象装冰箱，分几步？答：分三步：答：分三步：第一步：打开冰箱门第一步：打开冰箱门第二步：把大象装冰箱第二步：把大象装冰箱第三步：关上冰箱门第三步：关上冰箱门 一个一个农夫农夫带着一只带着一只狼狼、一头、一头 羊羊和一篮和一篮蔬菜蔬菜要过河要过河,但只有一但只有一 条小船条小船.乘船时乘船时,农夫只能带一样农夫只能带一样

2、东西东西.当农夫在场的时候当农夫在场的时候,这三样这三样 东西相安无事东西相安无事.一旦农夫不在一旦农夫不在,狼狼 会吃羊会吃羊,羊会吃菜羊会吃菜.请设计一个方请设计一个方 案案,使农夫能安全地将这三样东使农夫能安全地将这三样东 西带过河西带过河. 算法算法(algorithm)(algorithm)一词源于算术一词源于算术(algorism)(algorism)，即算术方法，即算术方法，是指一个由已知推求未知的运算过程。后来，人们把它推广到一般，是指一个由已知推求未知的运算过程。后来，人们把它推广到一般，把进行某一工作的方法和步骤称为算法。把进行某一工作的方法和步骤称为算法。 广义地说，算法

3、就是做某一件事的步骤或程序。广义地说，算法就是做某一件事的步骤或程序。 菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。在数学中，主要研究计算机能实的算法，歌谱是一首歌曲的算法。在数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问题现的算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。比如解方程的算法、函数求值的算法、作图的算法，等等的程序。比如解方程的算法、函数求值的算法、作图的算法，等等。 算法：算法：在数学中，算法通常是指按照一定规则来在数学中，算法通常是指按照一

4、定规则来解决某一类问题的明确和有限的步骤。解决某一类问题的明确和有限的步骤。你能举几个现实生活中或数学中算法的例子吗？请举例说明.例例1.1.我国南宋数学家杨辉在我国南宋数学家杨辉在12751275年提出的一个问年提出的一个问 题：题：“直田积直田积( (矩形面积矩形面积) )八百六十四步八百六十四步( (平方平方 步步) )，阔不及长一十二步，阔不及长一十二步( (宽比长少一十二宽比长少一十二 步步) )，问阔及长各几步，问阔及长各几步” ：矩形的阔：矩形的阔( (宽宽) )为为2424步，长为步，长为3636步步 阔阔( (宽宽) )为为x x步，则长为步，则长为(x+12)(x+12)步

5、步 出方程出方程(12)864x x 这个方程，得这个方程，得12,xx 设设列列解解答答解：解：第一步第一步. .第二步第二步. .第三步第三步. .第四步第四步. . 24 -36（舍）22.0 (0)axbxca例 求一元二次方程的根的值第一步：计算acb42，则方程无实根。如果，则方程有解第二步：如果0;202, 1abx练习练习1.1.现有九枚硬币，有一枚略轻，你能用天平现有九枚硬币，有一枚略轻，你能用天平( (不用砝不用砝 码码) )将其找出来吗？设计一种算法，解决这将其找出来吗？设计一种算法，解决这一问题一问题. .第一步第一步. .将将9 9枚硬币平均分成三组枚硬币平均分成三组

6、; ;第二步第二步. .任取其中两组放在天平的两边任取其中两组放在天平的两边. . 如果天平平如果天平平 衡衡, , 则轻的硬币必定在未称的一组则轻的硬币必定在未称的一组; ;否则否则, ,轻轻 的硬币必定在较轻的一组的硬币必定在较轻的一组; ;第三步第三步. .将有较轻的一组硬币中将有较轻的一组硬币中, ,取出两枚硬币，分别取出两枚硬币，分别 放在天平的两边放在天平的两边. .如果天平平衡如果天平平衡, ,则较轻的硬则较轻的硬 币必定是剩余的币必定是剩余的; ;否则否则, ,轻的硬币必定在较轻轻的硬币必定在较轻 的一边的一边. .第一步，用第一步，用2 2除除7 7，得余数，得余数1 1。因

7、为余数不为。因为余数不为0 0，所以所以2 2不能整除不能整除7 7。第二步，第二步，用用3 3除除7 7，得余数，得余数1 1。因为余数不为。因为余数不为0 0，所以所以3 3不能整除不能整除7 7。第三步，第三步，用用4 4除除7 7，得余数，得余数2 2。因为余数不为。因为余数不为0 0，所，所以以4 4不能整除不能整除7 7。第四步，第四步，用用5 5除除7 7，得余数，得余数2 2。因为余数不为。因为余数不为0 0，所，所以以5 5不能整除不能整除7 7。第五步，第五步，用用6 6除除7 7，得余数，得余数1 1。因为余数不为。因为余数不为0 0，所以所以6 6不能整除不能整除7.7

8、.因此，因此，7 7是质数。是质数。练习练习2.2.练习练习3 3：在给定素数表的条件下，请你设计一个算法，：在给定素数表的条件下，请你设计一个算法，将将936936分成素因数的乘积分成素因数的乘积. . 解解: :算法步骤如下：算法步骤如下： 判断判断936936是否为素数：否。是否为素数：否。 确定确定936936的最小素因数：的最小素因数：2 2。 936=2936=2468468 判断判断468468是否为素数：否。是否为素数：否。 确定确定468468的最小素因数：的最小素因数：2 2。 936=2936=22 2234234 判断判断234234是否为素数：否。是否为素数：否。 确

9、定确定234234的最小素因数：的最小素因数：2 2。 936=2936=22 22 2117117 判断判断117117是否为素数：否。是否为素数：否。 确定确定117117的最小素因数：的最小素因数：3 3。 936=2936=22 22 23 33939 判断判断3939是否为素数：否。是否为素数：否。 确定确定3939的最小素因数：的最小素因数：3 3。 936=2936=22 22 23 33 31313 判断判断13 13 是否为素数：是否为素数：1313是素数，所以分解结束。是素数，所以分解结束。 分解结果是：分解结果是： 936=2223313练习练习4. 4. 写出求写出求1

10、 12 23 34 45 56 6的一个算法的一个算法解算法解算法1：1计算计算12得到得到3；2将第将第1步中的运算结果步中的运算结果3与与3相加得到相加得到6；3将第将第2步中的运算结果步中的运算结果6与与4相加得到相加得到10；4将第将第3步中的运算结果步中的运算结果10与与5相加得到相加得到15；5将第将第4步中的运算结果步中的运算结果15与与6相加得到相加得到21；算法算法2：1取取n6；2计算计算 ；3输出运算结果输出运算结果算法的五个重要特征算法的五个重要特征（1 1）确定性：算法的每一步必须是确切定义的，确定性：算法的每一步必须是确切定义的，且无二义性，算法只有唯一的一条执行路

11、径，对且无二义性，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出于相同的输入只能得出相同的输出（2 2）可行性：算法中的每一个步骤必须能用实现可行性：算法中的每一个步骤必须能用实现算法的工具算法的工具可执行指令精确表达，并在有限可执行指令精确表达，并在有限步骤内完成，否则这种算法也是不会被采纳的步骤内完成，否则这种算法也是不会被采纳的（3 3）有穷性：必须在有限个步骤内完成，不能无）有穷性：必须在有限个步骤内完成，不能无休止地执行下去休止地执行下去. .（4 4）不唯一性：算法不一定是唯一的，可以有不）不唯一性：算法不一定是唯一的，可以有不同的算法同的算法. .（5 5）普遍性：

12、同一类问题，可以用同一算法去解）普遍性：同一类问题，可以用同一算法去解决决. .确定性确定性可行可行性性有穷性有穷性 不惟一性不惟一性 普遍性普遍性例：例：对算法的理解不正确的是对算法的理解不正确的是()A一个算法包含的步骤是有限的一个算法包含的步骤是有限的B一个算法中每一步都是明确可操作的，而不是模一个算法中每一步都是明确可操作的，而不是模棱两可的棱两可的C算法在执行后，结果应是明确的算法在执行后，结果应是明确的D一个问题只可以有一个算法一个问题只可以有一个算法【解析】由算法的不唯一性可知【解析】由算法的不唯一性可知D错错【答案】【答案】D今有物不知数，三三数之剩二，五五数之剩三，七七数之剩

13、四，问物几何？孙子算经 翻译：一个数除以3余2，除以5余3，除以7余4，问这个数是几?算法一算法一第一步第一步 三三数之剩二三三数之剩二 ：2 2，5 5，8 8，1111，1414，1717，2020，2323，2626，2929，3232，3535，3838，4141，4141，4747，5050，5353，5656第二步第二步 五五数之剩三：五五数之剩三：3 3，8 8，1313，1818，2323，2828，3333，3838，4343，4848，5353，5858第三步第三步 七七数之剩四：七七数之剩四：4 4，1111，1818，2525，3232，3939，4646，5353，6

14、060第四步第四步 从以上三列数中找出满足条件的最小的数是从以上三列数中找出满足条件的最小的数是5353算法二算法二 1. 1. 先确定除以先确定除以3 3余余2 2的正整数的正整数2 2，5 5，8 8，1111，1414，1717，2020，2323，2626，2929，3232，3535，3838，4141，4141，4747，5050，5353，56562. 2. 在上列数中找出最小的除以在上列数中找出最小的除以5 5余余3 3的正整数：的正整数：8 83. 3. 然后依次加上然后依次加上1515得到：得到：8 8，2323，3838，53.53.（这些数既满足除（这些数既满足除以以3

15、 3余余2 2，又满足除以，又满足除以5 5余余3 3）4. 4. 在上述数列中找出最小的满足除以在上述数列中找出最小的满足除以7 7余余4 4的数的数5353一、算法的概念一、算法的概念二、算法的特征二、算法的特征三、会写出简单的算法步骤三、会写出简单的算法步骤算法设计的要求(1)写出的算法必须能够解决一类问题，并且能够重复使用(2)要使算法尽量简单，步骤尽量少(3)要保证算法正确，且算法步骤能够一步一步执行，每一步执行的操作必须确切，不能含混不清，而且在有限步后能得到结果.22.430 xx写出解的两种不同的算法。1. 回回家家给给自自己己的的家家人人做做道道西西红红柿柿炒炒鸡鸡蛋蛋，并并用用算算 法法语语言言写写出出如如何何做做这这道道菜菜。3. 有一把围棋子，5个5个地数，最后余下2个；7 个 7个地数，最后余下3个；9个9个地数，最后余下 4个，请设计一种算法，求出这把棋子至少有多少 个？感 谢 聆 听