第二章第二章 算法初步算法初步1 1 算法的基本思想算法的基本思想1.1.了解算法的含义，形成算法的初步印象，体会算法是解了解算法的含义，形成算法的初步印象，体会算法是解决问题的决问题的“机械机械”程序，并能在有限步内解决问题；程序，并能在有限步内解决问题；2.2.能够用自然语言叙述算法；能够用自然语言叙述算法；3.3.掌握正确的算法应满足的条件；掌握正确的算法应满足的条件；4.4.会写出简单问题的算法会写出简单问题的算法. . 作为家里的一员，在平时分担一些力所能及的事是我们作为家里的一员，在平时分担一些力所能及的事是我们应尽的义务，你每天都帮家里做家务吗？你会烧开水吗？请应尽的义务，你每天都帮家里做家务吗？你会烧开水吗？请写出你在家中烧开水的过程写出你在家中烧开水的过程. .1 1、往壶内注水；、往壶内注水；2 2、点火加热；、点火加热；3 3、观察：如果水开，则停止烧火，否则继续烧火；、观察：如果水开，则停止烧火，否则继续烧火；4 4、如果水未开，重复过程、如果水未开，重复过程 “ “3”3”，直至水开，直至水开. .2 2、判断水是否烧开与是否继续烧火的过程是一个反馈、判断水是否烧开与是否继续烧火的过程是一个反馈与判断的过程，因此有必要不断重复过程与判断的过程，因此有必要不断重复过程“3”. 3”. 小结：小结：1 1、其实大部分事情都是按照一定的程序执行的，因此、其实大部分事情都是按照一定的程序执行的，因此要理清事情的每一步要理清事情的每一步. . 事实上，我们完成任何事，都要有步骤，合理安排步事实上，我们完成任何事，都要有步骤，合理安排步骤，会达到事半功倍的效果骤，会达到事半功倍的效果. .从我们数学的意义来讲，在解从我们数学的意义来讲，在解决某些问题时，需要设计出一系列可操作或可计算的步骤，决某些问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，我们通常把这些步骤称为通过实施这些步骤来解决问题，我们通常把这些步骤称为解决问题的一种算法解决问题的一种算法. .这种描述不是算法的定义，但反映了这种描述不是算法的定义，但反映了算法的基本思想算法的基本思想. . 随着计算科学和信息技术的飞速发展，算法的思想已随着计算科学和信息技术的飞速发展，算法的思想已经渗透到社会的方方面面经渗透到社会的方方面面. .在以前的学习中，虽然没有出在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量现算法这个名词，但实际上在数学教学中已经渗透了大量的算法思想，如四则运算的过程、求解方程的步骤等等的算法思想，如四则运算的过程、求解方程的步骤等等. .完成这些工作都需要一系列程序化的步骤，这就是算法的完成这些工作都需要一系列程序化的步骤，这就是算法的思想思想. . 例例1 1 在电视台的某个娱乐节目中，要求参与者快速猜出物品的价格在电视台的某个娱乐节目中，要求参与者快速猜出物品的价格. .主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或者正确高了、低了或者正确. .在某次节目中，主持人出示了一台价值在在某次节目中，主持人出示了一台价值在10001000元元以内的随身听，并开始了竞猜以内的随身听，并开始了竞猜. .下面是主持人和参与者的一段对话：下面是主持人和参与者的一段对话：如果你是参与者，你接下来会怎么猜？如果你是参与者，你接下来会怎么猜？800元！高了!400元！600元！低了!低了!参与者主持人主持人实际上，可以把过程概括如下：实际上，可以把过程概括如下：例例2 2 在给定素数表的条件下，设计算法，将在给定素数表的条件下，设计算法，将936936分解分解成素因数的乘积成素因数的乘积.(4000.(4000以内的素数表见课本附录以内的素数表见课本附录1)1)解解:算法步骤如下：算法步骤如下：1.判断判断936是否为素数：否是否为素数：否.2.确定确定936的最小素因数：的最小素因数：2. 936=24683.判断判断468是否为素数：否是否为素数：否.4.确定确定468的最小素因数：的最小素因数：2. 936=222345.判断判断234是否为素数：否是否为素数：否.6.确定确定234的最小素因数：的最小素因数：2. 936=2221177.7.判断判断117117是否为素数：否是否为素数：否. .8.8.确定确定117117的最小素因数：的最小素因数：3. 936=2223393. 936=2223399.9.判断判断3939是否为素数：否是否为素数：否. .10.10.确定确定3939的最小素因数：的最小素因数：3. 936=22233133. 936=2223313判断判断1313是否为素数：是否为素数：1313是素数，所以分解结束是素数，所以分解结束. .分解结果是：分解结果是： 936=2223313936=2223313 例例3 3 设计一个算法，求设计一个算法，求840840与与17641764的最大公因数的最大公因数. .1.先将先将840进行素因数分解：进行素因数分解：；2.然后将然后将1764进行素因数分解：进行素因数分解：；3.确定他们的公共素因数确定他们的公共素因数2,3,7；4.确定公共素因数的指数：公共素因数确定公共素因数的指数：公共素因数2,3,7的指数分别为的指数分别为2,1,1;5.最大公约数为最大公约数为: .解：解：算法步骤如下：算法步骤如下：例例4 “4 “韩信点兵韩信点兵”问题问题. .韩信是汉高祖刘邦手下的大将，他英勇善战，韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为建立汉朝立下了汗马功劳智谋超群，为建立汉朝立下了汗马功劳. .据说他在点兵的时候，为了据说他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，采用下述点兵的方法：保住军事机密，不让敌人知道自己部队的实力，采用下述点兵的方法：先令士兵从先令士兵从1 13 3报数，结果最后一个士兵报报数，结果最后一个士兵报2 2；再令士兵从；再令士兵从1 15 5报数，报数，结果最后一个士兵报结果最后一个士兵报3 3；又令士兵从；又令士兵从1 17 7报数，结果最后一个士兵报报数，结果最后一个士兵报4.4.这样，韩信很快就算出了自己部队的总人数这样，韩信很快就算出了自己部队的总人数. .请设计一个算法，求请设计一个算法，求出士兵至少有多少人出士兵至少有多少人? ?分析：分析：从报数情况分析，总人数除以从报数情况分析，总人数除以3余余2；总人数除以；总人数除以5余余3；总人数；总人数除以除以7余余4.算法的第一步是将所有的除以算法的第一步是将所有的除以3余余2的正整数找出来，按从小的正整数找出来，按从小到大排成一列到大排成一列.第二步是从第一步的数列中找出除以第二步是从第一步的数列中找出除以5余余3的一列数，按的一列数，按从小到大排成一列从小到大排成一列.最后在满足前两个条件的第二步数列中再找出除以最后在满足前两个条件的第二步数列中再找出除以7余余4的一列数，这列数中最小的数，即为我们所求的数的一列数，这列数中最小的数，即为我们所求的数.（1）首先确定最小的满足除以）首先确定最小的满足除以3余余2的正整数：的正整数：2.解：解：具体算法步骤如下：具体算法步骤如下：（5）在第）在第4步得到的一列数中，找出满足除以步得到的一列数中，找出满足除以7余余4的最小的最小数：数：53.这就是我们要求的数这就是我们要求的数.（4）然后依次加上）然后依次加上15，得到，得到8，23，38，53，显然，显然这些数既满足除以这些数既满足除以3余余2，又满足除以，又满足除以5余余3.（3）在上列数中确定最小的满足除以）在上列数中确定最小的满足除以5余余3的正整数：的正整数：8.（2）依次加）依次加3就得到所有除以就得到所有除以3余余2的正整数：的正整数：2，5，8，11，14，17，20，23，26，29，32，35，38，41，44，47，50，53，563 3、算法要简洁，要清晰可读，不能繁杂，易程序化、算法要简洁，要清晰可读，不能繁杂，易程序化. .算法不同于求解一个具体问题的方法，是这种方法算法不同于求解一个具体问题的方法，是这种方法的高度概括的高度概括. .一个好的算法有如下要求：一个好的算法有如下要求：1 1、写出的算法，必须能解决一类问题（如一元二次方、写出的算法，必须能解决一类问题（如一元二次方程求根公式），并且能重复使用程求根公式），并且能重复使用. .2 2、算法过程要能一步一步执行，每步执行的操作，必、算法过程要能一步一步执行，每步执行的操作，必须确切，不能含混不清，而且在有限步能得出结果须确切，不能含混不清，而且在有限步能得出结果. .例例5 5、写出以下问题的算法：、写出以下问题的算法：一位商人有一位商人有9 9枚银元，其中有枚银元，其中有1 1枚略轻的是假银元枚略轻的是假银元. .你能你能用天平（不用砝码）将假银元找出来吗？用天平（不用砝码）将假银元找出来吗？解解: 1.把银元分成把银元分成3组，每组组，每组3枚枚.2先将两组分别放在天平的两边先将两组分别放在天平的两边.如果天平不平衡，那如果天平不平衡，那边假银元就放在轻的那一组；如果天平左右平衡，则假边假银元就放在轻的那一组；如果天平左右平衡，则假银元就在末称的第银元就在末称的第3组里组里.3取出含假银元的那一组，从中任取两枚银元放在天平取出含假银元的那一组，从中任取两枚银元放在天平的两边的两边.如果左右不平衡，则轻的那一边就是假银元；如如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则末称的那一枚就是假银元果天平两边平衡，则末称的那一枚就是假银元.算法是什么？算法是什么？算法可以理解为由基本运算及规定的运算顺序构成的算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤，或看成按要求设计好的、有限的、确完整的解题步骤，或看成按要求设计好的、有限的、确切的计算序列，并且这样的步骤或序列能解决一类问题切的计算序列，并且这样的步骤或序列能解决一类问题. .现代意义上的现代意义上的“算法算法”通常是指可以用计算机来解决通常是指可以用计算机来解决的某一类问题的程序或步骤的某一类问题的程序或步骤. .说明：说明：1 1、算法实际上就是解决某一类问题的步骤和方法，在解、算法实际上就是解决某一类问题的步骤和方法，在解决问题时形成的规律性的东西，按照算法描述的规则与步决问题时形成的规律性的东西，按照算法描述的规则与步骤，一步一步地去做，最终便能解决问题骤，一步一步地去做，最终便能解决问题. .2 2、算法的基本思想就是我们分析问题时的想法、算法的基本思想就是我们分析问题时的想法. .由于想法由于想法不同、思考的角度不同，着手点不一样，同一问题存在不不同、思考的角度不同，着手点不一样，同一问题存在不同的算法，算法有优劣之分同的算法，算法有优劣之分. .3 3、从熟悉的问题出发，体会算法的程序化思想，学会用、从熟悉的问题出发，体会算法的程序化思想，学会用自然语言来描述算法自然语言来描述算法. .例例6 6在函数的应用部分在函数的应用部分,我们学习了用二分法求方程我们学习了用二分法求方程f(x)=0的的近似解近似解.如图所示如图所示分析：分析：yxOabx*二分法的基本思想是二分法的基本思想是:将方程的有解将方程的有解区间分为两个小区间区间分为两个小区间,然后判断解在然后判断解在哪个小区间哪个小区间;继续把有解的区间一分继续把有解的区间一分为二进行判断为二进行判断,如此周而复始如此周而复始,直到直到求出满足精度要求的近似解求出满足精度要求的近似解.其算法步骤如下其算法步骤如下5.5.判断新的有解区间长度是否大于精确度判断新的有解区间长度是否大于精确度: :(1)(1)如果新的有解区间长度大于精确度如果新的有解区间长度大于精确度, ,则在新的有解区间则在新的有解区间的基础上重复上述步骤的基础上重复上述步骤; ;(2)(2)如果新的有解区间长度小于或等于精确度如果新的有解区间长度小于或等于精确度, ,则这个有解则这个有解区间中的任意一个数均为方程的满足精度的近似解区间中的任意一个数均为方程的满足精度的近似解. .3.计算计算f(0.5)=-0.625;6.计算计算f(0.75)=-0.015625;9.计算计算f(0.875)=0.435 546 875;10.由于由于f(0.75)f(0.875)0.1;12.12.计算计算所以，区间所以，区间0.75,0.81250.75,0.8125中的任一数值，都可以作中的任一数值，都可以作为方程的近似解为方程的近似解. .13.13.第一步第一步: :令令f(x)=xf(x)=x3 3+x+x2 2-1,-1,因为因为f(0)f(1)0,f(0)f(1)0,)f(m)0,则令则令x x1 1= m;= m;否则否则, ,令令x x2 2= m.= m.简化写法简化写法: :第四步第四步: :判断判断|x|x1 1-x-x2 2|0.1|0.1是否成立是否成立? ?若是若是, ,则则x x1 1,x,x2 2之间的中之间的中间值为满足条件的近似解间值为满足条件的近似解; ;若否若否, ,则返回第二步则返回第二步. .算法的特征算法的特征 有穷性：有穷性：一个算法应包含有限的操作步骤而不应是无限的一个算法应包含有限的操作步骤而不应是无限的; ; 确定性：确定性：算法中每一个步骤应当是确定的，而不应当是含算法中每一个步骤应当是确定的，而不应当是含糊的、模棱两可的糊的、模棱两可的; ;有效性：有效性：算法中每一个步骤应当能有效地执行，并得到确算法中每一个步骤应当能有效地执行，并得到确定的结果定的结果. .输入输入: :有零个或多个输入有零个或多个输入; ;输出输出: :有一个或多个输出有一个或多个输出; ;一个人带三只狼和三只羚羊过河，只有一条船，船可以一个人带三只狼和三只羚羊过河，只有一条船，船可以容纳一个人和两只动物没有人在的时候，如果狼的数量不容纳一个人和两只动物没有人在的时候，如果狼的数量不少于羚羊的数量，狼就会吃掉羚羊请设计过河的算法少于羚羊的数量，狼就会吃掉羚羊请设计过河的算法解：解：算法或步骤如下：算法或步骤如下：S4 人带两只狼返回；人带两只狼返回；S2 人自己返回；人自己返回；S3 人带一只羚羊过河；人带一只羚羊过河；S1 人带两只狼过河；人带两只狼过河；S5 人带两只羚羊过河；人带两只羚羊过河；S6 人自己返回；人自己返回；S7 人带两只狼过河；人带两只狼过河；S8 人自己返回；人自己返回；S9 人带一只狼过河人带一只狼过河1 1、算法：算法是解决某类问题的一系列步骤或程序；、算法：算法是解决某类问题的一系列步骤或程序；2 2、算法的基本思想算法的基本思想：程序化思想程序化思想；3 3、算法的特算法的特征征: :有穷性有穷性确定性确定性输入输入输出输出有效性有效性世间没有一种具有真正价值的东西，可以不经过艰苦辛勤的劳动而得到.