搜索
算法初步第二章相传在古代印度的贝拿勒斯神庙，有一块黄铜板上插了三根宝石柱A，B，C，在其中一根宝石柱A上自上而下、由小到大地叠放着若干个大小不等的金盘．一名僧人要把这些金盘从宝石柱A移到另外一根宝石柱C上，也是自上而下、由小到大地叠放．僧人在移动金盘时遵守下面两条规则：第一，可以利用中间一根宝石柱B作为辅助，但一次只能移动一个金盘；第二，任何时候都不能把大的金盘放到小的金盘上．如果僧人把六十四个金盘从宝石柱A全部移到另外一根宝石柱C上，世界末日就要到了．当然，从僧人搬完六十四个金盘所需时间的角度来说，即使僧人每秒都能移动一个金盘，用最优算法，那也得要几千亿年！现代社会是一个信息化的社会，知识更新特点就是一个字“快”，当我们学好了算法，我们就拥有更强的思维能力．同时，算法也是电脑编程的基础，学好了算法，再学电脑编程，更是如鱼得水．为了能跟上时代的步伐，在这个信息化的社会中表现得更优秀，请让我们一起以最认真的态度努力学好算法初步这一章．§1算法的基本思想第二章课堂典例讲练2易错疑难辨析3课时作业4课前自主预习1课前自主预习电影《神枪手》中描述的凌靖是一个天生的狙击手，他百发百中，最难打的位置对他来说也是轻而易举，是香港警察狙击手队伍的第一神枪手．作为一名狙击手，要想成功地完成一次狙击任务，一般要按步骤完成以下几步：第一步：观察、等待目标出现(用望远镜或瞄准镜)；第二步：瞄准目标；第三步：计算(或估测)风速、距离、空气湿度、空气密度；第四步：根据第三步的结果修正弹着点；第五步：开枪；第六步：迅速转移(或隐蔽)．以上这种完成狙击任务的方法、步骤在数学上我们叫算法.1.算法的概念算法是解决某类问题的一系列________或________，只要按照这些________执行，都能使问题得到解决．一般来说，“______________”都是可以利用计算机帮助完成的．2．算法的基本思想在解决某些问题时，需要设计出____________________的步骤，通过实施这些步骤来解决问题，通常把这些步骤称为解决这些问题的________．这种解决问题的思想方法称为算法的基本思想．步骤程序步骤用算法解决问题一系列可操作或可计算算法3．算法的特征(1)________：一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束．(2)________：算法的计算规则及相应的计算步骤必须是唯一确定的．(3)________：算法中的每一个步骤都是可以在有限的时间内完成的基本操作，并能得到确定的结果．(4)________：算法从初始步骤开始，分为若干个明确的步骤，前一步是后一步的前提，后一步是前一步的后续，且除了最后一步外，每一个步骤只有一个确定的后续．(5)__________：解决同一问题的算法可以是不唯一的．有限性确定性可行性顺序性不唯一性1.以下对算法的描述正确的个数是()①对一类问题都有效；②对个别问题有效；③计算可以一步步地进行，每一步都有唯一的结果；④是一种通法，只要按部就班地做，总能得到结果．A．1个B.2个C．3个D.4个[答案]C[解析]①③④正确，均符合算法的概念与要求，②不正确．2．下列四种叙述能称为算法的是()A．在家里一般是爸爸做饭B．做饭需要刷锅、淘米、加水、加热这些步骤C．在野外做饭叫野炊D．做饭必须有米[答案]B[解析]B答案描述的是解决一类问题的方法，能称为算法，故选B.3．下列语句中是算法的个数是()①从广州到北京旅游，先坐火车，再坐飞机抵达；②解一元一次方程的步骤是去分母、去括号、移项、合并同类项、系数化为1；③方程x2－1＝0有两个实根；④求1＋2＋3＋4的值，先计算1＋2＝3，再由3＋3＝6,6＋4＝10得最终结果10.A．1个B.2个C．3个D.4个[答案]C[分析]解答本题可先正确理解算法的概念及其特点，然后逐一验证每个语句是否正确．[解析]①中说明了从广州到北京的行程安排，完成任务；②中给出了一元一次方程这一类问题的解决方法；④中给出了求1＋2＋3＋4的一个过程，最终得出结果．对于③，并没有说明如何去算，故①②④是算法，③不是算法．4．下面给出了解决问题的算法：S1输入x；S2若x≤1，则y＝2x－1，否则y＝x2＋3；S3输出y.(1)这个算法解决的问题是：________________.(2)当输入的x值为________时，输入值与输出值相等．[答案](1)求分段函数y＝2x－1x≤1，x2＋3x1，的函数值(2)1[解析](1)根据题意可知：y＝2x－1x≤1x2＋3x1输入x的值求y.(2)令2x－1＝x(x≤1)或x2＋3＝x(x1)求解方程．5．设计一个算法求方程5x＋2y＝22的正整数解，其最后输出的结果应为________．[答案](2,6)，(4,1)[解析]因为求方程的正整数解，所以应将x从1开始输入，直到方程成立．x＝2时，y＝22－5×22＝6；x＝4时，y＝22－5×42＝1.课堂典例讲练下列说法正确的是()A．算法就是某个问题的解题过程B．算法执行后可以产生不同的结果C．解决某一个具体问题时，算法不同，结果不同D．算法执行步骤的次数不可以很大，否则无法实施[思路分析]解答本题的关键是理解算法的意义及特征．对算法意义的理解[规范解答]选项A，算法不能等同于解法；选项C，解决某一个具体问题，算法不同结果应该相同，否则就是算法构造得有问题；选项D，算法执行的步骤可以有很多次，但不可以是无限次．[答案]B[规律总结]算法一般是机械的，有时需要进行大量的重复计算．只要按部就班地去做，总能算出结果．通常把算法过程称为“数学机械化”．数学机械化的最大优点是它可以借助计算机来完成．指出下列哪个不是算法()A．解方程2x－6＝0的过程是移项和系数化为1B．从青岛经上海再到杭州旅游要先乘轮船到上海，再转乘火车C．解方程2x2＋x－1＝0D．利用公式S＝πr2计算半径为3的圆的面积就是计算π×32[答案]C[解析]由算法概念知，C不是算法，而A、B、D三项都解决了一类问题，故为算法.筛选问题的算法设计设计一个算法，对任意3个整数a、b、c，求出其中的最小值．[思路分析]比较a，b――→较小的数记为m比较m与c―→最小数[规范解答]算法步骤如下：1．比较a与b的大小，若ab，则m＝a；若ba，则m＝b；2．比较m与c的大小，若mc，则m为最小数；若cm，则c为最小数．[规律总结]求最小(大)数就是从中筛选出最小(大)的一个，筛选过程中的每一步都是比较两个数的大小，保证了筛选的可行性，这种方法可以推广到从多个不同数中筛选出满足要求的一个．在下列数字序列中，写出搜索89的算法：21,3,0,9,15,72,89,91,93.[解析]1.先找到序列中的第一个数m，m＝21；2．将m与89比较，是否相等，如果相等，则搜索到89；3．如果m与89不相等，则往下执行；4．继续将序列中的其他数赋给m，重复第2步，直到搜索到89.数值性问题的算法写出求1＋2＋3＋4＋5＋6的一个算法．[思路分析]这是一个累加求和问题，可按照逐个相加的办法计算，就得到一种解决它的步骤，即一种算法；若想到公式1＋2＋3＋…＋n＝nn＋12，也可运用它解决，问题就是计算当n＝6时式子的值．[规范解答]解法一：逐个相加，算法设计如下：1．计算1＋2得到3.2．将第1步的运算结果3与3相加，得到6.3．将第2步的运算结果6与4相加，得到10.4．将第3步的运算结果10与5相加，得到15.5．将第4步的算运结果15与6相加，得到21.解法二：利用公式，算法设计如下：1．给定n＝6.2．计算nn＋12.3．输出运算结果21.[规律总结]本题的解法二体现了算法的本质：对一类问题的机械的、统一的求解方法．将步骤一直写下去，便得到任意有限个数相加的算法．运用公式使算法显得简单，特别地，当加数的个数比较多时，解法二便显示出了它的优越性．写出求2×4×6×8×10值的算法．[解析]算法如下：1．计算2×4，得到8.2．将第1步的运算结果8与6相乘，得到48.3．将第2步的运算结果48与8相乘，得到384.4．将第3步的运算结果384与10相乘，得到3840.非数值性问题的算法一个人带三只狼和三只羚羊过河，只有一条船，同船可以容一个人和两只动物，没有人在的时候，如果狼的数量不少于羚羊的数量，狼就会吃掉羚羊．(1)设计安全渡河的算法；(2)思考每一步算法所遵循的共同原则是什么？[思路分析]应首先运具有威胁性的动物狼，再运羚羊，运过河的狼还可以再运回来，注意不能让狼吃羊．[规范解答](1)1．人带两只狼过河；2．人自己返回；3．人带一只狼过河；4．人自己返回；5．人带两只羚羊过河；6．人带两只狼返回；7．人带一只羚羊过河；8．人自己返回；9．人带两只狼过河．(2)在人运送动物过河的过程中，人离开岸边时必须保证每个岸边的羚羊的数目大于狼的数目．[规律总结]1.对于非数值性的问题，在设计算法时，应当先建立过程模型，也就是找到解决问题的方案，再把它细化为一步连接一步组成的步骤．从而设计出算法．2．首先应想到先运两只狼，这是唯一的首选步骤，只有这样才可避免狼吃羊，带过一只羊后，必须将狼带回来才行．两个大人和两个小孩一起渡河，渡口只有一条小船，每次只能渡一个大人或两个小孩，他们四人都会划船，但都不会游泳，他们如何渡河？请写出你的渡河方案及算法．[解析]因为一次只能渡过一个大人或两个小孩，而船还要回来渡其他人，所以只能让两个小孩先过河，渡河的方案算法为：1．两个小孩同船渡过河去；2．一个小孩划船回来；3．一个大人独自划船渡过河去；4．对岸的小孩划船回来；5．两个小孩再同船渡过河去；6．一个小孩划船回来；7．余下的一个大人独自划船渡过河去；8．对岸的小孩划船回来；9．两个小孩再同船渡过河去．易错疑难辨析设计一个解方程ax2＋bx＋c＝0的算法[错解]小华采用的算法描述如下：1计算Δ＝b2－4ac；2若Δ0，则输出“方程无实根”；3若Δ0，则输出方程的根．[辨析]上述算法中有两处错误：第一处是没有考虑a是否为0，显然a＝0时，方程无Δ，上述算法无效；第二处错误是漏掉了Δ＝0的情况．[正解]1输入a、b、c的值．2若a＝0，b≠0，则输出方程的根x＝－cb；若a＝b＝0，c≠0，则输出“方程无实根”；若a＝b＝c＝0，则输出“方程有无数个实根”．3．若a≠0，计算Δ＝b2－4ac：若Δ0，则输出“方程无实根”；若Δ≥0，则输出方程的根x1,2＝－b±Δ2a.[规律总结]本例说明算法一方面具有具体化、程序化、机械化的特点，同时又具有高度的抽象性、概括性和精确性，所以算法在表达问题解决的过程中具有条理性、逻辑性的特点．课时作业（点此链接）