問題プレビューID: 8ac136e5応用情報技術者試験 2015年(平成27年度)秋期 午前

問 6
応用情報技術者試験 2015年(平成27年度)秋期 午前

次に示すユークリッドの互除法(方法 1,方法 2)で,正の整数 aa,bb の最大公約数は,それぞれ mm と nn のどちらの変数に求まるか。ここで,m mod nm \bmod n は,mm を nn で割った余りを表す。

方法 1

方法 2

解説

正解は「ウ」です。

ユークリッドの互除法は,「mm を nn で割った余り rr を求め,nn を新しい mm,rr を新しい nn として,余りが 00 になるまで繰り返す」アルゴリズムです。余りが 00 になったとき,そのときの除数が最大公約数になります。

具体的に a=12a = 12,b=8b = 8 で追跡します。

  • 方法 1:m=12m = 12,n=8n = 8 のとき r=12 mod 8=4r = 12 \bmod 8 = 4。ループ 1 で r≠0r \neq 0 なので n→mn \to m(m=8m = 8),r→nr \to n(n=4n = 4),r=8 mod 4=0r = 8 \bmod 4 = 0。ループ 1 で r=0r = 0 となり終了します。このとき最大公約数 44 は nn に入っています。
  • 方法 2:m=12m = 12,n=8n = 8 のとき r=12 mod 8=4r = 12 \bmod 8 = 4,n→mn \to m(m=8m = 8),r→nr \to n(n=4n = 4)で r≠0r \neq 0。再びループ 2 で r=8 mod 4=0r = 8 \bmod 4 = 0,n→mn \to m(m=4m = 4),r→nr \to n(n=0n = 0)となり終了します。このとき最大公約数 44 は mm に入っています。

このように,方法 1 では割り算の結果をループの前後で nn に残すため最大公約数は nn に,方法 2 では除数 nn を先に mm へ移すため最大公約数は mm に求まります。

よって,方法 1 は nn,方法 2 は mm となり,「ウ」が正解です。

関連問題

本文が同じ・似ている問題を表示しています