2017-2018学年32.1算法的基本思想学案

1、第二有算法初步1算法的基本思想第7页共7页.2. 了解算法的含义和学习目标1.通过几个具体问题的求解过程，体会算法的基本思想特征.3.会用自然语言描述简单的具体问题的算法.g知识梳理自主学习知识点一算法的含义及特征1 .算法的概念在解决某些问题时，需要设计出一系列可操作的或可计算的步骤,通过实施这些步骤解决问题，通常把这些步骤称为解决这些问题的算法.2 .算法的特征(1)有限性 一个算法的步骤序列是有限的.必须在有限的操作之后停I匕 不能是无限的.(2)确定性算法中的每一步应该是确定的,并且能有效地执行且得到确定的结果,而不应当模棱两可.(3)顺序性与正确性 算法从初始步骤开始，分为若干明确的

2、步骤，每一个步骤只能有一个确 定的后续步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，并且每一步都准确无误，才能完成问题.(4)不唯一性 求解某一问题的解法不一定是唯一的，对于同一个问题可以有不同的算法.(5)普遍性很多具体的问题，都可以设计合理的算法去解决，如心算、计算器计算都要经过 有限、事先设计好的步骤加以解决.3 .算法与计算机计算机解决任何问题都要依赖于算次 只有将解决问题的过程分解为若干个明确的步骤，即算法,并用计算机能够接受的“语言”准确地描述出，计算机才能够解决问题.知识点二算法的设计1 .设计算法的目的设计算法的目的实际上是寻求一类问题的算法，它可以通过计算机完成

3、.设计算法的关键是把过程分解成若干个明确的步骤，然后用计算机能够接受的“语言”准确地描述出，从而达到让计算机执行的目的.2 .设计算法的要求(1)写出的算法必须能解决一类问题.(2)要使算法尽量简单、步骤尽量少.(3)要保证算法步骤有效，且计算机能够执行.思考 一次青青草原园长包包大人带着灰太狼、懒羊羊和一捆青草过河.河边只有一条船， 由于船太小，只能装下两样东西.在无人看管的情况下，灰太狼要吃懒羊羊，懒羊羊要吃青草，请问包包大人如何才能带着他们平安过河？答包包大人采取的过河的算法可以是第一步，包包大人带懒羊羊过河；第二步，包包大人自己返回；第三步，包包大人带青草过河；第四步，包包大人带懒羊羊

4、返回；第五步，包包大人带灰太狼过河；第六步，包包大人自己返回；第七步，包包大人带懒羊羊过河.重点突破题型一算法的概念例1下列关于算法的说法，正确的个数有()求解某一类问题的算法是唯一的；算法必须在有限步操作之后停止；算法的每一步操作必须是明确的，不能有歧义或模糊；算法执行后一定产生确定的结果.A. 1B. 2C. 3D. 4答案 C解析 由于算法具有有限性、 确定性等特点，因而正确，而解决某类问题的算法不一定唯一，从而错.反思与感悟 算法实际上是解决问题的一种程序性方法，它通常解决某一个或某一类问题，在用算法解决问题时，体现了特殊与一般的数学思想.跟踪训练1下列说法中是算法的有 (填序号).从

5、上海到拉萨旅游，先坐飞机，再坐客车；解一元一次不等式的步骤是去分母、去括号、移项、合并同类项，系数化为1;求以A(1,1), B(1, 2)两点为端点的线段 AB的中垂线方程，可先求出 AB中点坐标，再求ab及中垂线的斜率，最后用点斜式方程求得线段AB的中垂线方程；求1X2X 3X4的值，先计算1X2=2,再计算2X3=6,6X4=24,得最终结果为 24;1 2X2x+4.答案解析 说明了从上海到拉萨的行程安排.给出了解一元一次不等式这类问题的解法.给出了求线段的中垂线的方法及步骤.给出了求1X2X3X 4的值的过程并得出结果.故都是算法.题型二算法的设计例2所谓正整数p为素数是指 p的所有

6、约数只有1和p.例如，35不是素数，因为35的约 数除了 1,35外，还有5与7; 29是素数，因为29的约数就只有1和29.试设计一个能够判 断一个任意正整数 n(n1)是否为素数的算法.解算法如下第一步，给出任意一个正整数n(n1).第二步，若n=2,则输出“2是素数:判断结束.第三步，令m=1.第四步，将m的值增加1,仍用m表示.第五步，如果 mn,则输出“n是素数”，判断结束.第六步，判断m能否整除n,如果能整除，则输出“n不是素数”，判断结束；如果不能整除，则转第四步.反思与感悟设计一个具体问题的算法，通常按以下步骤(1)认真分析问题，找出解决该问题的一般数学方法；(2)借助有关变量

7、或参数对算法加以表述；(3)将解决问题的过程划分为若干步骤；(4)用简练的语言将这个步骤表示出.跟踪训练2判断一个大于2的整数是否为质数的算法步骤如何设计?解第一步，给定大于 2的整数n.第二步，令i=2.第三步，用i除n,得到余数r.第四步，判断“r = 0”是否成立.若是，则n不是质数，结束算法；否则，将 i的值增加1,仍用i表示.第五步，判断“in1”是否成立.若是，则 n是质数，结束算法；否则，返回第三步.题型三算法的应用例3 一位商人有9枚银元，其中有1枚略轻的是假银元，你能用天平 (无祛码)将假银元找 出吗？解方法一算法如下.第一步，任取2枚银元分别放在天平的两边，若天平左、右不平

