ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

問11 流れ図のトレースと初期値の関係

基本情報​技術者試験 令和5年度 公開問題 科目A、全20問のうちの問11。

出典：令和5年度 基本情報技術者試験 公開問題 科目A 問11（流れ図は、記号ごとに番号と記号の種類、中身、次へ進む先を並べた表に書き起こした。判断の分岐の向き (＝ ≠ ＜ ＞) は次へ進む先の欄に書いた）

次の流れ図において，

① → ② → ③ → ⑤ → ② → ③ → ④ → ② → ⑥

の順に実行させるために，①において m と n に与えるべき初期値 a と b の関係はどれか。ここで，a，b はともに正の整数とする。

流れ図 (開始と終了は番号のない端子)
記号中身次へ
端子開始①
① 処理m ← a，n ← b②
② 判断m：n＝ なら ⑥，≠ なら ③
③ 判断m：n＞ なら ④，＜ なら ⑤
④ 処理m ← (m − n)②
⑤ 処理n ← (n − m)②
⑥ 入出力m の値を印字終了
端子終了なし
  1. アa ＝ 2b
  2. イ2a ＝ b
  3. ウ2a ＝ 3b
  4. エ3a ＝ 2b
答えと解説を開く

正解はエです。

指定の順に沿って、m と n の値を追います。①で m＝a、n＝b です。②で ≠ に進むので a≠b です。③のあと⑤に進むので、m＜n、つまり a＜b です。⑤で n←(n−m) を行い、n＝b−a になります。m は a のままです。次の②でも ≠ に進み、③のあと④に進むので、m＞n、つまり a＞b−a です。④で m←(m−n) を行い、m＝a−(b−a)＝2a−b になります。n は b−a のままです。最後の②で ＝ に進み⑥で印字するので、m＝n、つまり 2a−b＝b−a です。これを整理すると 3a＝2b になります。たとえば a＝2、b＝3 で確かめます。①で m＝2、n＝3、②で 2≠3、③で 2＜3 なので⑤で n＝3−2＝1、②で 2≠1、③で 2＞1 なので④で m＝2−1＝1、②で 1＝1 なので⑥で 1 を印字します。指定の順と一致します。正解はエです。

ほかの選択肢が違う理由

  • アa＝2b なら、たとえば a＝2、b＝1 です。最初の③で m＞n になり④へ進み、m＝1 で m＝n となって、①→②→③→④→②→⑥ の順になります。⑤を通りません。
  • イ2a＝b なら、たとえば a＝1、b＝2 です。最初の③で m＜n になり⑤へ進み、n＝1 で m＝n となって、①→②→③→⑤→②→⑥ の順になります。④を通りません。
  • ウ2a＝3b なら、たとえば a＝3、b＝2 です。最初の③で m＞n になり④で m＝1、次の③で m＜n になり⑤で n＝1 となります。④と⑤を通る順が逆です。

仕組み

この流れ図は、大きい方から小さい方を引くことを繰り返して、2 つの数の最大公約数を求める手順 (ユークリッドの互除法の引き算の形) です。m と n が等しくなったときの値が最大公約数です。

流れ図の問は、具体的な数を 1 組入れてトレースすると確かめやすくなります。式を立てたあと、条件に合う小さな数 (この問なら a＝2、b＝3) で順番どおりに進むかを見ます。

この問に出る言葉