2017-2018版高中数学第一章算法初步1.4算法案例学案苏教版必修3

1、1.4 算法案例【学习目标】1.理解解决“韩信点兵一孙子问题”的算法思想；2.理解辗转相除法与更相减损术的数学原理；3.能用伪代码实现二分法求方程的近似解.IF问题导学-知识点一本节涉及的内置函数就像木工不必自己造锯一样，VB 也把一些常用基础工具做成内置函数，以备使用者直接调用,下面是本节涉及的内置函数：函数功能例子Mod(a，b)得到a除以b的余数Mod(9，2) = 1Val()将字符串转换为数值Int(x)表示不超过x的最大整数In t(3.9)= 3知识点二“韩信点兵一孙子问题”的数学本质思考“三三数之剩二”是什么意思？如何用代数式表示?梳理“韩信点兵一孙子问题”是求关于x,y,z的

2、一次不定方程组 _ 的正整数解.知识点三辗转相除法与更相减损术的算法原理思考 我们知道 204 = 85X2+ 34.为什么 204 与 85 的最大公约数就是 85 与 34 的最大公约 数？梳理 一般地，有 2 种算法求两个正整数的最大公约数：(1) 辗转相除法的运算步骤：第一步，给定_ .第二步，计算_ .第三步，_.第四步，若r= 0,则m n的最大公约数等于 _;否则，返回_.(2) 更相减损术的运算步骤：第一步，任意给定两个正整数，判断它们是否都是 _若是，用_约简；若不是，执2行_.第二步，以_的数减去_ 的数，接着把所得的差与 _ 的数比较，并以大数减小数，继续这个操作，直到所

3、得的数 _ 为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.知识点四 二分法的实现思考 你还能回忆起二分法的作用和原理吗？梳理 求方程f(x) = 0 在区间a,b上的近似解的步骤为：1S1 取a,b的中点xo= 2(a+b)，将区间一分为二.S2 若_ ，则xo就是方程的根，否则判断根x*在xo的左侧还是右侧:若_ ，贝Ux*(xo,b)，以xo代替a;若_ ，贝Ux*(a,xo)，以xo代替b.S3 若|ab|b)的最大公约数的一个算法吗？并画出流程图，编写伪代码.反思与感悟 利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数

4、不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.跟踪训练 2 用辗转相除法和更相减损术求 261 和 319 的最大公约数.类型三 求方程f(x) = 0 近似解的算法例 3 画出用区间二分法求方程x3X 1 = 0 在区间1 , 1.5上的一个近似解(误差不超过0.001)的一个算法流程图并编写伪代码.反思与感悟在此算法中用到了条件语句和循环语句，所以用“Do”是因为要执行再判断是否满足条件，因为不知循环次数，所以也不宜用“For ”语句.跟踪训练 3 改造例 3 中伪代码，用来求f(x) = Inx+ 2x 1 在区间a

5、,b上的一个近似解(误 差不超过c) 1. m是一正整数，对两个正整数a, b,若ab是m的倍数，则称模m同余，用符号a=b(Modn) 表示.则a三 5(Mod27)中，a的取值最小为 _ .2 .用更相减损术求 36 与 134 的最大公约数，第一步应为 _.当堂训练43.求方程x= 5y+ 3（其中y为自然数）的所有小于 100 的x的正整数解，用伪代码表示.4 .求两个正数 8 251 和 6 105 的最大公约数.规律与方法-1 .求两个正整数的最大公约数时，用辗转相除法进行设计的关键是：将“辗转”的过程用循环语句表示.为了避免求循环次数（对两个具体的正整数，循环次数可以求出，但会使

6、程序更为复杂），最好使用“ While ”语句.2 用二分法求方程近似解，必须先判断方程在给定区间上是否有解.3 二分法的过程是一个多次重复的过程，故可用循环结构处理.4.二分法过程中需要对中点（端点）处函数值的符号进行判定，故实现算法需用选择结构，即用条件语句进行分支选择.5合案精析问题导学知识点二思考“三三数之剩二”意思是一堆东西，三个三个地分组，余二个.设这堆东西数目为m则m=3x+ 2,其中x指组数.m= 3x + 2,梳理m= 5y+ 3,m= 7z+ 2知识点三思考 设 204 与 85 的最大公约数为a,则a能整除 204,故能整除 85X2+ 34.又因为a也是 85 的约数，

7、故a能整除 85X2,所以a必能整除 34,即a是 34 的约数，从而是 85 与 34 的 最大公约数，显然，204与 85 的公约数问题转化成了85 与 34 的公约数问题，问题难度降低了.梳理两个正整数m n(nn)m除以n所得的余数r m- n,nrm第二步偶数 2 第二步较大较小较小相等知识点四思考 二分法是用来求方程近似解的，其原理是先确定一个解所在的大致区间，然后借助零 点存在定理，不断缩小这个区间.梳理f(x。)= 0f(a)f(xo)Of(a)f(xo)0XXoS1题型探究例 1 解流程图为6伪代码为vm2While Mod(m,3)工 2 orMod(m,5)丰3 orMo

8、d(m,7)工2vm- 1End WhilePrintm跟踪训练 1 解算法的伪代码如下:m2While Mod(n,5)丰2 orMod(m,7)丰3 orMod(m,9)工4mm1End WhilePrintm例 2 解算法如下:S1 输入两个正整数a,b；52若 Mod(a，b)工 0,那么转 S3,否则转 S6;53rJMod(a,b)；54ajb；55bJr,转 S2；S6 输出b.流程图如图:7伪代码如下:Reada,biih k.vi a,b丰0r Ta,babbrEnd WhilePrintb跟踪训练 2 解辗转相除法：319- 261= 1（余 58）,261 - 58= 4

9、（余 29）,58-29= 2（余 0）,所以 319 与 261 的最大公约数为 29. 更相减损术：319 261 = 58,261 58= 203,203 58= 145,145 58= 87,87 58= 29,58 29= 29,29 29= 0,所以 319 与 261 的最大公约数是 29.例 3 解流程图如图：8伪代码如图:a1b1.5c0.0 01DoDoThe nb-X0ElseaX0End IfUn til |ab|cEnd Do/输出心/Iff a f xo0X0(a b)fX03x0X0 1IffX0= 0 The n Exit9Printxo跟踪训练 3 解伪代码如图:Reada,b,cDof a Ina+ 2a- 1fX0 lnX0+ 2x0 1Iff X0= 0 The n Exit DoIff a f X00 ThenbX0ElseaX0End IfUn til|ab|cEnd DoPrintX0当堂训练1 . 322 .先除以 2，得到 18 与 67解析/ 36 与 134 都是偶数，.第一步应为：先除以 2，得到 18 与 67.3 .解算法的伪代码如图：y0 x0Whilex100 x5y+ 3Printxyy+ 1End