11.1算法概念_课件1-湘教版数学必修5 25张PPT

【课标要求】
1．通过对解决具体问题过程与步骤的分析，体会算法是解决问题的“机械”程序，并能在有限步内完成，体会算法的思想．
2．通过对具体问题解决过程的探索和研究，掌握算法步骤，了解算法与求解一个具体问题在方法上的区别，明确算法的要求．
3．初步学会为一个具体问题设计算法．
算法的概念
自学导引
1．算法的概念
算法(algorithm)通常是指由 组成的求解某 的通用的方法，对于该类问题中的每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答．
2．算法的要求
(1)写出的算法，必须能解决 (例如解任意一个二元一次方程组)，并且能 ；
(2)算法过程要能 ，每一步执行的操作，必须 ，不能含混不清，而且经过有限步后能 ．
有限多个步骤
一类问题
一类问题
重复使用
一步一步执行
确切
得出结果
3．算法的特点
算法具有确定性、 和 ．
4．更相减损术
对于给定两个正整数， ．作差后将所得的 与 的数构成一对新数，对这对数再用大数减小数，以同样的操作一直做下去，直到产生一对相等的数，这个数就是最大公约数．
有效性
有限性
用较大的数减去较小的数
差
较小
自主探究
1．算法与一般意义上的数学问题的解法一样吗？
答案　算法与一般意义上的数学问题的解法既有联系又有区别．
(1)联系：算法与解法是一般与特殊、抽象与具体的关系．例如：教材先从分析一个具体的二元一次方程组的求解过程(解法)出发，归纳出了二元一次方程组的求解步骤，并且指出，这样的求解步骤也适合所有满足限制条件的二元一次方程组，这些步骤就构成了解二元一次方程组的算法；
(2)区别：算法是解决某一类问题所需要的程序和步骤的统称，也可理解为数学中的“通法”；解法是解决某一个具体问题的过程和步骤，是具体的解题过程．
2．怎样正确理解更相减损术？
答案　所谓更相减损术就是对于给定的两个数，以两数中较大的数减去较小的数，然后将差和较小的数构成一对新数，再用较大的数减去较小的数，反复执行此步骤直到差数与较小的数相等，此时相等的两数便为原两数的最大公约数．
算法步骤：(以求a，b两整数的最大公约数为例)
S1：输入两个正整数a，b(a＞b)；
S2：若a不等于b，则执行第三步，否则执行第五步；
S3：把a－b的差赋给r；
S4：如果b＞r，则把b赋给a，把r赋给b；否则把r赋给a，执行第二步；
S5：输出最大公约数b.
预习测评
1．用更相减损术求98与56的最大公约数为(　　)．
A．2 B．7
C．14 D．56
答案　C
解析　D中所示求解是无限个数相加，不具备算法的有限性特点，因此不可以用算法求解．
答案　D
3．以下有六个步骤：
①拨号；②等拨号音；③提起话筒(或免提功能)；④开始通话或挂机(线路不通)；⑤等复话方信号；⑥结束通话．
试写出打一个本地电话的算法________(只写编号)．
答案　③②①⑤④⑥
4．假设家中生火泡茶有下列几个步骤，最优的一个算法是________(只写编号)．
a．生火；b.将水倒入锅中；c.找茶叶；d.洗茶壶茶杯；e.用开水冲茶．
解析　遵循时间最短原则设计最优算法．
答案　bacde(或badce)
要点阐释
1．算法概念的理解
算法就是对一类问题(不是个别问题)都有效，计算可以一步一步地进行，每一步都能得到唯一的结果，通常我们把这一类问题的求解过程，叫做解决这一类问题的算法．算法一般是机械的，有时要进行大量重复的计算，它的优点是一种通法，只要按部就班地去做，总能算出结果，通常把算法过程称为“数学机械化”．数学机械化最大的优点，是它可以让计算机来完成．
2．算法可概括为以下几个特点
(1)有限性
一个算法应包含有限的操作步骤，而不能是无限的．
(2)确定性
算法中的每一个步骤都应当是确定的，而不应当是模棱两可的．
(3)顺序性与正确性
算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，并且每一步都准确无误，才能解决问题．
(4)不唯一性
求解某一个问题的解法不一定是唯一的，对于一个问题可以有不同的算法．
(5)普遍性
很多具体的问题，都可以设计合理的算法去解决，如心算、计算器计算都要经过有限的、事先设计好的步骤加以解决．
3．更相减损术求两个数的最大公约数时，一定要弄清每一次减法中的被减数、减数，同时要掌握减法应在何种情况下停止运算，得出结果．
典例剖析
题型一　算法的概念
【例1】 下列关于算法的描述正确的是(　　)．
A．算法与求解一个问题的方法相同
B．算法只能解决一个问题，不能重复使用
C．算法过程要一步一步执行，每步执行的操作必须确切
D．有的算法执行完后，可能无结果
解析　算法与求解一个问题的方法既有区别又有联系，故A不对；算法能重复使用，故B不对；每个算法执行后必须有结果，故D不对；由算法的有序性和确定性可知C正确．
答案　C
方法点评　算法实际上是解决问题的一种程序性方法，它通常指向某一个或一类问题，而解决的过程是程序性和构造性的．算法也可以看成解决问题的特殊的、有效的方法．
1．下列关于算法的说法，正确的有(　　)．
①求解某一类问题的算法是唯一的；②算法必须在有限步操作之后停止；③算法的每一步操作必须是明确的，不能有歧义或模糊；④算法执行后一定产生确定的结果．
A．1个 B．2个
C．3个 D．4个
解析　解决某一类问题的算法不唯一，第①个说法错误，②③④正确，故选C.
答案　C
题型二　更相减损术
【例2】 用更相减损术求下列两数的最大公约数：
(1)261,319；　(2)1 734,816.
解　用更相减损术就是根据m－n＝r，反复执行，直到n＝r为止．
(1)更相减损术：
319－261＝58，
261－58＝203，
203－58＝145，
145－58＝87，
87－58＝29，
58－29＝29，
∴319与261的最大公约数是29.
(2)更相减损术：因为两数皆为偶数，首先除以2得到867,408，再求867与408的最大公约数．
867－408＝459，
459－408＝51，
408－51＝357，
357－51＝306，
306－51＝255，
255－51＝204，
204－51＝153，
153－51＝102，
102－51＝51，
∴1 734与816的最大公约数是51×2＝102.
方法点评　通过上例可以发现用更相减损术求最大公约数，运算简单，程序易编．
2．用更相减损术求63和98的最大公约数．
解　由于63不是偶数，把98和63以大数减小数，并辗转相减，如下图所示：
所以98和63的最大公约数是7.
题型三　实际问题的算法
【例3】 一个人带三只狼和三只羚羊过河．只有一条船，同船可以容一个人和两只动物．没有人在的时候，如果狼的数量不少于羚羊的数量就会吃掉羚羊．请你设计安全渡河的算法．
解　要想安全过河，每一步都要遵循一个共同原则：在人运送动物过河的过程中，人离开岸边时必须保证每个岸边的羚羊数目要大于狼的数目．
算法如下：
S1：人带两只狼过河；
S2：人自己返回；
S3：人带一只狼过河；
S4：人自己返回；
S5：人带两只羚羊过河；
S6：人带两只狼返回；
S7：人带一只羚羊过河；
S8：人自己返回；
S9：人带两只狼过河．
方法点评　实际问题的算法与数学问题的算法是有区别的，一般数学问题的算法可以设计程序用计算机求解，而实际问题的算法一般不能用计算机解决．
3．两个大人和两个小孩一起渡河，渡口只有一条小船，每次只能渡一个大人或两个小孩，他们四人都会划船，但都不会游泳．同学们现在想一想，他们怎样渡过河去？请写一写你的渡河方案．
解　因为一次只能渡过一个大人，而船还要回来渡其他人，所以只能让两个小孩先过河，渡河的方法与步骤为：
S1：两个小孩同船渡过河去；
S2：一个小孩划船回来；
S3：一个大人独自划船渡过河去；
S4：对岸的小孩划船回来；
S5：两个小孩再同船渡过河去；
S6：一个小孩划船回来；
S7：余下的一个大人独自划船渡过河去；
S8：对岸的小孩划船回来；
S9：两个小孩再同船渡过河去．
误区警示　因对算法步骤理解不明确而致误
【例4】 写出求2＋4＋6＋8＋…＋100的算法．
[错解]　算法：
S1：计算2＋4＋6＋8＋…＋100；
S2：输出第一步中的结果．
错因分析　对于连加连乘的问题，不能直接得到答案，应当逐步进行．
[正解]　算法：
S1：计算2＋4得到6；
S2：将第一步的结果与6相加得到12；
S3：将第二步的结果与8相加得到20；
S4：如此继续下去，一直加到100；
S5：输出运算结果．
纠错心得　算法从初始步骤开始，分为若干明确的步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，而且每一步都是正确无误的，从而组成了一个有着很强逻辑性的步骤序列．
课堂总结
1．给出一个问题，设计其算法时应注意：
(1)认真分析问题，联系解决此问题的一般数学方法；
(2)综合考虑此类问题中可能涉及的各种情况；
(3)借助有关的变量或参数对算法加以表述；
(4)将解决问题的过程划分为若干个步骤；
(5)用简炼的语言将各个步骤表示出来．
2．对于数值计算问题，如解方程、求方程组的解、解不等式、解不等式组、套用公式判断性的问题、累加累乘等这一类算法的描述，一般可以通过数学模型借助数学计算方法，分解成清晰的步骤，使之条理化就可以了．
3．对于非数值性计算问题(例如：排序、查找、变量的替换、文字处理等)需要建立过程模型解决问题．
4．对于某一问题往往可以设计出多种算法，通常选用步骤较少、结构较好的算法．
5．更相减损术
求两数最大公约数时，是当较大的数减较小的数恰好等于较小的数时停止减法，这时的较小的数就是要求的两数的最大公约数.