ソフトウェア開発技術者平成20年秋期 午前問14

問14

次に示すユークリッド互除法(方法1,方法2)で,正の整数a,b の最大公約数は,それぞれmとnのどちらの変数に求まるか。ここで,m mod n はmをnで割った余りを表す。
14.gif/image-size:233×387
  • 14a.gif/image-size:187×134

            
  • [出題歴]
  • 応用情報技術者 H27秋期 問6
  • ソフトウェア開発技術者 H18秋期 問13

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

2つの方法で、a=256、b=160、最大公約数32 を設定した場合の流れをトレースしてみます。
[方法1]
m=256; n=160
256 mod 160=96 //r=96
[--ループ1回目--]
160→m; 96→n
160 mod 96=64 //r=64
[--ループ2回目--]
96→m; 64→n
96 mod 64=32 //r=32
[--ループ3回目--]
64→m; 32→n
64 mod 32=0 //r=0
[--ループ終了--]
終了時点でm=64、n=32なので最大公約数は変数nに格納されます。

[方法2]
m=256; n=160
[--ループ1回目--]
256 mod 160=96 //r=96
160→m; 96→n
[--ループ2回目--]
160 mod 96=64 //r=64
96→m; 64→n
[--ループ3回目--]
96 mod 64=32 //r=32
64→m; 32→n
[--ループ4回目--]
64 mod 32=0 //r=0
32→m; 0→n
[--r=0でループ終了--]
終了時点でm=32、n=0なので最大公約数は変数mに格納されます。

したがって方法1では変数n、方法2では変数mに求まることになります。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop