基本情報技術者試験 科目B サンプル問題 問4の解説｜引き算をくり返して最大公約数を求める gcd

科目B サンプル問題 問4難易度 ★擬似言語・while と if・最大公約数最終更新 2026-09-22

どの行が何をしているかをつかめば、空欄は3つとも決まります。

出題

○整数型: gcd(整数型: num1, 整数型: num2)
  整数型: x ← num1
  整数型: y ← num2
  　a　
    if (　b　)
      x ← x － y
    else
      y ← y － x
    endif
  　c　
  return x

この問題に出てくる記号

読めない記号があったときだけ開いてください。

コードは何をしているか ── 3つの性質が、コードのどこにあるか

見えている行が、問題文の性質(1)〜(3)のどれにあたるかを結びつけます。

※ 右側の注釈は当サイトで書き加えたものです。プログラム自体は原文のまま引用しています。

関数 gcd が返すのは x です。だから、最後の x が最大公約数になっていなければなりません。そして性質(2)(3)のとおり、大きいほうから小さいほうを引いても、最大公約数は変わりません。つまりこのコードは、最大公約数を変えないまま引き算で2つの数を小さくしていき、x そのものが最大公約数になったところで返します。空欄で決めるのは、引き算の4行を何回実行するか（a・c）と、どちらが大きいときに x から引くか（b）です。

空欄 a と c を決める ── 1回引いたら終わりか

〔プログラム〕空欄 a〜c のまわり（上の〔プログラム〕から抜き出した。1字も変えていない）

  整数型: y ← num2
  　a　
    if (　b　)
      x ← x － y
    else
      y ← y － x
    endif
  　c　
  return x

※ 上の〔プログラム〕からの抜粋です（1字も変えていません）。

return x が最大公約数になるのは、性質(1)のx と y が等しいときだけです。15 と 6 なら、9 と 6 → 3 と 6 → 3 と 3 と、3回引いてやっと等しくなります。だから、等しくなるまで引き算をくり返します。

条件が真のあいだくり返すのが while です。a ＝ while (x ≠ y)、c ＝ endwhile。

空欄 b を決める ── どちらから引くか

〔プログラム〕空欄 b の if（上の〔プログラム〕から抜き出した。1字も変えていない）

    if (　b　)
      x ← x － y
    else
      y ← y － x
    endif

※ 上の〔プログラム〕からの抜粋です（1字も変えていません）。

b が真のときに実行するのは x ← x － y。性質(2)の引き算で、使えるのは「num1 がnum2 より大きいとき」です。だから b ＝ x ＞ y。

      y ← y － x

解答群を見る

a ＝ while (x ≠ y)、b ＝ x ＞ y、c ＝ endwhile。この組は エ です。

答え合わせ

正解は エ です。

ア・イは if なので1回で終わり、ウは向きが逆で終わりません。エを入れて gcd(15, 6) を最後まで動かすと、3 が返ります。

次に読む

この問題でどこに手間取ったかで、行き先が変わります。