欢迎您访问教学资源网(www.jxzy.wang)
首页 > 教案设计 > 数学教案设计 > 算法案例

算法案例

网友 分享 时间: 加入收藏 我要投稿 点赞
j.Co M
1.3 案例算法
案例1 辗转相除法与更相减损术
1、在对16和12求最大公约数时,整个操作如下:(16,12)→(4,12)→(4,8)→(4,4),由此可以看出12和16的最大公约数是( )
A、 4 B、 12 C、 16 D、 8
2、下列各组关于最大公约数的说法中不正确的是( )
A、16和12的最大公约数是4 B、78和36的最大公约数是6
C、85和357的最大公约数是34 D、105和315的最大公约数是105
3、我国古代数学家求两个正整数最大公约数的算法,被称为 ,又称为
4、运算速度快是计算机一个很重要的特点,而算法好坏的一个重要标志是
5、算法
S1  输入,x,y
S2  m=max{x,y}
S3  n=min{x,y}
S4  若m/n=[m/n]([x]表示x的整数部分)
则输出n,否则执行S5
S5  r=m-[m/n]*n
S6  m=n
S7  n=r
S8  执行S4
S9  输出n
上述算法的含义是         。
6、试写出一个算法,并画出流程图,使得能够输入n个正整数值,即可求出它们的最大公约数。


7、用当型和直到型语句,写出求两正整数的最大公约数的算法程序。



8、求两个整数x(x≥0)和y(y>0)的整数商和余数(规定只能用加法和减法运算)。

9、试用更相减损术求80和36的最大公约数。


参考答案

1.A
2.C
3、更相减损之术 等值算法
4、运算次数
5、求x,y的最大公约数
6、略解:
Read n ,a
For i=2 to n
Read b
If aDo
r=mod(a,b)
a=b:b=r
Loop Until r=0
If a=1 then prind a
Goto End
Next i
Print a
End
7、
INPUT   m,n
(当型)  r=m/n的余数
WHILE r≠0
m=n
n=r
r=m/n的余数
WEND
PRINT   n
END
(直到型)
INPUT   m,n
DO   r=m/n的余数
m=n
n=r
LOOP  UNTIL   r=0
PRINT     m
END
8、
解:算法:
S1  使q=0,r=2
S2  当r≥y时,重复下面操作
S3  r=r-y
S4  q=q+1
S5  输出x
程序框图
INPUT   q=0
r=x
y=y
DO    r=r-y
q=q+1
LOOP   UNTIL    r≥y
RIINT r
END
9、
解:80-36=44,
44-36=8,
36-8=28,
28-8=20,
20-8=12,
12-8=4,
8-4=4。
因此80和36的最大公约数是4。

221381