高中数学 第一章 算法初步 1_4 算法案例学案 苏教版必修3

1.4 算法案例学习目标1.理解解决“韩信点兵孙子问题”的算法思想；2.理解辗转相除法与更相减损术的数学原理；3.能用伪代码实现二分法求方程的近似解知识点一本节涉及的内置函数就像木工不必自己造锯一样，VB也把一些常用基础工具做成内置函数，以备使用者直接调用，下面是本节涉及的内置函数：函数功能例子Mod(a，b)得到a除以b的余数Mod(9，2)1Val()将字符串转换为数值Int(x)表示不超过x的最大整数Int(3.9)3知识点二“韩信点兵一孙子问题”的数学本质思考“三三数之剩二”是什么意思？如何用代数式表示？梳理“韩信点兵孙子问题”是求关于x，y，z的一次不定方程组_的正整数解知识点三辗转相除法与更相减损术的算法原理思考我们知道20485234.为什么204与85的最大公约数就是85与34的最大公约数？梳理一般地，有2种算法求两个正整数的最大公约数：(1)辗转相除法的运算步骤：第一步，给定_第二步，计算_第三步，_.第四步，若r0，则m，n的最大公约数等于_；否则，返回_(2)更相减损术的运算步骤：第一步，任意给定两个正整数，判断它们是否都是_若是，用_约简；若不是，执行_第二步，以_的数减去_的数，接着把所得的差与_的数比较，并以大数减小数，继续这个操作，直到所得的数_为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数知识点四二分法的实现思考你还能回忆起二分法的作用和原理吗？梳理求方程f(x)0在区间a，b上的近似解的步骤为：S1取a，b的中点x0(ab)，将区间一分为二S2若_，则x0就是方程的根，否则判断根x*在x0的左侧还是右侧：若_，则x*(x0，b)，以x0代替a；若_，则x*(a，x0)，以x0代替b.S3若|ab|b)的最大公约数的一个算法吗？并画出流程图，编写伪代码反思与感悟利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数跟踪训练2用辗转相除法和更相减损术求261和319的最大公约数类型三求方程f(x)0近似解的算法例3画出用区间二分法求方程x3x10在区间1，1.5上的一个近似解(误差不超过0.001)的一个算法流程图并编写伪代码反思与感悟在此算法中用到了条件语句和循环语句，所以用“Do”是因为要执行再判断是否满足条件，因为不知循环次数，所以也不宜用“For”语句跟踪训练3改造例3中伪代码，用来求f(x)ln x2x1在区间a，b上的一个近似解(误差不超过c)1m是一正整数，对两个正整数a，b，若ab是m的倍数，则称模m同余，用符号ab(Modm)表示则a5(Mod27)中，a的取值最小为_2用更相减损术求36与134的最大公约数，第一步应为_3求方程x5y3(其中y为自然数)的所有小于100的x的正整数解，用伪代码表示4求两个正数8 251和6 105的最大公约数1求两个正整数的最大公约数时，用辗转相除法进行设计的关键是：将“辗转”的过程用循环语句表示为了避免求循环次数(对两个具体的正整数，循环次数可以求出，但会使程序更为复杂)，最好使用“While”语句2用二分法求方程近似解，必须先判断方程在给定区间上是否有解3二分法的过程是一个多次重复的过程，故可用循环结构处理4二分法过程中需要对中点(端点)处函数值的符号进行判定，故实现算法需用选择结构，即用条件语句进行分支选择答案精析问题导学知识点二思考“三三数之剩二”意思是一堆东西，三个三个地分组，余二个设这堆东西数目为m，则m3x2，其中x指组数梳理知识点三思考设204与85的最大公约数为a，则a能整除204，故能整除85234.又因为a也是85的约数，故a能整除852，所以a必能整除34，即a是34的约数，从而是85与34的最大公约数，显然，204与85的公约数问题转化成了85与34的公约数问题，问题难度降低了梳理(1)两个正整数m，n(mn)m除以n所得的余数rmn，nrm第二步(2)偶数2第二步较大较小较小相等知识点四思考二分法是用来求方程近似解的，其原理是先确定一个解所在的大致区间，然后借助零点存在定理，不断缩小这个区间梳理f(x0)0f(a)f(x0)0f(a)f(x0)0x*x0S1题型探究例1解流程图为伪代码为m2While Mod(m，3)2 or Mod(m，5)3 or Mod(m，7)2mm1End WhilePrint m跟踪训练1解算法的伪代码如下：m2While Mod(m，5)2 or Mod(m，7)3 or Mod(m，9)4mm1End WhilePrint m例2解算法如下：S1输入两个正整数a，b；S2若Mod(a，b)0，那么转S3，否则转S6；S3rMod(a，b)；S4ab；S5br，转S2；S6输出b.流程图如图：伪代码如下：Read a，bWhile Mod(a，b)0rMod(a，b)abbrEnd WhilePrint b跟踪训练2解辗转相除法：3192611(余58)，261584(余29)，58292(余0)，所以319与261的最大公约数为29.更相减损术：31926158，26158203，20358145，1455887，875829，582929，29290，所以319与261的最大公约数是29.例3解流程图如图：伪代码如图：a1b1.5c0.001Dox0f(a)a3a1f(x0)x01If f(x0)0 Then Exit DoIf f(a)f(x0)0 Thenbx0Elseax0End IfUntil |ab|cEnd DoPrint x0跟踪训练3解伪代码如图：Reada，b，cDox0f(a)ln a2a1f(x0)ln x02x01Iff(x0)0ThenExitDoIff(a)f(x0)0Thenbx0Elseax0EndIfUntil|ab|cEndDoPrintx0当堂训练1322先除以2，得到18与67解析36与134都是偶数，第一步应为：先除以2，得到18与67.3解算法的伪代码如图：y0x0While x100x5y3Print xyy1End While4解8 2516 10512 146；6 1052 14621 813；2 1461