問題プレビューID: 92a6b3fe基本情報技術者試験 午前免除試験 2019年7月28日

問 7
基本情報技術者試験 午前免除試験 2019年7月28日

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

方法 1

  1. 開始
  2. m←am \leftarrow a,n←bn \leftarrow b
  3. r←m mod nr \leftarrow m \bmod n
  4. ループ 1:r=0r = 0 ならば終了へ,そうでなければ次へ
  5. m←nm \leftarrow n
  6. n←rn \leftarrow r
  7. r←m mod nr \leftarrow m \bmod n
  8. ループ 1 へ戻る
  9. 終了

方法 2

  1. 開始
  2. m←am \leftarrow a,n←bn \leftarrow b
  3. ループ 2
  4. r←m mod nr \leftarrow m \bmod n
  5. m←nm \leftarrow n
  6. n←rn \leftarrow r
  7. r=0r = 0 ならば終了へ,そうでなければループ 2 へ戻る
  8. 終了
解説

正解は「ウ」です。

a=175a = 175,b=77b = 77 を例に,各方法でループ終了時にどちらの変数に最大公約数が残るかを確認します。

方法 1:r=0r = 0 になったときループを抜けます。

  • m=175m = 175,n=77n = 77,r=175 mod 77=21r = 175 \bmod 77 = 21
  • m=77m = 77,n=21n = 21,r=77 mod 21=14r = 77 \bmod 21 = 14
  • m=21m = 21,n=14n = 14,r=21 mod 14=7r = 21 \bmod 14 = 7
  • m=14m = 14,n=7n = 7,r=14 mod 7=0r = 14 \bmod 7 = 0 → ループ終了

終了時は m=14m = 14,n=7n = 7 であり,最大公約数 7 は nn に求まります。

方法 2:先に m←nm \leftarrow n,n←rn \leftarrow r を行ってから r=0r = 0 を判定します。

  • r=175 mod 77=21r = 175 \bmod 77 = 21,m=77m = 77,n=21n = 21
  • r=77 mod 21=14r = 77 \bmod 21 = 14,m=21m = 21,n=14n = 14
  • r=21 mod 14=7r = 21 \bmod 14 = 7,m=14m = 14,n=7n = 7
  • r=14 mod 7=0r = 14 \bmod 7 = 0,m=7m = 7,n=0n = 0 → ループ終了

終了時は m=7m = 7 であり,最大公約数 7 は mm に求まります。

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

関連問題

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