《算法的概念》课件

第一章算法初步1.1.1算法的概念2022/11/22我们从小学就开头接触算法，生疏很多问题的算法。如，做四则运算要先乘除后加减，从里往外脱括弧，竖式笔算等都是算法，至于乘法口诀、珠算口诀更是算法的具体表达。广义地说，算法就是做某一件事的步骤或程序。菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。在数学中，算法通常是指依据肯定规章解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。(古代的计算工具：算筹与算盘.20世纪最宏大的制造：计算机，计算机是强大的实现各种算法的工具。)2022/11/22一、引入一个农夫带着一只狼、一头山羊和一篮蔬菜要过河，但只有一条小船。乘船时,农夫只能带一样东西。当农夫在场的时候,这三样东西相安无事，一旦农夫不在，狼会吃羊，或羊会吃菜。请设计一个方案，使农夫能安全地将这三样东西带过河。S1:农夫带羊过河;S2:农夫单独回来;S3:农夫带狼过河;S4:农夫带羊回来;S5:农夫带蔬菜过河;S6:农夫单独回来;S7:农夫带羊过河。2022/11/22S1：把九枚硬币平均分成三份，取其中两份放天平上称，假设平衡则重的在剩下的一份里，假设不平衡则在重的一份里； S2：在重的一份里取两枚放天平的两边，假设平衡则剩下的一枚就是所找的，假设不平衡则重的那枚就是所要找的。二、提出问题1、现有九枚硬币，有一枚略重，你能用天平(不用砝码)将其找出来吗？设计一种最有效的方法，解决这一问题。2022/11/222:用加减消元法解二元一次方程组

的具体步骤是什么？①+②×2，得5x=1.③解③，得

.

②-①×2，得5y＝3

.④

解④，得

.第一步，其次步，第三步，第四步，第五步，得到方程组的解为

.

15x=①②2022/11/22参照上述思路，一般地，解方程组的基本步骤是什么？②①2022/11/22第一步，①×-②×，得

.③第二步，解③

，得.

第三步，②×-①×，得

.④第四步，解④

，得.

第五步，得到方程组的解为2022/11/22依据上述分析，用加减消元法解二元一次方程组，可以分为五个步骤进展，这五个步骤就构成了解二元一次方程组的一个“算法”.我们再依据这一算法编制计算机程序，就可以让计算机来解二元一次方程组.阅读P2-32022/11/22算法通常指可以用来解决的某一类问题的步骤或程序，这些步骤或程序必需是明确的和有效的，而且能够在有限步之内完成的。三、概念一般来说，“用算法解决问题”可以利用计算机帮助完成。2022/11/22四、算法的步骤设计例1.写出交换两个大小一样的杯子中的液体(A水、B酒)的一个算法。S1：找一个大小与A一样的空杯子C。酒B空C水A2022/11/22例1.写出交换两个大小一样的杯子中的液体(A水、B酒)的一个算法。S1：找一个大小与A一样的空杯子C。S2：将A中的水倒入C中。酒B水C空A四、算法的步骤设计2022/11/22例1.写出交换两个大小一样的杯子中的液体(A水、B酒)的一个算法。S1：找一个大小与A一样的空杯子C。S2：将A中的水倒入C中。S3：将B中的酒精倒入A中。空B水C酒A四、算法的步骤设计2022/11/22例1.写出交换两个大小一样的杯子中的液体(A水、B酒)的一个算法。S1：找一个大小与A一样的空杯子C。S4：将C中的水倒入B中，完毕。S2：将A中的水倒入C中。S3：将B中的酒精倒入A中。水B空C酒A四、算法的步骤设计2022/11/222、假设要推断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是质数.2022/11/223、假设要推断35是否为质数，如何设计算法步骤？第一步，用2除35，得到余数1,所以2不能整除35.其次步，用3除35，得到余数2,所以3不能整除35.第三步，用4除35，得到余数3,所以4不能整除35.第四步，用5除35，得到余数0,所以5能整除35.第五步，所以35不是质数.2022/11/224、整数89是否为质数？假设让要推断89是否为质数，依据上述算法需要设计多少个步骤？第一步，用2除89，得到余数1,所以2不能整除89.其次步，用3除89，得到余数2,所以3不能整除89.第三步，用4除89，得到余数1,所以4不能整除89.