8、衡，则轻的一枚就是假银元, 若天平平衡，则进行第二步.第二步，取下右边的银元放在一边， 然后把剩下的7枚银元依次放在右边进行称量，直到天平不平衡，偏轻的那一枚就是假银元.方法二算法如下.第一步，把9枚银元平均分成 3组，每组3枚.第二步，先将其中两组放在天平的两边，若天平不平衡，则假银元就在轻的那一组；否则假银元在未称量的那一组.第三步，取出含假银元的那一组，从中任取2枚银元放在天平左、 右两边称量，若天平不平衡，则假银元在轻的那一边；若天平平衡，则未称量的那一枚是假银元.反思与感悟对于查找、变量代换、文字处理等非数值型计算问题，设计算法时，首先建立过程模型，然后根据过程设计步骤，完成算法.跟

9、踪训练3“韩信点兵”问题 韩信是汉高祖手下的大将，他英勇善战，谋略超群，为汉朝的建立立下了不朽功勋.据说他在一次点兵的时候，为保住军事秘密， 不让敌人知道自己部队的军事实力，采用下述点兵方法先令士兵从13报数，结果最后一个士兵报 2;又令士兵从15报数，结果最后一个士兵报3;又令士兵从17报数，结果最后一个士兵报4.这样韩信很快算出自己部队里士兵的总数.请设计一个算法，求出士兵至少有多少人.解 第一步，首先确定最小的满足除以3余2的正整数2;第二步，依次加 3就得到所有除以3余2的正整数2,5,8,11,14,17,20,第三步，在上列数中确定最小的满足除以5余3的正整数8.第四步，然后在自然

10、数内，在 8的基础上依次加上 15的倍数，得到8,23,38,53,.第五步，在上列数中确定最小的满足除以7余4的正整数应为53.易错点对算法的含义及特征的理解例4计算下列各式中的 S值，能设计算法求解的是 .(1)S= 1+2+3+ 100;(2)S= 1+2+3+ 100+ ;(3)S= 1+2+3+ n(nC N ).错解 算法是为解决某一类问题而设计的一系列操作或可计算的步骤，也就是说在实际的算法中的值是具体的，因此(1)正确；而(3)中的值不具体，错误；对于(2)显然不符合算法的有限性，故只有(1)正确.错解分析错识的根本原因在于对算法的理解不透彻.自我矫正算法是为解决某一类问题而设

11、计的一系列操作或可计算的步骤，也就是说在实际的算法中n的值是具体确定的，因此（1）（3）是正确的，而算法又是具有有限性的，即执行有 限步操作后一定能解决问题，而 （2）显然不符合算法的有限性，所以 （2）不正确.答案（3）声当堂检测自查自纠1.下列关于算法的说法中正确的是 （）A.算法是某个具体的解题过程B.算法执行后可以不产生确定的结果C.解决某类问题的算法不是唯一的D.算法可以无限地操作下去不停止答案 C解析 算法与一般意义上具体问题的解法，既有区别，又有联系，算法的获得要借助一类问题的求解方法，而这一类具体问题都可以用这种方法解决，因此A不对；算法中的每一步都应该是确定的，并且能有效执行

12、，得到确定的结果，而不能含糊其辞或有歧义，所以B不正确；算法的操作步骤必须是有限的，必须在有限的步骤内完成，因此D不对；算法具有不唯一性，C正确.2.下列四种自然语言叙述中，能称为算法的是（）A.在家里一般是妈妈做饭B.做米饭需要刷锅、淘米、添水、加热这些步骤C.在野外做饭叫野炊D.做饭必须要有米答案 B解析算法是做一件事情或解决一个问题等的程序或步骤，故选 B.3.在用二分法求方程零点的算法中，下列说法正确的是（）A.这个算法可以求所有的零点B.这个算法可以求任何方程的零点C.这个算法能求所有零点的近似解D.这个算法可以求变号零点近似解答案 D解析 二分法的理论依据是函数的零点存在定理.它解

13、决的是求变号零点的问题，并不能求 所有零点的近似值.4 .已知直角三角形两直角边长为 a, b,求斜边长c的一个算法分下列三步(i)计算 c= ya+b2 ；(2)输入直角三角形两直角边长 a, b的值；输出斜边长c的值.其中正确的顺序是.答案(2)(1)(3)解析 算法的步骤是有先后顺序的，第一步是输入，最后一步是输出，中间的步骤是赋值、计算.5 .下面是解决一个问题的算法第一步输入x.第二步 若xb 4,转到第三步；否则转到第四步.第三步输出2x-1.第四步 输出x2-2x+ 3.当输入x的值为 时，输出的数值最小值为 .答案 1 22x- 1(x4 )解析 所给算法解决的问题是求分段函数f(x)=S的函数值问题，当 x4x2 2x+3(x2X4-1 = 7;当 xv