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

-1-1.4算法案例学习目标核心素养1.通过中国古代算法案例，体会中国古代数学对世界数学发展的贡献．2．能综合运用所学的算法知识解决实际问题，会用自然语言、流程图和伪代码表述问题的算法过程．(重点、难点)3．拓展视野，进一步感受算法的意义和价值.通过算法案例，培养学生发现、探索问题的能力，通过抽象、概括把实际问题转化为数学问题，提升学生的数学抽象、数学建模以及逻辑推理的数学核心素养.1．“孙子问题”是求关于x，y，z的一次不定方程组m＝3x＋2，m＝5y＋3，m＝7z＋2的正整数解．2．辗转相除法和更相减损术(1)欧几里得辗转相除法求两个正整数a，b的最大公约数的步骤是：计算出a÷b的余数r，若r＝0，则b即为a，b的最大公约数；若r≠0，则把前面的除数b作为新的被除数，把余数r作为新的除数，继续运算，直到余数为0，此时的除数即为a，b的最大公约数．(2)“更相减损术”是我国的《九章算术》中提到的一种求两个正数最大公约数的算法，它与“辗转相除法”相似．它的基本思想是：对于给定的两个数，以两个数中较大的数减去较小的数，然后将差和较小的数组成一对新数，再用两个数中较大的数减去较小的数，反复执行此步骤，直到产生一对相等的数为止，这个数就是原来两个数的最大公约数．3．Int(x)和Mod(x)函数(1)Int(x)表示不超过x的最大整数．例如：Int(5)＝5，Int23＝0，Int(3.6)＝3.(2)Mod(a，b)的意义是a除以b所得的余数，因此当Mod(a，b)＝0时，表示a能被b整除，当0Mod(a，b)b时，a不能被b整除，即b不是a的约数．4．利用“二分法”求方程f(x)＝0在区间[a，b]上的近似解的步骤S1取[a，b]的中点x0＝12(a＋b)，将区间一分为二；S2若f(x0)＝0，则x0就是方程的根；否则判断根x*在x0的左侧还是右侧：若f(a)f(x0)0，则x*∈(x0，b)，以x0代替a；-2-若f(a)f(x0)0，则x*∈(a，x0)，以x0代替b；S3若|a－b|c，计算终止，此时x*≈x0，否则转S1.1．两个整数490和910的最大公约数是________．70[∵910＝490×1＋420,490＝420×1＋70,420＝70×6＋0，∴490和910的最大公约数是70.]2．Mod(8,3)＝________.2[Mod(8,3)表示8除以3所得的余数．∵8＝2×3＋2，∴Mod(8,3)＝2.]3．若Int(x)表示不超过x的最大整数，对于下列等式：①Int(10.01)＝10；②Int(－1)＝－1；③Int(－5.2)＝－5.其中正确的有________个．2[①②正确，③错误．因为Int(x)表示的是不超过x的最大整数．所以Int(－5.2)＝－6.]4．用二分法求方程的近似解，误差不超过ε，则循环结构的终止条件是________．①|x1－x2|ε；②x1＝x2＝ε；③x1εx2；④|x1－x2|ε.④[依据用二分法求方程近似解时误差限制要求判断，④对．]孙子剩余定理的应用【例1】有3个连续的正整数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，画出求满足要求的一组三个连续正整数的流程图，并写出伪代码．思路点拨：设最小的正整数m，根据题意，m应同时满足3个条件：(1)m被15整除即Mod(m,15)＝0，(2)m＋1被17整除即Mod(m＋1,17)＝0，(3)m＋2被19整除即Mod(m＋2,19)＝0.首先，从m＝2开始检验条件，若3个条件中有任何一个不满足则m递增1.直到m同时满足3个条件时，输出m，m＋1，m＋2.因为要从m＝2开始反复验证，故需要用循环结构．[解]流程图：-3-伪代码：m←2WhileMod(m,15)≠0orMod(m＋1,17)≠0orMod(m＋2,19)≠0m←m＋1EndWhilePrintm，m＋1，m＋2解决此类问题的方法就是从m＝2开始，对每一个正整数逐一检验，当m满足所有已知条件时，结束循环，输出m.1．如图所示的流程图，输出的结果是________．17[m＝10时，不满足条件，则m←10＋7，m＝17时，Mod(m,3)＝2且Mod(m,5)＝2成-4-立，故输出17.]2．方程组3x＋4＝m，2y＋1＝m的整数解有________组．无数[消去m，得3x－2y＋3＝0，即x＝23y－1，只要y取3的整数倍，所得的解都符合题意．]求两个正整数的最大公约数【例2】设计用辗转相除法求8251与6105的最大公约数的算法，并画出流程图，写出伪代码．思路点拨：根据用辗转相除法求两个正整数的算法步骤写出解决此问题的算法，再转换为流程图和伪代码．[解]算法如下：S1a←8251；S2b←6105；S3如果Mod(a，b)≠0，那么转S4，否则转S7；S4r←Mod(a，b)；S5a←b；S6b←r，转S3；S7输出B．流程图与伪代码：-5-a←8251b←6105WhileModa，b≠0r←Moda，ba←bb←rEndWhilePrintb辗转相除法是用于求两个数的最大公约数的一种方法，这种方法由欧几里得在公元前300年左右首先提出，因而又叫“欧几里得辗转相除法”．辗转相除法的算法步骤(以求两个正整数a，b(ab)的最大公约数为例)为：S1输入两个正整数a，b；S2如果Mod(a，b)≠0，那么转S3，否则，转S6；S3r←Mod(a，b)；S4a←b；S5b←r，转S2；S6输出B．其流程图如图：-6-伪代码为：Reada，bWhileModa，b≠0r←Moda，ba←bb←rPrintb提醒：求两个正整数的最大公约数时，用辗转相除法进行设计的关键是：将“辗转”的过程用循环语句表示．为了避免求循环次数(对两个具体的正整数，循环次数可以求出，但会使程序更为复杂)，最好使用“While”语句．3．用辗转相除法求261和319的最大公约数．[解]319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝2(余0)，所以319与261的最大公约数为29.4．运行下面伪代码，当输入168,72时输出的结果是__________．Readm，nr←Modm，nm←nn←rUntilr＝EndPrintm24[伪代码是求168与72的最大公约数．]二分法求方程的近似解【例3】设计用二分法求方程x3－2＝0在区间[1,2]内的近似解(误差不超过0.005)的流程图，写出伪代码．思路点拨：依据二分法求方程的近似解的步骤设计出算法再转换成流程图和伪代码，设f(x)＝x3－2如图所示．-7-如果估计出方程f(x)＝0在某区间[a，b]内有一个根x*，就能用二分法搜索求得符合误差限制c的近似解．用自然语言表示算法如下：S1取[a，b]的中点x0＝12(a＋b)，将区间一分为二；S2若f(x0)＝0，则x0就是方程的根，否则判断根x*在x0的左侧还是右侧；若f(a)f(x0)0，则x*∈(x0，b)，以x0代替a；若f(a)f(x0)0，则x*∈(a，x0)，以x0代替b；S3若|a－b|c，计算终止，此时x*≈x0，否则转S1.[解]流程图如图所示：伪代码如下：-8-a←1b←2c←0.005Dox0←a＋bfa←a3－fx0←x30－Iffx0＝0Iffa*fx0b←x0a←x0Until|a－b|cPrintx01．用二分法求方程近似解，必须先判断方程在给定区间上是否有解．2．二分法的过程是一个多次重复的过程，故可用循环结构处理．3．二分法过程中需要对中点(端点)处函数值的符号进行判定，故实现算法需用选择结构，即用条件语句进行分支选择．5．用区间二分法求出方程3x＝5－x在区间[1,2]上的近似解(误差不超过0.001)，并写出这个算法的伪代码，画出流程图．[解]设f(x)＝3x＋x－5.伪代码如下：-9-a←1b←2c←0.001Dox0←a＋bfa←3a＋a－fx0←3x0＋x0－Iffx0＝0Iffafx0＜0b←x0a←x0Until|a－b|＜cPrintx0其流程图如图所示：1．本节课重点是会用孙子定理求一次不定方程组的解，会求两个数的最大公约数，用二分法求方程的近似解．2．求最大公约数的两种方法步骤-10-(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数．若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果.1．有一堆火柴棒，三根三根地数，最后余下一根；四根四根地数，最后余下两根；五根五根地数，最后余下四根．那么这堆火柴棒最少根数为()A．31B．34C．44D．54B[由题意知，本题实际上是求关于a，b，c的不定方程组的正整数解，即m＝3a＋1，m＝4b＋2，m＝5c＋4，得m的最小值为34.]2．4557与5115的最大公约数是________．93[因为5115＝4557×1＋558，4557＝558×8＋93,558＝93×6，所以4557与5115的最大公约数是93.]3．Mod(100,17)＝________.15[Mod(a，b)＝c表示b除a所得余数为C．100＝17×5＋15，故余数为15.]4．根据如图所示的流程图(其中[x]表示不大于x的最大整数)，可知输出r＝________.73[由流程图的算法原理可知：a＝5，b＝7，n＝1，n(b－a)＝7－51；n＝2，n(b－a)＝2(7－5)1；-11-n＝3，n(b－a)＝3(7－5)1，分子有理化得67＋563＋3＝1，此时，m＝[35]＝6，r＝m＋1n＝6＋13＝73，故输出r＝73.]