《算法的概念》优秀PPT.ppt

第一章第一章 算法初步算法初步 1.1.1 1.1.1 算法的概念算法的概念2022/10/29 我们从小学就起先接触算法，熟悉很多问题我们从小学就起先接触算法，熟悉很多问题的算法。如，做四则运算要先乘除后加减，从里的算法。如，做四则运算要先乘除后加减，从里往外脱括弧，竖式笔算等都是算法，至于乘法口往外脱括弧，竖式笔算等都是算法，至于乘法口诀、珠算口诀更是算法的具体体现。广义地说，诀、珠算口诀更是算法的具体体现。广义地说，算法就是做某一件事的步骤或程序。菜谱是做菜算法就是做某一件事的步骤或程序。菜谱是做菜肴的算法，洗衣机的运用说明书是操作洗衣机的肴的算法，洗衣机的运用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。算法，歌谱是一首歌曲的算法。在数学中，算法通常是指依据确定规则解决某一在数学中，算法通常是指依据确定规则解决某一类问题的明确和有限的步骤。现在，算法通常可类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。以编成计算机程序，让计算机执行并解决问题。(古代的计算工具：算筹与算盘古代的计算工具：算筹与算盘.20.20世纪最宏大的世纪最宏大的独创：计算机，计算机是强大的实现各种算法的独创：计算机，计算机是强大的实现各种算法的工具。工具。)2022/10/29一、引入一、引入一个农夫带着一只狼、一头山羊和一篮蔬菜要过河，但一个农夫带着一只狼、一头山羊和一篮蔬菜要过河，但只有一条小船。乘船时只有一条小船。乘船时,农夫只能带一样东西。当农夫农夫只能带一样东西。当农夫在场的时候在场的时候,这三样东西相安无事，一旦农夫不在，狼这三样东西相安无事，一旦农夫不在，狼会吃羊，或羊会吃菜。请设计一个方案，使农夫能平安会吃羊，或羊会吃菜。请设计一个方案，使农夫能平安地将这三样东西带过河。地将这三样东西带过河。S1:S1:农夫带羊过河农夫带羊过河;S2:S2:农夫独自回来农夫独自回来;S3:S3:农夫带狼过河农夫带狼过河;S4:S4:农夫带羊回来农夫带羊回来;S5:S5:农夫带蔬菜过河农夫带蔬菜过河;S6:S6:农夫独自回来农夫独自回来;S7:S7:农夫带羊过河。农夫带羊过河。2022/10/29S1S1：把九枚硬币平均分成三份，取其中两份放：把九枚硬币平均分成三份，取其中两份放天平上称，若平衡则重的在剩下的一份里，若天平上称，若平衡则重的在剩下的一份里，若不平衡则在重的一份里；不平衡则在重的一份里；S2S2：在重的一份里取两枚放：在重的一份里取两枚放天平的两边，若平衡则剩下天平的两边，若平衡则剩下的一枚就是所找的，若不平的一枚就是所找的，若不平衡则重的那枚就是所要找的。衡则重的那枚就是所要找的。二、提出问题二、提出问题1、现有九枚硬币，有一枚略重，你能用天平、现有九枚硬币，有一枚略重，你能用天平(不用不用砝码砝码)将其找出来吗？设计一种最有效的方法，解将其找出来吗？设计一种最有效的方法，解决这一问题。决这一问题。2022/10/292:用加减消元法解二元一次方程组用加减消元法解二元一次方程组 的具体步骤是什么？的具体步骤是什么？+2+2，得，得 5x=1.5x=1.解解，得，得 .-2-2，得，得 5y5y3 3.解解，得，得 .第一步，第一步，其次步，其次步，第三步第三步，第四步，第四步，第五步，第五步，得到方程组的解为得到方程组的解为 .15x=2022/10/29参照上述思路，一般地，解方程参照上述思路，一般地，解方程组组 的基的基本步骤是什么？本步骤是什么？2022/10/29第一步第一步，-，得，得 .第二步第二步，解，解，得，得 .第三步第三步，-，得，得 .第四步第四步，解，解，得，得 .第五步第五步，得到方程组的解为，得到方程组的解为 2022/10/29依据上述分析，用加减消元法解二元一依据上述分析，用加减消元法解二元一次方程组，可以分为五个步骤进行，这次方程组，可以分为五个步骤进行，这五个步骤就构成了解二元一次方程组的五个步骤就构成了解二元一次方程组的一个一个“算法算法”.”.我们再依据这一算法编制我们再依据这一算法编制计算机程序，就可以让计算机来解二元计算机程序，就可以让计算机来解二元一次方程组一次方程组.阅读阅读P2-32022/10/29 算法通常指可以用来解决的某一类问算法通常指可以用来解决的某一类问题的步骤或程序，这些步骤或程序必需是题的步骤或程序，这些步骤或程序必需是明确的和有效的，而且能够在有限步之内明确的和有效的，而且能够在有限步之内完成的。完成的。三、概念三、概念 一般来说，一般来说，“用算法解决问题用算法解决问题”可以利用计可以利用计算机帮助完成。算机帮助完成。2022/10/29四、四、算法的步骤设计算法的步骤设计例例1.1.写出交换两个大小相同的杯子中的液体写出交换两个大小相同的杯子中的液体(A(A水、水、B B酒酒)的一个算法。的一个算法。S1S1：找一个大小与：找一个大小与A A相同的空杯子相同的空杯子C C。酒酒B B空空C C水水A A2022/10/29例例1.1.写出交换两个大小相同的杯子中的液体写出交换两个大小相同的杯子中的液体(A(A水、水、B B酒酒)的一个算法。的一个算法。S1S1：找一个大小与：找一个大小与A A相同的空杯子相同的空杯子C C。S2S2：将：将A A中的水倒入中的水倒入C C中。中。酒酒B B水水C C空空A A四、四、算法的步骤设计算法的步骤设计2022/10/29例例1.1.写出交换两个大小相同的杯子中的液体写出交换两个大小相同的杯子中的液体(A(A水、水、B B酒酒)的一个算法。的一个算法。S1S1：找一个大小与：找一个大小与A A相同的空杯子相同的空杯子C C。S2S2：将：将A A中的水倒入中的水倒入C C中。中。S3S3：将：将B B中的酒精倒入中的酒精倒入A A中。中。空空B B水水C C酒酒A A四、四、算法的步骤设计算法的步骤设计2022/10/29例例1.1.写出交换两个大小相同的杯子中的液体写出交换两个大小相同的杯子中的液体(A(A水、水、B B酒酒)的一个算法。的一个算法。S1S1：找一个大小与：找一个大小与A A相同的空杯子相同的空杯子C C。S4S4：将：将C C中的水倒入中的水倒入B B中，结束。中，结束。S2S2：将：将A A中的水倒入中的水倒入C C中。中。S3S3：将：将B B中的酒精倒入中的酒精倒入A A中。中。水水B B空空C C酒酒A A四、四、算法的步骤设计算法的步骤设计2022/10/292 2、假如要推断、假如要推断7 7是否为质数，如何设计算法是否为质数，如何设计算法步骤？步骤？第一步，第一步，用用2 2除除7 7，得到余数，得到余数1,1,所以所以2 2不能整除不能整除7.7.第四步，第四步，用用5 5除除7 7，得到余数，得到余数2,2,所以所以5 5不能整除不能整除7.7.第五步，第五步，用用6 6除除7 7，得到余数，得到余数1,1,所以所以6 6不能整除不能整除7.7.其次步，用其次步，用3 3除除7 7，得到余数，得到余数1,1,所以所以3 3不能整除不能整除7.7.第三步，第三步，用用4 4除除7 7，得到余数，得到余数3,3,所以所以4 4不能整除不能整除7.7.第六步第六步，所以所以7 7是质数是质数.2022/10/293 3、假如要推断、假如要推断3535是否为质数，如何设计算是否为质数，如何设计算法步骤？法步骤？第一步，第一步，用用2 2除除3535，得到余数，得到余数1,1,所以所以2 2不能整除不能整除35.35.其次步，用其次步，用3 3除除3535，得到余数，得到余数2,2,所以所以3 3不能整除不能整除35.35.第三步，第三步，用用4 4除除3535，得到余数，得到余数3,3,所以所以4 4不能整除不能整除35.35.第四步，第四步，用用5 5除除3535，得到余数，得到余数0,0,所以所以5 5能整除能整除35.35.第五步，所以第五步，所以3535不是质数不是质数.2022/10/294 4、整数、整数8989是否为质数？假如让要推断是否为质数？假如让要推断8989是否为质数，依据上述算法须要设计多是否为质数，依据上述算法须要设计多少个步骤？少个步骤？第一步，第一步，用用2 2除除8989，得到余数，得到余数1,1,所以所以2 2不能整除不能整除89.89.其次步，用其次步，用3 3除除8989，得到余数，得到余数2,2,所以所以3 3不能整除不能整除89.89.第三步，第三步，用用4 4除除8989，得到余数，得到余数1,1,所以所以4 4不能整除不能整除89.89.第八十七步，第八十七步，用用8888除除8989，得到余数，得到余数1,1,所以所以8888不能不能 整除整除89.89.第八十八步第八十八步，所以所以8989是质数是质数.这种写法不能算是一个正规算法这种写法不能算是一个正规算法2022/10/29思索思索:用用2 28888逐一去除逐一去除8989求余数，须要求余数，须要8787个个步骤，这些步骤基本是重复操作，我们可以步骤，这些步骤基本是重复操作，我们可以按下面的思路改进这个算法，削减算法的步按下面的思路改进这个算法，削减算法的步骤骤.（1 1）用）用i i表示表示2 28888中的随意一个整数，并从中的随意一个整数，并从2 2起先取数；起先取数；（2 2）用）用i i除除8989，得到余数，得到余数r.r.若若r=0r=0，则，则8989不不是质数；若是质数；若r0r0，将，将i i用用i+1i+1替代，再执行同替代，再执行同样的操作；样的操作；（3 3）这个操作始终进行到）这个操作始终进行到i i取取8888为止为止.你能依据这个思路，设计一个你能依据这个思路，设计一个“推断推断8989是否是否为质数为质数”的算法步骤吗？的算法步骤吗？2022/10/29用用i i除除8989，得到余数，得到余数r r；令令i=2i=2；若若r=0r=0，则，则8989不是质数，结束算不是质数，结束算法；若法；若r0r0，将，将i i用用i+1i+1替代替代；推断推断“i88”“i88”是否成立？若是，是否成立？若是，则则8989是质数，结束算法；否则，是质数，结束算法；否则，返回其次步返回其次步.第一步，第一步，第四步，第四步，第三步，第三步，其次步，其次步，算法设计算法设计:2022/10/29一般地，推断一个大于一般地，推断一个大于2 2的整数是否为质数的整数是否为质数的算法步骤如何设计？的算法步骤如何设计？第一步，第一步，给定一个大于给定一个大于2 2的整数的整数n n；其次步，令其次步，令i=2i=2；第三步，第三步，用用i i除除n n，得到余数，得到余数r r；第四步，推断第四步，推断“r=0”“r=0”是否成立是否成立.若是，则若是，则n n 不是质数，结束算法；否则，将不是质数，结束算法；否则，将i i 的值增加的值增加1 1，仍用，仍用i i表示；表示；第五步，推断第五步，推断“i(n-1)”“i(n-1)”是否成立，若是，是否成立，若是，则则n n是质数，结束算法；否则，返回是质数，结束算法；否则，返回 第三步第三步.2022/10/29S1S1：令：令f(x)=xf(x)=x2 2-2-2，因为，因为f(1)0f(1)0,f(2)0,所以所以设设a=1,b=2a=1,b=2。S2S2：令：令m=,m=,推断推断f(m)f(m)是否为是否为0 0。若是。若是0 0，则，则m m为所为所求；若否，则接着推断求；若否，则接着推断f(a)f(m)f(a)f(m)大于大于0 0还是小于还是小于0 0。S3S3：若：若f(a)f(m)0f(a)f(m)0，则令，则令a=ma=m；否则，令；否则，令b=m b=m。S4:S4:推推断断|a-b|0.005|a-b|0.005是是否否成成立立？若若是是，则则a a或或b(b(或或区区间间上随意值上随意值)为满足条件的近似根；若否，则返回为满足条件的近似根；若否，则返回S2S2。事实上事实上,上述步骤就是在求上述步骤就是在求 的近似值。的近似值。算法设计算法设计:5、用二分法设计一个求方程、用二分法设计一个求方程 的近似的近似正根的算法，精确度正根的算法，精确度0.005。2022/10/29第一步，取函数第一步，取函数f(x)f(x)，给定精确度，给定精确度d.d.其次步，确定区间其次步，确定区间aa，bb，满足，满足f(a)f(b)0.f(a)f(b)0.第五步，推断第五步，推断a,ba,b的长度是否小于的长度是否小于d d或或f(m)f(m)是否等是否等于于0.0.若是，则若是，则m m是方程的近似解；否则，返回第是方程的近似解；否则，返回第三步三步.第三步，取区间中点第三步，取区间中点 .第四步，若第四步，若f(f(a)f(m)f(m)n”“in”是否成立，若是，是否成立，若是，结束算法；否则，返回第三步结束算法；否则，返回第三步.第五步，使第五步，使i i值增加值增加1 1，仍用，仍用i i表示表示，2022/10/29四、小结作业四、小结作业 1.1.算算法法定定义义的的理理解解：在在数数学学中中，现现代代意意义义上上的的 “算算法法”通通常常是是指指可可以以用用计计算算机机来来解解决决的的某某一一类类问问题题的的程程序序或或步步骤骤，这这些些程程序序或或步步骤骤必必需需是是明明确确和和有有效效的，而且能够在有限步之内完成的，而且能够在有限步之内完成.2.2.算法的要求：算法的要求：(1)(1)写出的算法，必需能解决一类问题写出的算法，必需能解决一类问题(例如解例如解随意一个二元一次方程组随意一个二元一次方程组)，并且能重复运用；，并且能重复运用；(2)(2)算法过程要能一步一步执行，每一步执行的算法过程要能一步一步执行，每一步执行的操作操作,必需精确，不能含混不清，而且在有限步必需精确，不能含混不清，而且在有限步之内完成后能得出结果。之内完成后能得出结果。2022/10/293.3.算法的基本特征算法的基本特征:明确性：算法对每一个步骤都有精确的，能有效明确性：算法对每一个步骤都有精确的，能有效执行且得到确定结果的，不能模棱两可。执行且得到确定结果的，不能模棱两可。依依次次与与正正确确性性：算算法法从从初初始始步步骤骤起起先先，分分为为若若干干明明确确的的步步骤骤，每每一一步步都都只只能能有有一一个个确确定定的的继继任任者者，只只有有执执行行完完前前一一步步才才能能进进入入到到后后一一步步，并并且且每每一一步步都确定无误后，才能解决问题。都确定无误后，才能解决问题。有限性：有限性：算法应由有限步组成，至少对某些输入，算法应由有限步组成，至少对某些输入，算法应在有限多步内结束，并给出计算结果。算法应在有限多步内结束，并给出计算结果。不不唯唯一一性性：求求解解某某一一个个问问题题的的解解法法不不确确定定是是唯唯一一的，对于同一个问题可以有不同的解法。的，对于同一个问题可以有不同的解法。2022/10/29