《算法的概念》教程文件.ppt

《《算法的概念》教程文件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法的概念》一、引入一个农夫带着一只狼、一头山羊和一篮蔬菜要过河，但只有一条小船。乘船时,农夫只能带一样东西。当农夫在场的时候,这三样东西相安无事，一旦农夫不在，狼会吃羊，或羊会吃菜。请设计一个方案，使农夫能安全地将这三样东西带过河。S1:农夫带羊过河;S2:农夫独自回来;S3:农夫带狼过河;S4:农夫带羊回来;S5:农夫带蔬菜过河;S6:农夫独自回来;S7:农夫带羊过河。2021/9/15S1：把九枚硬币平均分成三份，取其中两份放天平上称，若平衡则重的在剩下的一份里，若不平衡则在重的一份里；S2：在重的一份里取两枚放天平的两边，若平衡则剩下的一枚就是所找

2、的，若不平衡则重的那枚就是所要找的。二、提出问题1、现有九枚硬币，有一枚略重，你能用天平(不用砝码)将其找出来吗？设计一种最有效的方法，解决这一问题。2021/9/152:用加减消元法解二元一次方程组的具体步骤是什么？①+②×2，得5x=1.③解③，得.②-①×2，得5y＝3.④解④，得.第一步，第二步，第三步，第四步，第五步，得到方程组的解为.15x=①②2021/9/15参照上述思路，一般地，解方程组的基本步骤是什么？②①2021/9/15第一步，①×-②×，得.③第二步，解③，得.第三步，②×-①×，得.④第四步，解④，得.第五步，得到方程组的解为20

3、21/9/15根据上述分析，用加减消元法解二元一次方程组，可以分为五个步骤进行，这五个步骤就构成了解二元一次方程组的一个“算法”.我们再根据这一算法编制计算机程序，就可以让计算机来解二元一次方程组.阅读P2-32021/9/15算法通常指可以用来解决的某一类问题的步骤或程序，这些步骤或程序必须是明确的和有效的，而且能够在有限步之内完成的。三、概念一般来说，“用算法解决问题”可以利用计算机帮助完成。2021/9/15四、算法的步骤设计例1.写出交换两个大小相同的杯子中的液体(A水、B酒)的一个算法。S1：找一个大小与A相同的空杯子C。酒B空C水A2021/9/

4、15例1.写出交换两个大小相同的杯子中的液体(A水、B酒)的一个算法。S1：找一个大小与A相同的空杯子C。S2：将A中的水倒入C中。酒B水C空A四、算法的步骤设计2021/9/15例1.写出交换两个大小相同的杯子中的液体(A水、B酒)的一个算法。S1：找一个大小与A相同的空杯子C。S2：将A中的水倒入C中。S3：将B中的酒精倒入A中。空B水C酒A四、算法的步骤设计2021/9/15例1.写出交换两个大小相同的杯子中的液体(A水、B酒)的一个算法。S1：找一个大小与A相同的空杯子C。S4：将C中的水倒入B中，结束。S2：将A中的水倒入C中。S3：将B中的酒精倒

5、入A中。水B空C酒A四、算法的步骤设计2021/9/152、如果要判断7是否为质数，如何设计算法步骤？第一步，用2除7，得到余数1,所以2不能整除7.第四步，用5除7，得到余数2,所以5不能整除7.第五步，用6除7，得到余数1,所以6不能整除7.第二步，用3除7，得到余数1,所以3不能整除7.第三步，用4除7，得到余数3,所以4不能整除7.第六步，所以7是质数.2021/9/153、如果要判断35是否为质数，如何设计算法步骤？第一步，用2除35，得到余数1,所以2不能整除35.第二步，用3除35，得到余数2,所以3不能整除35.第三步，用4除35，得到余数3

6、,所以4不能整除35.第四步，用5除35，得到余数0,所以5能整除35.第五步，所以35不是质数.2021/9/154、整数89是否为质数？如果让要判断89是否为质数，按照上述算法需要设计多少个步骤？第一步，用2除89，得到余数1,所以2不能整除89.第二步，用3除89，得到余数2,所以3不能整除89.第三步，用4除89，得到余数1,所以4不能整除89.……………………第八十七步，用88除89，得到余数1,所以88不能整除89.第八十八步，所以89是质数.这种写法不能算是一个正规算法2021/9/15思考:用2～88逐一去除89求余数，需要87个步骤，这些步

7、骤基本是重复操作，我们可以按下面的思路改进这个算法，减少算法的步骤.（1）用i表示2～88中的任意一个整数，并从2开始取数；（2）用i除89，得到余数r.若r=0，则89不是质数；若r≠0，将i用i+1替代，再执行同样的操作；（3）这个操作一直进行到i取88为止.你能按照这个思路，设计一个“判断89是否为质数”的算法步骤吗？2021/9/15用i除89，得到余数r；令i=2；若r=0，则89不是质数，结束算法；若r≠0，将i用i+1替代；判断“i>88”是否成立？若是，则89是质数，结束算法；否则，返回第二步.第一步，第四步，第三步，第二步，算法设计:202

8、1/9/15一般地，判断一个大于2的整数是否为质数的