当前位置:首页 >> 数学 >>

1.3算法案例


为您服务教育网

http://www.wsbedu.com/

1.3

算法案例

[学习目标导航] 学习提示 1. 通过对中国古代算法研究的学习,了解中国古代伟大的文化成就, 重点是进位制,用算法设计 增强民族自豪感. 程序;难点是在程序设计中用好 2.通过对算法案例的学习,进一步理解算法的思想,能够用程序来解 三种基本的逻辑结构. 决生活中常见的数学问题. 3.理解进位制,能进行各种进位制之间的相互转化. [教材优化全析] 全析提示 我们通过程序框图形象、直观地表示算法,因此,在编制程序前,先 程序框图比自然语言的描述 绘出程序框图, 能使思路清晰, 并且对于三种基本的逻辑结构: 顺序结构、 更容易理解.一般说来,设计程序 条件结构、循环结构的脉络表达准确,有助于我们准确写出程序语言. 时,先画程序框图比较好. (一)教材上介绍了辗转相除法(欧几里得算法) ,求两个数的最大 公约数,其基本步骤是带余除法 m=nq+r(0≤r<n) ,反复执行,直到余 数 r=0 为止.求任意两个数的最大公约数的算法是: 第一步:输入两个正整数 a,b(a>b) ; 举例说明. 第二步:求出 a÷b 的余数 r; m=90,n=36, 第三步:令 a=b,b=r,若 r≠0,重复第二步; m=2n+18,r=18. 第四步:输出最大公约数 a. 令 m=36, n=18. 相应的程序框图是: 又有 36=18×2, 即 m=2n, 此时 r=0. 令 m=18,n=0. 故最大公约数为 18. 两个数 a, 的最大公约数一 b 开 始 般写成(a,b) ,如 90 与 36 的最 大公约数为 18,写成(90,36) 输 入 a,b(a> b) =18.
求 a÷ b的 余 数 r a=b b=r

r= 0 ?




输 出 a 结 束

“更相减损术”是我国古代求最大公约数的方法,反映了我国古代劳 动人民的伟大智慧,让我们感到无比的光荣与自豪. 其程序语言是: INPUT “请输入两个正整数 a,b:;a,b ” PRINT a;b; WHILE a<>b IF a>=b THEN a=a-b ELSE b=b-a
第 1 页 共 10 页

如求 78 与 36 的最大公约数, 简单写成: (78,36)→(42,36)→ (36,6)→(30,6)→(24,6) →(18,6)→(12,6)→(6,6) 故(78,36)=6. 如两个数都为偶数,也可以 先提取 2,再用此法. PRINT a;b;表示与下一

为您服务教育网

http://www.wsbedu.com/

