第8课时习题课9.算法案例韩信点兵--孙子问题.doc

第8课时习题课（1）【双基演练】1下面的程序运行的结果是 （C）N0I0WhileI30I（I1）（I1）NN1EndPrintNEndA0B3C4D29提示：将初始值I0代入，求得新I1，N变成1，这是第1次循环；130，符合循环条件，第2次循环时，I变为4，N取值为2；4=0 then Y=6 Else Y=5 (End if) Print Y End提示：条件语句的终止需要说明。3.按下面的程序运行后输出的S的值是。 (120)ForI1TO5 S=0 J=1 For K=1 To I J=J*K End For S=S+J End For Print S End提示：此程序分内、外两层两个循环，由于外循环每一次都使J1，S0，故只要考虑最后一次循环，即I5时，分别计算了J12345120，故S0J120。4.下面的程序段中，语句Print I*J 的执行次数是。 (15)For I=1 To 3 For j=5 To 1 Step -1 Print I*J End For End For提示：对于每一个I，内循环都执行5次，而I分别取1,2，3，故PrintI*J共执行15次。【范例解读】1输入三角形的三边长，判断能否构成一个三角形。试用伪代码表示这个算法。解流程图输入a,b,ca+bcYN输出“不能构成三角形”b+caNa+cbNYY输出“能构成三角形” 程序：Reada,b,c If a+b=c then Print “不能构成三角形”ElseIf b+c=a then Print “不能构成三角形”ElseIfa+c2004成立的最小正整数n的算法过程。n1sum0Sum=2004N输出nYnn+1sumsum+n2解流程图 程序：n1 sum0 While sum50NY输出k解 流程图：伪代码：k=0 For i form 1 to 50 Read ai If Mod(ai,2)0 Then kk+1 End if End for Print k End【测试反馈】1下列程序的运行结果是 （C）A5B4IfB=AThenBABElseBAB End ifPrintBEndA9B4C1D0提示：条件不成立，执行ELSE分支，B被赋值为AB1，选C。2下面的程序运行时输出的结果是 （D） I1S0 While I5时为止，于是，共循环5次，Y输出结果为6。4.下列程序的运行结果是。 （13i1i）A1B2C10DBB4ACIfD=0 Then X1(-B+SQR(D)/(2*A) X2(-B-SQR(D)/(2*A) Print “X1=”; X1,“X2”；X2ElsePrint“X1”；B/（2A）；“”；SQR（D）/（2A）；“i”，Print“X2”；B/（2A）；“”；SQR（D）/（2A）；“i”EndifEnd(注：Print “A”表示将字符A打印出来)提示：这个程序是求方程x2+2x+10=0的根，由于判别式小于0，此方程无实数根，这里输出的是这个方程的虚数根（感兴趣的同学以后可以选修“复数”的有关内容）。注意：其中SQR（X）为取X的平方根。5按下列程序运行后的结果是。 (4)XY10 If XY100 Then AA+1 Else If XY50 Then AA+2 Else AA+4 End If End If Print A End提示：由于不符合循环的条件，应执行ELSE分支，而此分支中的条件也不满足，又应执行它的ELSE分支，故A被赋值为4。6求出所有能被7整除的两位数。用伪代码表示算法过程。解 For I for 10 to 99 IF Mod(I, 7)=0 then Print I End if End for End7某牛奶厂2002年初有资金1000万元，由于引进了先进生产设备，资金年平均增长率可达到50%。试设计一个算法，计算这家牛奶厂2008年底的资金总额。解由于每年的资金都在前一年的基础上增长50%，所以可以用循环语句设计算法。伪代码：A1000For I=1 to 6 AA(1+0.5) End for Print A End第9课时算法案例（韩信点兵孙子问题）【教法建议】1通过韩信点兵的传说激发学习兴趣，并通过孙子算经进行数学文化的渗透。“孙子问题”或“中国剩余定理”的意义可以用以下的数学游戏来表达：有一堆火柴棒，三根三根地数，最后余下两根(即被3除余2，下同)，五根五根地数，最后余下三根，七根七根地数，最后也余下两根，问这堆火柴可能是多少根？1592年明朝程大位的算法统宗里有一首“数学诗”暗示了“孙子问题”的一种解法（见习题8）2中国剩余定理的完整阐述，是我国南宋数学家秦九韶作出的，他发明了著名的“大衍求一术”，这是解决一次同余式组问题的关键，在计算上很有价值关于“大衍求一术”。3案例1的计算机解决并不困难，只要使用循环，由小到大搜索即可关键是判断的条件要用到整除的一些性质和记法，如用int(x)表示不超过x的整数部分，用mod(a, b)表示a除以b所得的余数等，这些术语和符号学生初次接触，并不容易理解在教学时可增加一些辅助性练习【问题情境】1int(3.26)= ； (3) int(0.35)= ； (0)int (-3.26) = . (-4)2mod(23,7) = ； (2)mod(7,23) = . (7)【范例解读】例1设计求6除余4,10除余8，9除余4的最小正整数的算法，画出流程图，写出伪代码。解流程图 除了按教材中的方法外，也可用下面的算法：n1mod(n,6)=4mod(n,10)=8mod(n,9)=4输出nYYYNNNnn+1伪代码10 n1 20 If mod(n,6)=4 then 30 If mod(n,10)=8 then 40 If mod(n,9)=4 then 50 Print n Else nn+1 60 Goto 20 End if Else nn+1 70 Goto 20 End if Else nn+1 80 Goto 20 End if 90 End例2孙子算经中的“物不知数”问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”可以用下面的算法解决：先在纸上写上2，每次加3，加成5除余3的时候停下来，再在这个数上每次加15，到得出7除余2的时候，就是答数。将这一算法用流程图表示。解2每次加3，能保证始终是3的倍数多2，到5除余3时就是3除余2用5除余3的数了。在每次加15时，也还保持3除余2且5除余3的性质，到7除余2时自然就满足所有的条件了。流程图m2mm+3mod(m,5)3YNmm+15mod(m,7)=2Y输出mN可让学生思考：（1） 用伪代码表示上述算法；（2） 如何用这种方法求最小解？【归纳点拔】书中介绍的处理孙子问题的算法思想主要有以下几点：1对正整数从2开始逐一检验（循环过程用Goto语句实现）；2对三个条件逐一检验（条件语句）。【测试反馈】1下列各数中，被2，3，5除都余1的正整数是（D）A9B11C14D312m是一正整数，对两个正整数a,b，若a-b是m的倍数，则称a、b对模m同余，用符号ab(modm)表示。则下列各式中(1) 127（mod5）;(2) 2110(mod3);(3) 3420(mod2);(4) 477(mod40).其中正确的有 （C）A1个B2个C3个D4个提示：（1）、（3）、（4）正确。3mod(35,12)= . (11)提示：mo35除以12的余数。4int(4p)= . （12）提示：int(x)是取x的整数部分。5设计求被7除余2，被9除余5的最小正整数的算法，画出流程图，写出伪代码。m2mod(m,7)2mod(m,9)5输出mmm+1YYNN解流程图伪代码10m2 20 If mod(m,7)2 then 60 30 If mod(m,9)5 then 60 40 Print m 50 Goto 80 60 mm+1 70 Goto 20 80 Dnd if6事实上，如果韩信点兵的传说是真事的话，用任何方法只能得到最小解和通解（最小解加上3，5，7的公倍数），韩信是如果得到具体的、精确的解的呢？在已知最小解为23的条件下，如果韩信知道总人数大约在2310到2400之间，请设计算法替韩信确定具体人数。解应该事先知道总数的范围。m2mm+3mod(m,5)3YNmm+15mod(m,7)=2Y输出mN因为3，5,7的最小公倍数为105，故所有解都具有105m23的形式，故只要在2310到2400之间找到具有这种形式的数即可。伪代码10 m1 20 M105m+23 30 If 2310=Mb0，ra mod b，则a与b的最大公约数是（D）Ar BbCb-r Db与r的最大公约数提示：根据辗转相除法的算法思想，就是将较大的数的最大分约数转化为较小的数的最大公约数。3已知a=333,b=24，则使得a=bq+r，（q，r均为自然数，且0rb）成立的q和r的值分别为。 (q=13,r=21)提示：用333除以24，商即为q，余数就是r。4用辗转相除法与更相减损法求333与24的最大公约数时的循环次数分别为。(辗转相除法需要3次循环，更相减损法需要21次循环)5设计一个算法，计算两个正整数a,b的最小公倍数，并将此算法用流程图表示。解算法设计思想：对正整数逐一进行检验。可用程序框图表示输入a,bmod(n,a)=0n=1n=n+1NYNmod(n,b)=0Y输出n6根据更相减损法的思想，设计求两个正整数a,b的最大公约数的算法过程，并画出程序框图，写出伪代码。解不妨设ab.输入a,br=a-br=0输出bYNa=Max(b,r)b=Min(b,r)7编制一个程序，求出前100个正整数中的所有素数。解算法设计思想：因为1和100都不是素数，故可从2开始，对299这98个自然数逐一进行检验。在对某个正整数k进行检验时，可对从2到k1逐一检验其是否为的约数。k=3i=2k MOD i=0Yk=k+1+=1k=100NNi=100Nk=k+1Y结束输出2Y程序框图 8编程输出十位数字与个位数字的和能被7整除，百位数字与十位数字的和能被3整除的所有3位数。解程序： For I form 1 to 9 For J from 0 to 9 For K from 0 to 9 If mod(J+K,7)=0,(I+J)mod(I+J,3)=0 then Print I*100+J*10+K End if End if End if End if第11课时算法案例（二分法）【教法建议】1案例3介绍的“二分法”是方程求根的一种常用方法本例也是第2章用二分法求方程近似解的拓展和深化教学中要引导学生从已有的知识出发，建立起解决问题的算法，并激发将算法程序化的兴趣，鼓励用计算机、计算器进行操作实习。2因为没有函数连续性的概念，对使用“二分法”求解一元方程f(x) = 0的前提条件：先判断根所在的范围a，b，若f(x)连续，且满足f(a)f(b) 0，那么方程f(x) = 0在(a，b)上至少有一个根，要学生有所了解，但连续性的概念不必介绍。3可适当复习相关知识（如函数、方程等），以克服学习过程中的障碍。分析问题时要结合图形进行。4“二分法”是一种有着广泛应用的方法，如本章第一节中的猜数游戏、数学家华罗庚“优选法”中的“中点法”等。可适当作些介绍。【问题情境】1若方程ax+2a-1=0在（1,1）上有且只有一个实数解，求a的取值范围。解设f(x)=ax+2a-1,则由函数图象可以看出，方程方程ax+2a-1=0在（1,1）上有且只有一个实数解的充分必要条件是f(-1)f(1)0,由此可得：（a-1）(3a-1)0,解得a1.2函数f(x)的图象在（0,1）上是不间断的，并且已知方程f(x)=0在（0,1）上有且只有一个解x0，如何判定x0是距0近还是距1近呢？解如果函数f(x)的图象在（0,1）上是不间断的，那么，只要看f(0),f(1)与f()的符号：若f()与f(0)异号，则x0与0较近，若f()与f(1)异号，则x0与1较近。【范例解读】例1华罗庚的“优选法”中也有一种叫做“二分法”的方法。现以实例加以说明：发现在A、B两地之间的电线发生断路现象，为了找到断点（假设只有一个断点），可先在AB中点C1处测试AC1和C1B是否通电，若发现AC1通电，C1B不通电，则又在C1B的中点C2处测试C1C2和C2B是否通电，如此下去。试将上述操作步骤用流程图表示。取AB中点C1，测AC1与C1B是否断电断电的线路两端点分别取作A、B点已找到断点结束YN解例2用二分法求方程lgx+x=3的近似解（误差不超过0.001），将解决这个问题的过程用流程图和伪代码表示。解即求方程lgx +x-3= 0的近似解。设f(x)=lgx +x-3，因为f(x)单调递增，且f(1)= -20，所以方程lgx +x-3= 0的解在（1,3）上。用二分法求这个方程的近似解的流程图：x0(a+b)f(a)lga+a-3f(x0)lgx0+x0-3f(a)f(x0)0NYbx0ax0|a-b|0.001输出x0YNa1b3f(x0)=0NY伪代码10 a1 b3 20 x0(a+b)/2 30 f(a)lga+a-3 40 f(x0)lgx0+x0-3 50 If f(x0)=0 then Goto 120 60 If f(a)f(x0)=0.001 then Goto 20 120 Print x0【归纳点拔】1用二分法求方程近似解，必须先判断方程在给定区间上是否有解。2二分搜索的过程是一个多次重复的过程，故可用循环结构处理，教材中运用Goto语句实现循环。3二分搜索过程中需要对中点（端点）处函数值的符号进行判定，故实现算法需用选择结构，即用条件语句进行分支选择。【测试反馈】1对下列说法 （A）（1）若函数f(x)满足f(-1)f(1)0),若f(0)0，则 （C）Af(x)0没有实数根Bf(x)=0两根同号Cf(x)0有一个正根和一个负根Df(x)=0可能没有实数根提示：函数图象开口向上，而图象上又存在在x轴下方的点，并且函数图象没有间断点。3用计算器根据二分法求方程=+1在（2,3）之间的根，使误差不超过0.1，需要取次中点。解设f(x)= - -1f(2)-0.0860,|2.5-2|=0.50.1;f(2.25)0.0560,|2.25-2|=0.250.1;f(2.125)-0.013,|2.25-2.125|=0.1250.1;f(2.1875)0.022,|2.125-1.1875|=0.06250.1.符合条件。共取了4次中点。4对上题中的方程，满足条件的根为。（近似解可取为2.1875）5用流程图表示用二分法求方程= +1在（2,3）之间的根（误差不超过0.001）的算法过程，并写出伪代码。解设f(x)= - -1,x1(a+b)f(a)- -1,f(x0)- -1,f(a)f(x0)0NYbx1ax1|a-b|0.001输出x0YNa2b3f(x0)=0NY伪代码10 a1 b3 20 x0(a+b)/2 30 f(a)- -1, 40 f(x0)- -1, 50 If f(x0)=0 then Goto 120 60 If f(a)f(x0)=0.001 then Goto 20 120 Print x06求证：方程5x2-7x-1=0的一个根在区间（1,0）内，另一个根在区间（1,2）内。证明设f(x)=5x2-7x-1，因为f(x)的图象在整个实数集范围内都没有间断点，且f(-1)=110,f(0)=-10,所以方程f(x)0在（1,2）内有一个实数解。7判定方程3x=x+4所在的区间，并用二分法求这个方程的近似解（误差不超过0.01）.(可以使用计算器或计算机)解设f(x)=3x-x-4，从函数图象可以看出，这个方程有两个解，并可估计其大致范围。因为f(-4)0,f(-3)0,故有根在（4，3）内；因为f(1)=-20,故有一根在（1,2）内。用计算器可以求得近似解x1-3.99,x21.56.8画出解决上述问题的流程图，并用伪代码表示这个算法。解类似于第5题，过程略。第12课时习题课（2）【双基演练】1下面的算法的功能是 （A）开始输入一个数据aa=32Y输出aN将a用下一数据赋值是否还有数据N结束A查找出一组数据中是否有32B将一组数据中的第32个数打印出来B判断32是一组数据中第几个数D找出一组数据中从小到大排列时第32个数提示：根据判断框中的条件，a32时即输出可知应选A。2用辗转相除法求36与24的最大公约数时的循环次数为 (B)A1次B2次C3次D4次3int(-3.14)=；mod(72,13)。4下面的程序是计算当x3时，多项式f(x)= 的值。（f(x)=x3+x2+2x+3） F= -3For I=1 To 3 FF(-3)+I End ForPrintFEnd提示：第一次循环：F1(-3)+1；第二次循环：F（3）1（3）2（3）2（3）2；第三次循环：F（3）3（3）22（3）3。【范例解读】例1写出一个在三个数a,b和c中找出第2个小数的算法（假设a,b,c互不相同），写出表示这个算法的伪代码。解实际上就是将a,b和c排序后，取中间一个数。故可用第4题中的方法先排序，再将中间一个数输出。程序：Reada，b，cIfbathen t=a a=b b=t End if If ca then t = a a = c c = t End if If cb then t = b b = c c = t End if Print b End例2设计一个算法，将一组数按从小到大的顺序排列起来。请用流程图表示这个算法。输入这组数确定最小数输出最小数由剔除最小数后的所有数构成新的一组数数组中只有一个数NY结束输出这个数解 例3形如1（nN）的数称为“费玛数”。著名数学家费玛认为，这种形式的数都是素数。试设计一个算法证明费玛的这一猜想是错误的。画出流程图。n1是素数nn+1YN“猜想错误！”解从正整数1开始逐步检验：注：对素数的验证程序前面已有介绍。可运用这种程序写出完成本算法的伪代码。【测试反馈】1下面程序运行后输出的结果是 （C）X5S0For I= -X To X S=S+1 Next I Print S End A6B10C11D12提示：I从5到5共循环了11次，S从0开始每次加1,11次后结果为11。2阅读下面的程序 （C）Read xIf 9x and xathen t=a a=b b=t End if If ca then t = (a) a = (c) c = (t) End if If cb then t = (b) b = (c) c = (t) End if PRINT a，b，c End6画出流程图，用二分法求方程1.3x3-26.013x2+0.975x-19.50975=0在（20,30）之间的近似根（误差不超过0.005）。解设f(x)= 1.3x3-26.013x2+0.975x-19.50975,本题与第11课时例2完全类同，略。7某人40足岁时参加养老保险，保险公司规定：40足岁起每年缴费437元，一直缴到59足岁为止；从60足岁起每年领取养老金1200元。设预期寿命为75岁，银行年利率为7.47%。用秦九韶算法设计求该人到75岁时所得到的养老金的本息之和。解该人到75岁时所得到的养老金的本息和为S1200（17.47%）15+1200(1+7.47%)14+1200。据此设计下述算法：x10.0747 S1For I form 1 to 15SxS+1 End forS1200S PRINT S END第13课时复习课1下面程序的功能是 （A）n0 Read x1,x2,x10 For I from 1 To 10 If xI=10 then value=5x else value=4x A 100 B 80 C 90 D70提示：x取值满足条件，执行THEN分支，value=5x=100。5十进制表达式：3512764485的运算结果，用二进制表示为（B）A10111100101B11111100101C11110100101D11111101101提示：先求出这个10进制数，再用k余除法反向取余。6将求两个十进制数的和的标准方法描述成一个算法，这个算法中一定包含 （D）A输入、输出语句和循环语句B输入、输出语句和条件语句C赋值语句、循环语句和条件语句D输入、输出语句、赋值语句和条件语句提示：因为要输入这个十进制数，计算后的结果也需输出，故算法中一定包含输入、输出语句。因为求和时有进位和不进位之分，故应有条件语句。运算的结果要赋值于某变量。7下面和程序框图的功能是。(求a,b中较大数的平方值)开始输入a,babb2sa2s输出s结束YN8用输入、输出语句和赋值语句表示下式的计算过程:已知a,b和c的值，求y=ab3+5(1+c2)的值。解Reada,b,c yab3+5(1+c2) Print yEnd9请看下面的程序S0I0WHILESEii+112按照下列程序y=0 IF x0 THEN y=5 ELSE IF x10 THEN y=10 IF x100 THEN y=100 END IF ELSE y=200 END IF END IF当x=80时，运行的结果是， (200)当x5时，运行的结果是。 (100)13根据下面的程序框图，用伪代码表示这个程序框图所表示的算法。开始x0=2x1=|x1-x0|10-4x0=x1YN打印