基本情報 令和5年度 科目A 問11：テクノロジ系に関する問題

答えは d「3a＝2b」 です。

この問題は「mとnを引き算しながら同じ値になるまで繰り返す」アルゴリズム。最終的にm=nになったら印字して終了。

指定された順番で実行されるためには：

1. 最初 m=a, n=b で a＜b（だから n←n-m を実行）

2. 次に m=a, n=b-a で a＞b-a（だから m←m-n を実行）→ つまり 2a＞b

3. 最後に m=a-(b-a)=2a-b, n=b-a で m＝n（だから 2a-b＝b-a）

3つ目から 3a＝2b が出ます。例：a=2, b=3で実際に動かすと、(2,3)→(2,1)→(1,1)→印字。確かにdが成立。

👉 覚え方：“流れ図問題は具体的な数字で1ステップずつ追う”。

なぜこれが正解か

正解は d。この流れ図はm,nの比較結果で分岐するユークリッド互除法類似のアルゴリズム。指定の経路から各ステップでの大小関係を逆算する。

| ステップ | m | n | 比較結果 |

|--------|---|---|--------|

| 初期 | a | b | m＜n（a＜b） |

| n←n-m後 | a | b-a | m＞n（a＞b-a） |

| m←m-n後 | 2a-b | b-a | m＝n（2a-b＝b-a） |

3番目の式 2a-b＝b-a を解くと 3a＝2b。

各選択肢の検証

• a a=2b：a=4,b=2で試すと m＞nから始まりルートが違う。
• b 2a=b：a=1,b=2で(1,2)→(1,1)→印字。経路が①→②→③→⑤→②→⑥となり指定経路と異なる。
• c 2a=3b：a=3,b=2で m＞nから開始、不一致。
• d 3a=2b：a=2,b=3で指定経路通り動作 ✓

覚え方・ひっかけ注意

流れ図トレース問題は最小の整数（a=2,b=3など）を選択肢の式に代入して実際に動かすのが最速。式から逆算するよりミスが少ない。本問は「比較→引き算→ループ」の典型構造で、ユークリッド互除法（GCD計算）の基礎を理解しておくと類題に強い。

理論的背景：ユークリッド互除法

本問のアルゴリズムは引き算版のユークリッド互除法（Euclidean algorithm）。m,nの最大公約数（GCD）を求める古代ギリシャ以来の手法で、剰余版（m mod n）の方が計算量効率が良い（O(log min(m,n))）。引き算版はO(max(m,n)/gcd(m,n))で、片方が極端に大きいと低速。

本問は最終的にm=n=gcd(a,b)を出力する。a=2,b=3ならgcd=1で出力1、a=4,b=6ならgcd=2で出力2となる。

アルゴリズム解析の体系

流れ図トレース問題は応用情報・基本情報技術者でループ不変条件（loop invariant）・停止性証明として登場する分野の基礎。本問のループ不変条件は「gcd(m,n)＝gcd(a,b)が保たれる」こと。減算操作 n←n-m を行ってもGCDは変わらないという性質（gcd(m,n)=gcd(m,n-m)）が、互除法の正当性を保証する。

試験での位置づけ

午前科目Aではアルゴリズム分野の頻出形式。手で実行（dry run）してトレース表を作る訓練が必要。基本情報技術者試験では擬似言語で同種アルゴリズムが午後・応用情報・基本情報技術者まで継続的に問われる。

発展トピック：拡張ユークリッド互除法

gcd(a,b)に加えて a·x + b·y = gcd(a,b) を満たす整数x,yを同時に求めるアルゴリズムで、RSA暗号の秘密鍵生成（modnの乗法逆元計算）に必須。情報セキュリティ分野と数論を橋渡しする重要トピック。

選択肢の発展補足

• 本問のような流れ図問題は、各分岐の論理条件をリストアップして連立不等式・等式として解く方法でも解ける。代入と逆算を併用するのが最速。
• 引き算版互除法は古代の「相互減算法」、剰余版は「除算法」と呼ばれる。Pythonの`math.gcd`は内部で剰余版を採用。
• 競技プログラミングではGCD/LCMは前処理ライブラリの基本部品で、Stern-Brocot tree・Bezout恒等式と組み合わせて整数問題を解く道具となる。