必修31.3 中国古代数学中的算法案例教案

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、算法

Ｓ１　　输入，ｘ，ｙ

Ｓ２　　ｍ＝ｍａｘ{ｘ，ｙ}

Ｓ３　　ｎ＝ｍｉｎ{ｘ，ｙ}

Ｓ４　　若ｍ／ｎ＝[ｍ／ｎ]（[ｘ]表示ｘ的整数部分）

则输出ｎ，否则执行Ｓ５

Ｓ５　　ｒ＝ｍ－[ｍ／ｎ]＊ｎ

Ｓ６　　ｍ＝ｎ

Ｓ７　　ｎ＝ｒ

Ｓ８　　执行Ｓ４

Ｓ９　　输出ｎ

上述算法的含义是　　　　　　　　　。

6、试写出一个算法，并画出流程图，使得能够输入n个正整数值，即可求出它们的最大公约数。

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

8、求两个整数ｘ（ｘ≥０）和ｙ（ｙ＞０）的整数商和余数（规定只能用加法和减法运算）。

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

参考答案

1.A 

2.C

3、更相减损之术       等值算法

4、运算次数

5、求ｘ，ｙ的最大公约数

6、略解：

Read n ,a

For i=2 to n

Read b

If a<b then m=a:a=b:b=m

Do

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　　　ｍ，ｎ

（当型）　　ｒ＝ｍ／ｎ的余数

ＷＨＩＬＥ　ｒ≠０

ｍ＝ｎ

ｎ＝ｒ

ｒ＝ｍ／ｎ的余数

ＷＥＮＤ

ＰＲＩＮＴ　　　ｎ

ＥＮＤ

（直到型）

INPUT　　　ｍ，ｎ

ＤＯ　　　ｒ＝ｍ／ｎ的余数

ｍ＝ｎ

ｎ＝ｒ

ＬＯＯＰ　　ＵＮＴＩＬ　　　ｒ＝０

ＰＲＩＮＴ　　　　　ｍ

ＥＮＤ

8、

解：算法：

Ｓ１　　使ｑ＝０，ｒ＝２

Ｓ２　　当ｒ≥ｙ时，重复下面操作

Ｓ３　　ｒ＝ｒ－ｙ

Ｓ４　　ｑ＝ｑ＋１

Ｓ５　　输出ｘ

程序框图

INPUT　　　ｑ＝０

ｒ＝ｘ

ｙ＝ｙ

ＤＯ　　　　ｒ＝ｒ－ｙ

ｑ＝ｑ＋１

ＬＯＯＰ　　　ＵＮＴＩＬ　　　　ｒ≥ｙ

ＲＩＩＮＴ　ｒ

ＥＮＤ

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。