……第八十七步，用88除89，得到余数1,所以88不能 整除89.第八十八步，所以89是质数.这种写法不能算是一个正规算法2022/11/22思考:用2～88逐一去除89求余数，需要87个步骤，这些步骤根本是重复操作，我们可以按下面的思路改进这个算法，削减算法的步骤.〔1〕用i表示2～88中的任意一个整数，并从2开头取数；〔2〕用i除89，得到余数r.假设r=0，则89不是质数；假设r≠0，将i用i+1替代，再执行同样的操作；〔3〕这个操作始终进展到i取88为止.你能依据这个思路，设计一个“推断89是否为质数”的算法步骤吗？2022/11/22用i除89，得到余数r；令i=2；

假设r=0，则89不是质数，完毕算法；假设r≠0，将i用i+1替代；推断“i>88”是否成立？假设是，则89是质数，完毕算法；否则，返回其次步.第一步，

第四步，

第三步，

其次步，算法设计:2022/11/22一般地，推断一个大于2的整数是否为质数的算法步骤如何设计？第一步，给定一个大于2的整数n；其次步，令i=2；第三步，用i除n，得到余数r；第四步，推断“r=0”是否成立.假设是，则n 不是质数，完毕算法；否则，将i 的值增加1，仍用i表示；第五步，推断“i>(n-1)”是否成立，假设是， 则n是质数，完毕算法；否则，返回 第三步.2022/11/22S1：令f(x)=x2-2，由于f(1)<0，f(2)>0,所以设a=1,b=2。S2：令m=,推断f(m)是否为0。假设是0，则m为所求；假设否，则连续推断f(a)·f(m)大于0还是小于0。S3：假设f(a)·f(m)>0，则令a=m；否则，令b=m。S4:推断|a-b|<0.005是否成立？假设是，则a或b(或区间上任意值)为满足条件的近似根；假设否，则返回S2。实际上,上述步骤就是在求的近似值。算法设计:5、用二分法设计一个求方程的近似正根的算法，准确度0.005。2022/11/22第一步，取函数f(x)，给定准确度d.其次步，确定区间[a，b]，满足f(a)·f(b)<0.第五步，推断[a,b]的长度是否小于d或f(m)是否等于0.假设是，则m是方程的近似解；否则，返回第三步.第三步，取区间中点

.第四步，假设f(a)·f(m)<0,则含零点的区间为[a,m],否则，含零点的区间为[m，b].将新得到的含零点的区间仍记为[a,b];函数f(x)的图象是一条连续不断的曲线，用“二分法”求方程f(x)=0的近似解的常用算法设计：2022/11/22练习：P5练习：1，2.第一步，给定一个正实数r.第三步，得到圆的面积S.1、算法步骤：第二步，计算以r为半径的圆的面积.2022/11/222、算法步骤：第一步，给定一个大于1的整数n；其次步，令i=1；第三步，用i除n，得到余数r；第四步，推断“r=0”是否成立.假设是，则i是n的因数,输出i;否则，不是n的因数，第六步，推断“i>n”是否成立，假设是， 完毕算法；否则，返回第三步.第五步，使i值增加1，仍用i表示，

2022/11/22四、小结作业1.算法定义的理解：在数学中，现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必需是明确和有效的，而且能够在有限步之内完成.2.算法的要求：(1)写出的算法，必需能解决一类问题(例如解任意一个二元一次方程组)，并且能重复使用；(2)算法过程要能一步一步执行，每一步执行的操作,必需准确，不能含混不清，而且在有限步之内完成后能得出结果。2022/