2019年数学湘教版必修5新设计同步（讲义）：第11章 11.1 算法的概念

11．1算法的概念
1．算法的概念
在数学中，算法通常是指由有限多个步骤组成的求解某一类问题的通用的方法．
2．算法的特点
一般地，对一个问题的算法就是解决该问题的程序步骤的概要说明，它有以下三个特点：
(1)这一程序必须是确定的——各步骤的本质与次序被明确清楚地加以描述；
(2)这一程序步骤必须是有效的——按此程序步骤最后必然能得到这一问题正确的解；
(3)这一程序步骤必须是有限的——该程序在有限步之后终止.
1．如何理解算法的概念？
提示：(1)现代意义上的“算法”通常是指用计算机来解决某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成．
(2)算法是机械的，有时要进行大量重复计算，只要按部就班地去做，总能算出结果．通常把算法过程称为“数学机械化”，其最大优点是可以让计算机来完成．
(3)求解某一个问题的算法不一定只有唯一的一个，可能有不同的算法．
2．如何理解算法的三个特点？
提示：(1)确定性
算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，并且每一步都准确无误，才能解决问题．
(2)有效性
算法中的每一步应该是确定的，并且能有效地执行且得到确定的结果，而不应当是模棱两可的．比如让学生求的近似值却没有要求近似的精确度，不同的学生会得到不同的结果或者说该问题根本不能求解．
(3)有限性
一个算法的步骤序列是有限的，它应在有限步操作之后停止，而不能是无限的．
算法的概念
有下列说法：
①求解某一类问题的算法是唯一的；
②算法必须在有限步操作后停止；
③算法的每一步操作必须是明确的，不能存在歧义；
④算法执行后一定能产生确定的结果．
其中，正确说法的序号有__________．
[解析]　由算法的不唯一性知①不正确；
由算法的有限性知②正确；
由算法的正确性知③和④正确．
[答案]　②③④
1．算法是解决某一类问题的一种程序化方法．
2.判断一个问题是否有算法，关键看是否有解决某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成．
1．指出下列哪个不是算法(　　)
A．解方程2x－6＝0 的过程是移项和系数化为1
B．从长沙到北京要先乘汽车到飞机场，再乘飞机到北京
C．解方程2x2＋x－1＝0
D．利用公式S＝πr2计算半径为3的圆的面积就是计算π×32
解析：选C　由算法概念知，C不是算法，而A，B，D三项都解决了一类问题，故为算法．
算法的设计
写出解方程x2－2x－3＝0的一个算法．
[解]　法一：S1：移项，得x2－2x＝3；
S2：x2－2x＝3式两边同时加1，并配方，得(x－1)2＝4；
S3：(x－1)2＝4式两边开方，得x－1＝±2；
S4：解x－1＝±2得x＝3或x＝－1.
法二：S1：计算出一元二次方程的判别式的值，并判断其符号，显然Δ＝22＋4×3＝16>0；
S2：将a＝1，b＝－2，c＝－3代入求根公式得x1＝3，x2＝－1.
设计一个具体的算法的步骤
(1)认真分析问题，找出解决此问题的一般数学方法；
(2)借助有关变量或参数对算法加以表述；
(3)将解决问题的过程划分为若干步骤；
(4)用简单的语言将这个步骤表示出来．
2．对任意3个整数a，b，c，写出求最大数的算法．
解：算法步骤如下：
S1：令max＝a；
S2：比较max与b的大小，若b＞max，则令max＝b；
S3：比较max与c的大小，若c＞max，则令max＝c；
S4：max就是a，b，c中的最大数．
利用“更相减损术”求最大公约数
用更相减损术求154与242的最大公约数．
[解]　154÷2＝77,242÷2＝121.
下面用更相减损术求77与121的最大公约数．
121－77＝44，
77－44＝33，
44－33＝11，
33－11＝22，
22－11＝11.
故77与121的最大公约数为11，则154与242的最大公约数为11×2＝22.
“更相减损术”的算法步骤
第一步：任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．
第二步：以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．重复这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．
3．用更相减损术求228与1 995的最大公约数．
解：1 995－228＝1 767,1 767－228＝1 539，
1 539－228＝1 311,1 311－228＝1 083，
1 083－228＝855,855－228＝627，
627－228＝399,399－228＝171，
228－171＝57,171－57＝114，
114－57＝57.
所以228与1 995的最大公约数为57.
[随堂体验落实]
1．下列对算法的理解不正确的是(　　)
A．算法有一个共同特点就是对一类问题都有效(而不是个别问题)
B．算法要求是一步步执行，每一步都能得到唯一的结果
C．算法一般是机械的，有时要进行大量重复的计算，它的优点是一种通法
D．任何问题都可以用算法来解决
解析：选D　算法是解决问题的精确的描述，但是并不是所有问题都有算法．
2．下列可以看成算法的是(　　)
A．学习数学时，课前预习，课上认真听讲并记好笔记，课下先复习再做作业，之后做适当的练习题
B．今天餐厅的饭真好吃
C．这道数学题很难做
D．方程2x2－x＋1＝0无实数根
解析：选A　A是学习数学的一个步骤，所以是算法．
3．早上从起床到出门需要洗脸刷牙(5 min)、刷水壶(2 min)、烧水(8 min)、泡面(3 min)、吃饭(10 min)、听广播(8 min)几个步骤．从下列选项中选出较好的一种算法(　　)
A．S1：洗脸刷牙、S2：刷水壶、S3：烧水、S4：泡面、S5：吃饭、S6：听广播
B．S1：刷水壶、S2：烧水同时洗脸刷牙、S3：泡面、S4：吃饭、S5：听广播
C．S1：刷水壶、S2：烧水同时洗脸刷牙、S3：泡面、S4：吃饭同时听广播
D．S1：吃饭同时听广播、S2：泡面、S3：烧水同时洗脸刷牙、S4：刷水壶
解析：选C　完成这个过程用时最少的是最好的算法，因此我们可以从四个答案所给出的步骤是否合理，需要花费多少时间入手．
4．求1＋2＋3＋…＋100时可运用公式1＋2＋3＋…＋n＝直接计算，算法可设计为：S1：________；S2：________；S3：输出计算结果．
解析：S1：取n＝100；
S2：计算的值．
答案：取n＝100　 计算 的值
5．给出下列算法：
S1：输入x的值；
S2：当x>4，计算y＝x＋2；否则执行下一步；
S3：计算y＝；
S4：输出y.
当输入x＝0时，输出y＝________.
解析：0<4，执行第三步，y＝＝2.
答案：2
6．求261和319的最大公约数．
解：319－261＝58，
261－58＝203，
203－58＝145，
145－58＝87，
87－58＝29，
58－29＝29.
∴261和319的最大公约数为29.
[感悟高手解题]
[巧解题]
一个人带着三只狼和三只羊过河，只有一条船，同船可容纳一个人和两只动物，没有人在的时候，如果狼的数量大于等于羊的数量，狼就会吃羊，该人如何将动物转移过河？请设计算法．
[解]　任何动物同船不用考虑动物的争斗，但需考虑承载的数量，还应考虑到两岸的动物都得保证狼的数量要小于羊的数量，故在算法的构造过程中尽可能保证船里面有狼，这样才能使得两岸羊的数量占到优势．
算法步骤如下：
S1：人带两只狼过河，并自己返回；
S2：人带一只狼过河，并自己返回；
S3：人带两只羊过河，并带两只狼返回；
S4：人带一只羊过河，自己返回；
S5：人带两只狼过河．
[点评]　算法是解决一类问题的精确描述，有些问题使用形式化、程序化的刻画是最恰当的，这就要求我们在写算法时应精练、清晰地表达，要善于分析任何可能出现的情况，体现思维的严密性和完整性．在现实生活中，很多较复杂的问题经常需要将某些步骤重复进行多次，设计算法时，如果能够合适地利用某些步骤的重复，不但可以使得问题变得简单，而且可以提高工效．
一、选择题
1．下列所给问题中，不可以设计一个算法求解的是(　　)
A．二分法求方程x2－3＝0的近似解
B．解方程组
C．求半径为3的圆的面积
D．判断函数y＝x2在R上的单调性
解析：选D　A，B，C选项中的问题都可以设计算法解决，D选项中的问题由于x在R上取值无穷尽，所以不能设计一个算法求解．
2．下列各式中T的值不能用算法求解的是(　　)
A．T＝12＋22＋32＋42＋…＋1002
B．T＝＋＋＋＋…＋
C．T＝1＋2＋3＋4＋5＋…
D．T＝1－2＋3－4＋5－6＋…＋99－100
解析：选C　根据算法的有限性知C不能用算法求解．
3．小明中午放学回家自己煮面条吃，有下面几道工序：①刷锅盛水2分钟；②洗菜6分钟；③准备面条及佐料2分钟；④用锅把水烧开10分钟；⑤煮面条3分钟．以上各道工序，除了④之外，一次只能进行一道工序．小明要将面条煮好，最少要用的分钟数为(　　)
A．13　　　　　　　　　 　B．14
C．15 D．23
解析：选C　①刷锅盛水2分钟、④用锅把水烧开10分钟(同时②洗菜6分钟、③准备面条及佐料2分钟)、⑤煮面条3分钟，共为15分钟．
4．对于算法：
S1：输入n；
S2：判断n是否等于2，若n＝2，则n满足条件；若n>2，则执行S3；
S3：依次从2到(n－1)检验能不能被n整除，若不能被n整除，则执行S4；若能整除n，则结束算法；
S4：输出n.
满足条件的n是(　　)
A．质数 B．奇数
C．偶数 D．约数
解析：选A　此题首先要理解质数，只能被1和自身整除的大于1的整数叫质数.2是最小的质数，这个算法通过对2到(n－1)一一验证，看是否有其他约数，来判断其是否为质数．
二、填空题
5．已知一位同学的语文成绩为89分，数学成绩为96分，英语成绩为99分．求他的总分和平均成绩的一个算法为：
S1：取A＝89，B＝96，C＝99；
S2：_______________________；
S3：_______________________；
S4：输出计算结果．
解析：S2：计算总分；S3：计算平均数．
答案：计算总分D＝A＋B＋C
计算平均成绩E＝
6．下面给出了解决问题的算法：
S1：输入x；
S2：若x≤1，则y＝2x－1，否则y＝x2＋3；
S3：输出y .
(1)这个算法解决的问题是________；
(2)当输入的x值为________时，输入值与输出值相等．
解析：由题意知，该算法的算法功能是求分段函数y＝的函数值．
当x≤1时，由2x－1＝x，得x＝1；当x>1时，由x2＋3＝x知，方程无解．
答案：(1)求分段函数y＝的函数值
(2)1
7．已知a＝333，b＝24，则使得a＝bq＋r(q，r均为自然数，且0≤r解析：333＝24×13＋21，
∴q＝13，r＝21.
答案：13,21
8．123和48的最大公约数是________．
解析：123－48＝75，
75－48＝27，
48－27＝21，
27－21＝6，
21－6＝15，
15－6＝9，
9－6＝3，
6－3＝3，
∴123和48的最大公约数为3.
答案：3
三、解答题
9．写出求方程组的解的算法．
解：法一：S1：②×2＋①，得到5x＝14－4； 　③
S2：解方程③，可得x＝2；　 ④
S3：将④代入②，可得2＋y＝－2；　 ⑤
S4：解⑤得y＝－4；
S5：得到方程组的解为
法二：S1：由②式移项可以得到x＝－2－y；　 ⑥
S2：把⑥代入①，得y＝－4；　 ⑦
S3：把⑦代入②，得x＝2；
S4：得到方程组的解为
10．写出求1×2×3×4×5×6的一个算法．
解：S1：计算1×2，得到2；
S2：将S1的运算结果2乘3，得到6；
S3：将S2的运算结果6乘4，得到24；
S4：将S3的运算结果24乘5，得到120；
S5：将S4的运算结果120乘6，得到720；
S6：输出运算结果.