PRINT END (二) 秦九韶算法求多项式的函数值, 在算法上减少了求乘法的次数, 使计算量减少,并且逻辑结构简单.这种算法避免了对自变量单独作幂的 计算,转而与系数一起逐次增长幂次,从而提高了计算精度.这也是我国 古代劳动人民智慧的结晶,是我国伟大国库中的瑰宝. 例如,求五次多项式 f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0,当 x=x0 (x0 为任意实数)时的值的程序语言是: INPUT “请输入自变量 x0 的值:;x0 ” INPUT “请输入最高次项系数 a5 的值:;a5 ” V=a5 n=1 WHILE n<=5 INPUT “请输入下一次的系数的值:;b ” V=V*x0+b n=n+1 WEND PRINT “函数值是:;V ” END (三)排序是日常生活中最常见的一项活动,就是按照一定的规则, 对数据加以排列整理,从而提高查找效率. 教材上介绍的直接插入排序是人们最容易想到, 也是最容易实现的方 法. 教材上介绍的冒泡排序法, 非常形象地描述了较小的数像气泡一样逐 趟向上飘浮,一直到最小的数浮到最上面,然后是逐渐增大的数.在这里 要特别理解“一趟”的意义,它可能有多次交换.如果一趟排序交换次数 为 0,说明排序已经完成. (四)进位制是人们为了计数和运算方便而约定的记数系统,约定满 二进一,就是二进制;满十进一,就是十进制,等等.即“满几进一”就 是几进制,几进制的基数就是几. 常用的是十进制,用 0~9 这十个数字,计数时,几个数字排成一行, 从右起向左分别是个位、十位、百位、千位、万位??它可以用 10 的幂 的形式写成,如 67890 可以写成 6×104+7×103+8×102+9×101+0×100. 其他进位制也可以类似地用基数的幂的形式,如:111111(2)=1× 25+1×24+1×23+1×22+1×21+1×20, 654321 7) ( =6×75+5×74+4×73+3 ×72+2×71+1×70. 上述方法实质上是将不同进制的数转化成了十进制的数, 这类问题可 统一由程序来实现. 我们也能把十进制的数转化为其他进制的数, 用除 K 取余法.方法是: 用 K 连续去除这个数,或所得的商,一直到商为 0 止,然后取其余数, 把这些余数顺次排起来,就是 K 进制的数.如,将 1285 化为 16 进制的数:
1 18 余 6 25 数 1 8 6 0 5 1 5 6 0 0 5

END IF WEND “的最大公约数为:;a ”

个输出语句不换行.

直到今天,秦九韶算法仍是 世界上多项式求值的最先进的方 法.这钟一成就比西方同样的算 法早五、六百年.这种算法容易在 计算器或计算机上实现.

分步写成: V0=a5, V1=V0x+a4, V2=V1x+a3, V3=V2x+a2, V4=V3x+a1, V5=V4x+a0.

排序的方法与技巧多种多 样,在不同的时间,不同的场合 可以用不同的技巧. 每一趟都从头开始,且两个 两个地比较, 一直到最后一个数, 每一趟可有多个交换.

日常生活中和普遍数学中用 的都是十进制.日常生活中有七 进制(一周 7 天) 、十二进制(一 年 12 个月) 、六十进制(1 小时 60 分,1 分钟 60 秒) ,等,基数 一般标在右下角. 基数不同,选用的数字也不 同,如二进制用 0 和 1,六进制 用 0,1,2,3,4,5. 任何一种进位制的数都可以 写成不同位上的数字与基数的幂 的乘积之和的形式. 最后一个余数写在首位,其 次是倒数第二个余数,依次递推. 验证: 505(16)=5×162+0×161+ 5×160 =5×256+5=1285. 规律发现

故 1285=505(16) 在实际生活中的数学知识很多,只要我们留心,世界上到处充满着数 学的气息,我国古代劳动人民在这方面积累了大量的知识和经验,有兴趣 的同学不妨上网查阅一下有关资料. [典型例题探究]
第 2 页 共 10 页

为您服务教育网

http://www.wsbedu.com/

【例 1】 我国《算经十书》之一《孙子算经》中有这样一个问题: “今 有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二.问物几何? 答曰:二十三.”你能用程序解决这个问题吗? 分析:设物共 m 个,被 3,5,7 除所得的商分别为 x、y、z,则这个 问题相当于求不定方程 ?m ? 3x ? 2, ? 的正整数解. ?m ? 5 y ? 3, ?m ? 7 z ? 2 ? m 应同时满足下列三个条件: (1)m MOD 3=2; (2)m MOD 5=3; (3)m MOD 7=2.因此,可以让 m 从 2 开始检验,若 3 个条件中有任何一 个不成立,则 m 递增 1,一直到 m 同时满足三个条件为止. 解:m=2 f=0 WHILE f=0 IF m MOD 3=2 AND m MOD 5=3 AND m MOD 7=2 THEN PRINT “物体的个数为:;m ” f=1 ELSE m=m+1 END IF WEND END 【例 2】我国古代数学家张邱建编《张邱建算经》中记有有趣的数学 问题: “今有鸡翁一,值钱五;鸡母一,值钱三;鸡雏三,值钱一凡百钱, 买鸡百只,问鸡翁、母、雏各几何?”你能用程序解决这个问题吗? 分析:设鸡翁、母、雏各 x、y、z 只,则 z ? ① ?5 x ? 3 y ? ? 100, 3 ? ? x ? y ? z ? 100, ② ? 由②,得 z=100-x-y, ③代入①,得 5x+3y+ ③

这个问题的通用解法称为 “孙子剩余定理”或“中国剩余 定理”.著名的“韩信点兵问题” 即为此例的应用. 考虑到 m 被 7 除余数为 2, 故 m 至少是 9,也可以从 m=9 开 始验证.

设置 f=0,f=1 的目的是让循 环进行或结束,否则循环无法停 下来.此处让 f=0 时进行循环, f=1 时中止循环. 实际上按此法求出来的只是 符合条件的最小正整数. 这个问题在数学上称为“百 鸡问题”.

把三元一次方程组转化为二 元一次不定方程.

100 ? x ? y =100, 3

即 7x+4y=100. ④ 求方程④的解,可由程序解之. 解:x=1 y=1 WHILE x<=14 WHILE y<=25 IF 7*x+4*y=100 THEN z=100-x-y PRINT “鸡翁、母、雏的个数别为:;x,y,z ” END IF y=y+1 WEND x=x+1 y=1 WEND END 实际上,该题可以不对方程组进行化简,通过设置多重循环的方式得 以实现.由①、②可得 x 最大值为 20,y 最大值为 33,z 最大值为 100,且 z 为 3 的倍数.程序如下:
第 3 页 共 10 页

从 x 的最小值开始验证,循 环进行. 由于 7x+4y=100, x、 且 y∈Z, 故 x≤14,y≤25.

为您服务教育网

http://www.wsbedu.com/

x=1 y=1 z=3 WHILE x<=20 WHILE y<=33 WHILE z<=100 IF 5*x+3*y+z/3=100 AND x+y+z=100 THEN PRINT “鸡翁、母、雏的个数分别为:;x、y、z ” END IF z=z+3 WEND y=y+1 z=3 WEND x=x+1 y=1 WEND END 【例 3】写出用二分法求方程 x3-x-1=0 在区间[1,1.5]上的一个 解的算法(误差不超过 0.001). 分析:教材 P23 练习第 1 题已研究过求 x2-2=0 的近似根的方法.本例 与上述方法类似,只是方程稍微复杂了些.由于 f(1)=13-1-1=-1<0, f(1.5)=1.53-1.5-1=0.875>0,所以取[1,1.5]中点

对于多重循环或条件嵌套, 要注意每一重都有开头和结尾, 程序本身也有一个结尾,不能丢 掉任何一个.

用二分法求方程的近似值一 般取区间[a,b]具有以下特征: f(a)<0,f(b)>0. 相应的程序框图是:
开始 a=1 b=1.5 c=0.001 a+b 2

1 ? 1.5 =1.25 研 2

究,以下同求 x2-2=0 的根的方法. 解:a=1 b=1.5 c=0.001 DO x=(a+b)/2 ∧ f(a)=a 3-a-1 ∧ f(x)=x 3-x-1 IF f(x)=0 THEN PRINT “x=” ;x ELSE IF f(a)*f(x)<0 THEN b=x ELSE a=x END IF END IF LOOP UNTIL ABS(a-b)<=c PRINT “方程的一个近似解 x=” ;x END 【例 4】 (1)将 101111011(2)转化为十进制的数; (2)将 53(8)转化为二进制的数. 分析: (1)将各位上的数字与基数的幂的积求和. (2)先转化为十进制的数,再利用除 2 取余法. 解: (1)101111011(2)=1×28+0×27+1×26+1×25+1×24+1×23+0× 2 1 2 +1×2 +1=379. (2)53(8)=5×81+3=43.

x=

f a)=a 3 -a-1 ( f x)=x3 -x-1 (

f x)=0? (




f a)f x)<0 ( (
否 是

a=x

b=x



a-b <c?


输出x

第 4 页

共 10 页

为您服务教育网

http://www.wsbedu.com/

2 43 余 数 1 2 21 1 2 10 2 5 0 1 2 2 0 2 1 0 1

不同进位制之间的转化是一 种通法,必须熟练掌握.

∴53(8)=101011(2). 【例 5】用冒泡排序法将下列各数排成一列: 8,6,3,18,21,67,54. 并写出各趟的最后结果及各趟完成交换的次数. 分析:每一趟都从头开始,两个两个地比较,若前者小,则两数位置 不变;否则,调整这两个数的位置. 解:第一趟的结果是: 6 3 8 18 21 54 67 完成 3 次交换. 第二趟的结果是: 3 6 8 18 21 54 67 完成 1 次交换. 第三趟交换次数为 0,说明已排好次序, 即 3 6 8 18 21 54 67. 【例 6】 用秦九韶算法写出求 f(x)=1+x+0.5x2+0.16667x3+0.04167x4+ 0.00833x5 在 x=-0.2 时的值的过程.分析:先把函数整理成 f(x)=(( ((0.00833x+0.04167)x+0.16667)x+0.5)x+1)x+1,按照 从内向外的顺序依次进行. 解:x=-0.2 a5=0.00833 V0=a5=0.008333 a4=0.04167 V1=V0x+a4=0.04 a3=0.016667 V2=V1x+a3=0.15867 a2=0.5 V3=V2x+a2=0.46827 a1=1 V4=V3x+a1=0.90635 a0=1 V5=V4x+a0=0.81873 ∴f(-0.2)=0.81873.

注意取余数的顺序: 从下向上.

注意“一趟”的意义:每一 趟都从头开始,每两个两个地比 较,一直到最后一个数.

相当于用提公因式法分解 因式.

通过分解步骤看出作乘法的 次数少,比直接代入求幂的运算 速度要快得多.

[教材习题研讨] P21 思考 答案:当计算机遇到 UNTIL 语句时,先执行一次循环体,再判断是 否满足条件,若不满足,再执行循环体,然后再检查是否满足条件,如此反 复.当满足条件时,将不执行循环体,转而执行 LOOP UNTIL 后的语句. P22 思考 答案:课本上的算法可以改进.将循环条件“WHILE d<=n-1 AND flag=1”改为“WHILE d<=SQR(n) AND flag=1”即可. P23 练习 1.解:a=1 b=2 c=0.005 DO x=(a+b)/2 ∧ f(a)=a 2-2 ∧ f(x)=x 2-2 IF f(x)=0 THEN PRINT “方程根为:;x ” ELSE
第 5 页 共 10 页

方法点拨 WHILE 语句称为前测试型, UNTIL 语句称为后测试型. 改进后循环次数少了,提高 了解题速度. 若改为 INPUT “请输入 a、 的值:; b ” a、b INPUT “请输入误差范围 c:;c ” 则该题的区间范围、误差范 围还可以改变、限制.

为您服务教育网

http://www.wsbedu.com/

IF f(a)*f(x)<0 THEN b=x ELSE a=x END IF END IF LOOP UNTIL ABS(a-b)<=c PRINT “方程的近似根为:;x ” END 2.解:x=1 WHILE x<=20 ∧ y=x 2-3*x+5 PRINT “x=” ;x PRINT “y=” ;y x=x+1 WEND END 3.解:t=1 i=1 INPUT “请输入 n 的值:;n ” DO t=t*i i=i+1 LOOP UNTIL i>n PRINT “这个数的阶乘为:;t ” END P23 习题 1.2 A组 1.解: (1)输入你的名字,输出你的名字. (2) A=1 A=1×2=2 A=2×3=6 A=6×4=24 A=24×5=120 输出 5! 是 120 2.解:INPUT “梯形的上底、下底、高分别为:;a,b,h ” c=(a+b)/2 S=c*h PRINT “梯形的面积 S=” ;S END 3.解:INPUT “请输入两个整数 a,b:;a,b ” IF a MOD b=0 THEN PRINT “a 能被 b 整除” ELSE PRINT “a 不能被 b 整除” END IF END 4.解:INPUT “请输入加数的个数 n:;n ” t=1 i=2 sum=0 DO sum=sum+i t=t+1 i=

|a-b|<=c 不成立时循环, 成立时则停止循环.

计算一个、输出一个,再计 算、输出下一个,如此反复.

也可以用 WHILE 语句 WHILE i<=n t=t*i i=i+1 WEND 输出语句可写成 PRINTn; “!=” ;t

正确理解输入语句、输出语 句和赋值语句.

a,b,h 可分别输入,写成 三个 INPUT 语句.

MOD 表示取余数,整除即 余数为 0. 输出语句可以写成 PRINTa; “能被” b; ; “整除”

sum=sum+i 是 累 加 求 和 , t=t+1 表示计数器.

t ?1 t
可以用 WHILE 语句,条件
第 6 页 共 10 页

LOOP UNTIL t>n

为您服务教育网

http://www.wsbedu.com/

PRINT “和 s=” ;sum END 5.解:s=1 t=1 p=1 i=1 j=1 k=1 INPUT “请输入 n,m 的值:;n,m ” DO s=s*i i=i+1 LOOP UNTIL i>n DO t=t*j j=j+1 LOOP UNTIL j>m DO p=p*k k=k+1 LOOP UNTIL k>n-m a=t*p b=s/a PRINT “组合数的值为:;b ” END B组 1.解:R=0.5 a=1000 i=1 DO a=a*(1+R) i=i+1 LOOP UNTIL i>6 PRINT “2008 年底的资金总额为:;a ” END 2.解:INPUT “请输入 x 的值:;x ” IF x<1 THEN y=x PRINT “y=” ;y ELSE IF x<10 THEN y=2*x-1 PRINT “y=” ;y ELSE y=3*x-11 PRINT “y=” ;y END IF END IF END 3.解:INPUT “请输入数字 a 和加数的个数 n:;a,n ” s=0 b=a i=1 DO
第 7 页 共 10 页

是 t<=n.

设置三个计数器,三个独立 的循环结构.

可以写成 WHILE 语句,同 学们自己写出.

2008 年 底 资 金 总 额 为 1000(1+0.5)6 万元,设计成累 乘的形式,用循环结构.如用 INPUT 语句输入 a、R 的值,则 具有一般意义.

分段函数对应于条件结构, 用 条件语句的形式,可以形成嵌套.

实数 aaaa=a×103+a×102+a ×10+a, aaaa=aaa×10+a,类推.

为您服务教育网

http://www.wsbedu.com/

s=s+b b=b*10+a i=i+1 LOOP UNTIL i>n PRINT “s=” ;s END

[知识应用自测] 1.写出下列程序运行的结果. (1)a=2 (2)x=100 i=1 i=1 WHILE i<=6 DO a=a+1 x=x+10 PRINT i,a PRINT i,x i=i+1 i=i+1 WEND LOOP UNTIL x=200 END END 答案: (1)1,3;2,4;3,5;4,6;5,7;6,8. (2)1,110;2,120;3,130;4,140;5,150;6,160;7,170; 8,180;9,190;10,200. 2.求小于 100 的所有正偶数的和,设计一个算法的程序. 解:s=2 i=4 DO s=s+i i=i+2 LOOP UNTIL i>=100 PRINT “2+4+6+?+98=” ;s END 3.计算 100×(1+0.02)8,用循环语句写出算法. 解:a=100 R=0.002 i=1 WHILE i<=8 a=a*(1+R) i=i+1 WEND ∧ PRINT “100*(1+0.002) 8=” ;a END 4.求平方值小于 1000 的最大正整数,写出一个算法的程序. 解:i=1 DO ∧ s=i 2 i=i+1 LOOP UNTIL s>=1000 i=i-2 PRINT “平方值小于 1000 的最大正整数为:;i ” END 5.计算 1+2+22+23+24+?+263,写出算法的程序. 解:s=1 n=2 i=1
第 8 页 共 10 页

思路导引 ←理解当型语句和直到型语句的 不同,理解循环体的执行步骤.

←用 UNTIL 语句.

←用 WHILE 语句.

←用 UNTIL 语句.

←用 WHILE 语句.

为您服务教育网

http://www.wsbedu.com/

i<=63 ∧ s=s+n i i=i+1 WEND ∧ ∧ ∧ PRINT “1+2+2 2+2 3+?+2 63=” ;s END 6.1,1,2,3,5,8,13,21,?这一列数的规律是:从第三个数开 始,每个数为其前面两个数的和,写出计算这列数前 20 个数的和的算法 程序. 解:A=1 B=1 s=A+B i=1 WHILE i<=18 C=A+B s=s+C A=B B=C i=i+1 WEND PRINT “前 20 个数的和为:;s ” END 7.设计 0°~180°间隔为 10°的角的正弦值的求法程序. 解:A=0 DO C=3.14159265*A/180 B=sin(C) PRINT “角和它的正弦值分别为:;A,B ” A=A+10 LOOP UNTIL A>180 END 8.2000 年我国人口为 13 亿,如果人口每年的自然增长率为 7?,那 么多少年后我国人口将达到 15 亿?设计一个算法的程序. 解:A=13 R=0.007 i=1 DO A=A*(1+R) i=i+1 LOOP UNTIL A>=15 i=i-1 PRINT “达到或超过 15 亿人口需要的年数为:;i ” END 9.编写求乘积为 399 的两个相邻奇数的程序. 解:i=1 DO t=i+2 s=i*t i=i+2 LOOP UNTIL s=399 PRINT t-2,t END

WHILE

←用 WHILE 语句,设置累加项.

←用 t=t+10 的形式.

←用 UNTIL 语句.

←用 UNTIL 语句.

第 9 页

共 10 页

为您服务教育网

http://www.wsbedu.com/

第 10 页

共 10 页


相关文章:
高中数学必修三1.3算法案例练习
高中数学必修三1.3算法案例练习_数学_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 高中数学必修三1.3算法案例练习_数学_高中教育_教育专区。一、选择...
高中数学必修3《1.3算法案例)》教案设计
高中数学必修3《1.3算法案例)》教案设计_数学_高中教育_教育专区。www.xkb1.com 新课标第一网系列资料 www.xkb1.com 新课标第一网不用注册,免费下载! 1.3...
高中数学必修三1.3算法案例
高中数学必修三1.3算法案例_高一数学_数学_高中教育_教育专区。1.3《算法案例 1——辗转相除法与更相减损术》导学案【学习目标】 1、 会用辗转相除法和更相减...
人教版高中数学必修三《1.3算法案例(教、学案)
临清三中数学组 编写人:赵万龙 审稿人: 郭振宇 李怀奎 1.3 算法案例 【教学目标】 : 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算...
1.3_算法案例
1.3_算法案例_高一数学_数学_高中教育_教育专区。1.3 算法案例 教学分析 在学生学习了算法的初步知识, 理解了表示算法的算法步骤、 程序框图和程序三种不同 ...
1.3算法案例
1.3算法案例_数学_高中教育_教育专区。1.3 算法案例 [自我认知]: 1.用辗转相除法求 840 与 1785 的最大公约数: 班次 姓名 2.用更相减损术求 612 与 ...
1.3算法案例
1.3算法案例_数学_高中教育_教育专区。高二数学必修 3 编号:SX--02--06 1.3.1《算法案例》导学案撰稿:付阿丽 审核:付阿丽 时间:2011.08.16 姓名: 班级:...
1.3算法案例
1.3算法案例_数学_高中教育_教育专区。高一数学必修 3 第一章算法初步导学案 编制人: 审核人: 班级: 小组: 姓名: 等级: §1.3 《算法案例》练习案 1、用...
1.3算法案例
1.3算法案例_数学_高中教育_教育专区。高二数学必修三1. 3 算法案例 (讲) 在初中,我们已经学过求最大公约数的知识,你能求出 18 与 30 的公约数吗? 我们...
1.3 算法案例
1.3 算法案例_数学_高中教育_教育专区。1.3 算法案例 . 课时安排 3 课时 提出问题 (1)怎样用短除法求最大公约数? (2)怎样用穷举法(也叫枚举法)求最大...
更多相关标签: