辗转相除法与更相减损术同步练习

辗转相除法与更相减损术练习题 1．下列有关辗转相除法的说法正确的是( ) A．它和更相减损术一样是求多项式值的一种方法

B．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r，直至r

D．以上说法均不正确

2．在m＝nq＋r(0≤r

D．不能确定

3．如图所示的程序表示的算法是( )

INPUT m，nDO

r＝m MOD n m＝n

n＝r

LOOP UNTIL r＝0PRINT mEND

A．交换m、n的值 B．辗转相除法 C．更相减损术

D．秦九韶算法 4．用辗转相除法求294和84的最大公约数时，需要做除法的次数是( )

A．1 B．2 C．3 D．4

5．运行下面的程序，当输入n＝840和m＝1764时，输出结果是( )

INPUT m，nDO

r＝m MOD n m＝n

n＝r

LOOP UNTIL r＝0PRINT mEND

A．84 B．12 C．168 D．252

6．用更相减损术，求105与30的最大公约数时，需要做减法的次数是( ) A．2 B．3 C．4 D．5

7．930与868的最大公约数是________． 8．阅读程序：

INPUT “m，n＝”；m，n

) 到

IF n>m THEN t＝m m＝n n＝t END IF DO

r＝m MOD n m＝n n＝r

LOOP UNTIL r＝0 PRINT m END

若INPUT语句中输入m，n的数据分别是72,168，则程序运行的结果为 9．(1)用辗转相除法求840与1764的最大公约数． (2)用更相减损术求459与357的最大公约数．

10．有甲、乙、丙三种溶液分别重147 g,343 g,133 g，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，则每瓶最多装多少溶液？

辗转相除法与更相减损术练习题答案

1．下列有关辗转相除法的说法正确的是( ) A．它和更相减损术一样是求多项式值的一种方法

B．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r，直至r

D．以上说法均不正确 [答案] C

2．在m＝nq＋r(0≤r

[解析] k是n，r的公约数，则n＝kk1，r＝kk2，m＝nq＋r＝kk1q＋kk2＝(k1q＋k2)k，所以k是(k1q＋k2)k与kk1的公约数，即k一定是m，n的公约数．

3．如图所示的程序表示的算法是( ) INPUT m，nDO

r＝m MOD n m＝n

n＝r

LOOP UNTIL r＝0PRINT mEND

A．交换m、n的值 C．更相减损术

B．辗转相除法 D．秦九韶算法 B．不一定是 D．不能确定

[答案] B

4．用辗转相除法求294和84的最大公约数时，需要做除法的次数是( ) A．1 B．2 C．3 D．4 [答案] B

[解析] ∵294＝84×3＋42,84＝42×2，∴选B.

5．运行下面的程序，当输入n＝840和m＝1764时，输出结果是( ) INPUT m，nDO

r＝m MOD n m＝n

n＝r

LOOP UNTIL r＝0PRINT mEND

A．84 B．12 C．168 D．252 [答案] A

[解析] ∵1764＝840×2＋84,840＝84×10， ∴1764与840的最大公约数为84.

6．用更相减损术，求105与30的最大公约数时，需要做减法的次数是( A．2 B．3 C．4 D．5 [答案] C

[解析] 105－30＝75,75－30＝45,45－30＝15,30－15＝15. 7．930与868的最大公约数是________． [答案] 62

[解析] ∵930＝868×1＋62 868＝62×14

∴930与868的最大公约数为62. 8．阅读程序：

INPUT “m，n＝”；m，n IF n>m THEN t＝m m＝n n＝t END IF DO

r＝m MOD n m＝n

)

n＝r

LOOP UNTIL r＝0 PRINT m END

若INPUT语句中输入m，n的数据分别是72,168，则程序运行的结果为________． [答案] 24

[解析] 该程序是用辗转相除法求两个数的最大公约数的算法程序，输入72,168，即求它们的最大公约数，可求出它们的最大公约数为24.

9．(1)用辗转相除法求840与1764的最大公约数． (2)用更相减损术求459与357的最大公约数． [解析] (1)1746＝840×2＋84 840＝84×10＋0

所以840与1764的最大公约数为84. (2)459－357＝102 357－102＝255 255－102＝153 153－102＝51 102－51＝51

所以459与357的最大公约数为51.

10．有甲、乙、丙三种溶液分别重147 g,343 g,133 g，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，则每瓶最多装多少溶液？

[解析] 每个小瓶的溶液的质量应是三种溶液质量147,343,133的公约数，最大质量即是其最大公约数．

先求147与343的最大公约数： 343－147＝196， 196－147＝49， 147－49＝98. 98－49＝49.

所以147与343的最大公约数是49. 再求49与133的最大公约数： 133－49＝84， 84－39＝35， 49－35＝14， 35－14＝21，

21－14＝7，

14－7＝7，所以49与133的最大公约数为7， 所以147,343,133的最大公约数为7. 即每瓶最多装7 g溶液．