错解剖析得真知24

1、For personal use only in study and research; not for commercial use错解剖析得真知（四十）§ 13. 3算法案例一、知识导学1.算法设计思想：（1） “韩信点兵一孙子问题”对正整数m从2开始逐一检验条件，若三个条件中有任何一 个不满足，则 m递增1，一直到m同时满足三个条件为止（循环过程用Goto语句实现）（2） 用辗转相除法找出匸U的最大公约数的步骤是：计算出一；L：1的余数，若 I，则：为；的最大公约数；若5' I ,则把前面的除数一：作为新的被除数，继续运算，直到余数为0，此时的除数即为正整数 -'

2、;的最大公约数2.更相减损术的步骤：（1）任意给出两个正数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以 大数减小数继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公 约数（3）二分法求方程工I在区间打一内的一个近似解丄*的解题步骤可表示为L 知二丄0+占）S1取“'的中点 一，将区间一分为二；S2若，则就是方程的根；否则判别根在的左侧还是右侧：若儿】，爲" ，以代替；若；丄1血冷1-：匚，则'一以代替；S3若l'： '''J ：，计算终止，此时

3、'匕I ,否则转S1.二、疑难知识导析1. 工 门表示不超过:的整数部分，如-'：，1 -'Jr ""，但当是负数时极易出错，如 二- 一、巴一 一-就是错误的，应为-2.2. 表示必除以B所得的余数，也可用l! mod力表示.3 .辗转相除法与更相减损术求最大公约数的联系与区别：(1) 都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显(2) 从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术 则以减数与差相等而得到

4、4.用二分法求方程近似解，必须先判断方程在给定区间；'上是否有解，即连续且满足.并在二分搜索过程中需对中点处函数值的符号进行多次循环判定，故需要选择结构、循环结构，即可用 Goto语句和条件语句实现算法三、经典例题导讲例 1血(了汀)二，血二,mod(6N9)= 45 mod 7=A. 16, -1 , 4, 3B.15, 0, 4, 3C.15,-1,3,4D.15,-1,4,3错解：根据工 门表示不超过:.的整数部分，豊二心川；表示“除以匚所得的余数 选择B.错因：对九表示的含义理解不透彻，将不超过-0.05的整数错认为是0,将负数的大小比较 与正数的大小比较相混淆正解：不超过-0

5、.05的整数是-1,所以答案为D.例2所谓同构数是指此数的平方数的最后几位与该数相等.请设计一算法判断一个大于0且小于1000的整数是否为同构数错解：算法思想：求出输入数的平方，考虑其个位或最后两位或最后三位与输入数是否相 等，若相等，则为同构数Read xIf /or -or :ThenPrint xEnd ifEnd错因：在表示个位或最后两位或最后三位出现错误，“/”仅表示除，y/10,y/100,y/1000都仅仅表示商.正解：可用-T，- - '' ' ' 1-1- -'"来表示个位，最后两位以及最后三位.Read xIf匕or111

6、orThenPrint xEnd ifEnd例3孙子算经中的“物不知数”问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？ ”可以用下面的算法解决：先在纸上写上2,每次加3,加成5除余3的时候停下来，再在这个数上每次加 15,到得出7除2的时候，就是答数.试用流程图和伪代码表示这一算法解：流程图为：伪代码为：10 220 :匚30 If二，丁 - Then Goto 2040 If二二ThenPrintmGoto8050 End if60亡+、70 Goto 4080 End点评：这是孙子思想的体现，主要是依次满足三个整除条件例4分别用辗转相除法、更相减损法求192与

7、81的最大公约数解：辗转相除法：S1S281- 30= 221S33021=19S4229 = 23S59 门二 3故3是192与81的最大公约数.更相减损法：S1192-81 = 111S2111-81=30S381-30 = 51S451-30 = 2155 J56 ：二57 I58 -:59 .-故3是192与81的最大公约数.点评：辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次 数相对较少辗转相除法是当大数被小数整除时停止除法运算，此时的小数就是两者的最大 公约数，更相减损术是当大数减去小数的差等于小数时减法停止，较小的数就是最大公约数例5为了设计用区间二分法求

8、方程 .： 一 - I在0，1上的一个近似解（误差不超过0.001）的算法，流程图的各个框图如下所示，请重新排列各框图，并用带箭头的流线和判断符,并写出其伪代码.（其中分别表示区间的左右端图 13-3-2图 13-3-3号“ Y”、“ N'组成正确的算法流程图点）流程图为伪代码为10 Read20心 (a +A)/230台 / +圧-14050If': Then Goto 12060If" Then70100End if80Else90100End if110 If -0.001 Then Goto 20120 Print '130 End点评：二分法的基本思

9、想在必修一中已渗透，这里运用算法将二分法求方程近似解的步骤更清晰的表述出来例6用秦九韶算法计算多项式在:'- 时的值时，1的值为解：根据秦九韶算法，此多项式可变形为/M = x«X+5)+6)+79)-8)+35)+12按照从内到外的顺序，依次计算一次多项式当，.-时的值: 故当- T时多项式的值为 J 点评：秦九韶算法的关键是 n次多项式的变形把一个次多项式-' 'L ' ' 71; ' ' I改写成_ .求多项式的值，首先计算最内层括号内一次多项式的值， 然后由内向外逐层计算一次多项式的值，这样把求1次多项式的值问题转化为求

10、1个一次多项式的值的问题，这种方法成为秦九韶算法这种算法中有反复执行的步骤，因此，可考虑用循环结构实现四、典型习题导练1.以下短文摘自古代孙子算经一书，其引申出的“大衍求一术”称为“中国剩余原理”：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？ ”答曰()A.二一 B. 二十二 C. 二十三D.二十四2用辗转相除法求52与39的最大公约数的循环次数为()A. 1次B.2次C.3次D.5次3下面程序功能是统计随机产生的十个两位正整数中偶数和奇数的个数，并求出偶数与奇 数各自的总和.For I from 1 to 10Print x;IfThenElseEnd IfEnd

11、forPrintPrint“奇数个数=”；一，“偶数个数=”；4若一个数的各因子之和正好等于该数本身，则该数成为完数请补充完整下列找出1100之间的所有完数的伪代码For 丿 from 2 to 100For b from 2 to If mod(a,b)=0 ThenEnd ifEnd ForIf The nPrint aEnd ifEnd ForEnd5设计求被9除余4,被11除余3的最小正整数的算法，画出流程图，写出伪代码6.利用辗转相除法或更相减损术求324,243,135的最大公约数.仅供个人用于学习、研究；不得用于商业用途For personal use only in study and research; not for commercial use.Nur f u r den pers?nlichen f u r Studien, Forschung, zu kommerziellen Zwecken verwendet werden.Pour l ' e tude et