2019-2020年高中数学 第1章 算法初步 1.4 算法案例教学案 苏教版必修3

《2019-2020年高中数学 第1章 算法初步 1.4 算法案例教学案 苏教版必修3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2019-2020年高中数学第1章算法初步1.4算法案例教学案苏教版必修3问题1：如何求12与20的最大公约数？提示：短除法．一般情况下数字不应过大．问题2：若求6750与3492的最大公约数，上述方法还奏效吗？提示：数值很大时短除法不方便用．问题3：对于问题1中12与20的最大公约数是4.若用20除以12余8，再用8去除12余4，再用4去除8余数为0，也可求得最大公约数为4.若对较大两数可否用此法求公约数？提示：可以．1．孙子问题(1)问题名称：人们将“韩信点兵——孙子问题”这种问题的通用解法

2、称为“孙子剩余定理”或“中国剩余定理”．(2)问题思想：“孙子问题”相当于求关于x，y，z的不定方程组2．欧几里得辗转相除法(1)含义：公元前3世纪，欧几里得在《原本》第七篇中介绍了求两个正整数a，b(a＞b)的最大公约数的方法，这种方法称为“欧几里得辗转相除法”．(2)步骤：计算出a÷b的余数r，若r＝0，则b即为a，b的最大公约数；若r≠0，则把前面的除数b作为新的被除数，把余数r作为新的除数，继续运算，直到余数为0，此时的除数即为a，b的最大公约数．3．两个常用函数(1)Mod(a，b)表

3、示a除以b所得的余数．(2)Int(x)表示不超过x的最大整数．1．由除法和减法的性质可知，对于任意两个正整数，辗转相除法或更相减损术总可以在有限步之后完成，故总能用这两种方法求出任意两个正整数的最大公约数．2．辗转相除法的理论依据是：由a＝nb＋r⇒r＝a－nb得a、b与b、r有相同的公约数．[例1]　有3个连续的正整数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，画出求满足要求的一组三个连续正整数的流程图，并写出伪代码．[思路点拨]　设这三个数分别为m，m＋1，m＋2，则

4、m满足的条件是Mod(m,15)＝0且Mod(m＋1,17)＝0且Mod(m＋2,19)＝0.[精解详析]　流程图：伪代码：m←2WhileMod(m,15)≠0　orMod(m＋1,17)≠0　orMod(m＋2,19)≠0m←m＋1EndWhilePrintm，m＋1，m＋2[一点通]解决此类问题的方法就是从m＝2开始，对每一个正整数逐一检验，当m满足所有已知条件时，结束循环，输出m.1．如图所示的流程图，输出的结果是________．解析：m＝10时，不满足条件，则m←10＋7.m＝17时

5、，Mod(m,3)＝2且Mod(m,5)＝2成立，故输出17.答案：172．下面一段伪代码的功能是________．m←2WhileMod(m,2)≠1　orMod(m,3)≠2　orMod(m,5)≠3m←m＋1EndWhilePrintm解析：由代码含义可知，m满足的条件是除以2余1，除以3余2，除以5余3，又m逐个增大，故输出的m是满足条件的最小正整数．答案：求关于x、y、z的不定方程组的最小正整数解[例2]　设计用辗转相除法求8251与6105的最大公约数的算法，并画出流程图，写出伪代码

6、．[思路点拨]　按照辗转相除法的步骤设计算法、画流程图，根据流程图，写出伪代码．[精解详析]　算法如下S1　a←8251；S2　b←6105；S3　如果Mod(a，b)≠0，那么转S4，否则转S7；S4　r←Mod(a，b)；S5　a←b；S6　b←r，转S3；S7　输出b.流程图与伪代码：　[一点通]　辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数．3．下图表示的流程图，输出的结果是________．解析：第一次执行循环体：r＝34，a＝119，b＝34，第二次执行循环体

7、r＝17，a＝34，b＝17.第三次执行循环体r＝0，输出b＝17.答案：174．求三个数168,56,264的最大公约数．解：先求168与56的最大公约数．∵168＝56×3，故168与56的最大公约数是56.再求56与264的最大公约数．∵264＝56×4＋40，56＝40×1＋16，40＝16×2＋8，16＝8×2.故56与264的最大公约数是8.因此168,56,264的最大公约数是8.[例3]　(12分)设计用二分法求方程x3－2＝0在区间[1,2]内的近似解(误差不超过0.005)的

8、流程图，写出伪代码．[思路点拨]　根据二分法求方程近似解的步骤画出流程图，然后根据流程图写出算法伪代码．[精解详析]　　流程图如图：　　　　(6分)伪代码如下：a←1b←2c←0.005Do　x0←f(a)←a3－2f(x0)←－2Iff(x0)＝0ThenExitDoIff(a)f(x0)<0Thenb←x0Elsea←x0EndIfUntil

9、a－b

10、