ITパスポート 令和4年度 問79：アルゴリズム・流れ図に関する問題

答えは b（14） です。

この計算は「大きい方から小さい方を引く」をくり返し、2つの数が同じになったら止める、というルール。実際に追ってみましょう。

x=98, y=42 →（98−42）x=56, y=42 →（56−42）x=14, y=42 → 今度はyの方が大きいので（42−14）y=28, x=14 →（28−14）y=14, x=14 → x と y が同じ14になって終了！

だから答えのxは 14 です。

👉 コツ：あせらず1ステップずつ紙に書く。引き算の引かれる側がそのつど入れ替わるのに注意。

なぜこれが正解か

正解は b（14）。この流れ図は「大きい方から小さい方を引く」を x=y になるまで繰り返す処理。トレースすると以下の通り。

| 手順 | x | y |

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

| 初期 | 98 | 42 |

| x>y: x←x−y | 56 | 42 |

| x>y: x←x−y | 14 | 42 |

| x≤y: y←y−x | 14 | 28 |

| x≤y: y←y−x | 14 | 14 |

x=y=14で終了条件成立。よってxは14。

ポイント

これは2数の最大公約数(GCD)を引き算で求めるユークリッドの互除法（減算版）。GCD(98,42)=14と一致する。

覚え方・ひっかけ注意

「x=yで終了」「大きい方を更新」を取り違えると値がずれる。表を書いて1行ずつ確実に。終了時はx=yなので、aの0やcの28などの中間値を選ばないこと。

理論的背景

本問の流れ図は「x＝98、y＝42からスタートし、x≠yの間ループして、x>yならx←x-y、x≤yならy←y-xを繰り返し、x＝yで終了したときのxの値を求める」問題であり、正解bは14である。このアルゴリズムはユークリッドの互除法（Euclidean Algorithm）の差分版（減算版）として知られる最大公約数（GCD：Greatest Common Divisor）計算アルゴリズムである。

計算過程をトレースすると：x=98, y=42→x>yなのでx=98-42=56→x=56, y=42→x>yなのでx=56-42=14→x=14, y=42→x<yなのでy=42-14=28→x=14, y=28→x<yなのでy=28-14=14→x=14, y=14→x=yで終了。答えは14。

数学的な証明として、x>yの場合はx←x-yに変更してもgcd(x,y)＝gcd(x-y,y)が成立することからこのアルゴリズムの正当性が保証される。98と42の最大公約数を素因数分解で確認すると、98＝2×7²、42＝2×3×7なので、gcd(98,42)＝2×7＝14で一致する。

ユークリッドの互除法の剰余版（高速版）は「gcd(a,b)＝gcd(b, a mod b)」で実装され、差分版より収束が速いが、基本的な考え方は同じである。Euclidがこのアルゴリズムを「Elements（原論）」（紀元前300年頃）に記述したことから、人類最古のアルゴリズムの一つとして数学史・計算機科学史における重要な位置を占める。

実務での使われ方

最大公約数計算の実際の応用として以下がある。①暗号技術：RSA暗号の鍵生成ではgcd(e, φ(n))＝1（eとφ(n)が互いに素）の検証にユークリッドの互除法の拡張版（拡張ユークリッドアルゴリズム）が使われる。②分数の約分：分子・分母のGCDを求めて割り算する（プログラムの有理数ライブラリ等）。③テクスチャ・解像度計算：画像処理でGCDを使ってアスペクト比（16:9等）の最簡分数を求める。④ユーザーインターフェイス：PythonやJavaのFraction（分数クラス）の内部実装、Rustのnum-traits等がgcdアルゴリズムを実装している。

アルゴリズムの計算量の観点では、差分版ユークリッドはO(max(a,b)/gcd(a,b))の時間計算量がかかり、a＝1000000・b＝1の場合に極めて多くのステップが必要となる。一方剰余版ユークリッドはO(log(min(a,b)))という対数時間計算量で収束するため、実用実装では必ず剰余版が採用される。本問の減算版は教育的なトレース練習として出題されており、剰余版より直感的に理解しやすい特徴がある。

試験での位置づけ

ITパスポートのアルゴリズム・流れ図分野でフローチャートのトレース問題は頻出かつ高難度の問題類型である。本問のポイントは「x=98・y=42の初期値で繰り返しを手計算で確実にトレースし、途中計算を書き記しながら正確に収束値を求める」能力にある。試験本番では計算用紙に「x→、y→」の列を順番に書いて系統的にトレースすることが最もミスが少なく確実な解法となる。選択肢に0（a）・14（b）・28（c）・56（d）が並んでいることから、x=56, y=42, x=14, y=28という計算の途中値が誤答として配置されている点も確認できる。

基本情報技術者（FE）ではより複雑な流れ図（二重ループ・再帰的定義・配列操作を含む）のトレース問題が出題され、加えて「時間計算量・空間計算量のオーダー評価」「複数アルゴリズムの比較（バブルソートO(n²)vs クイックソート平均O(n log n)等）」「再帰アルゴリズム（フィボナッチ・階乗・二分木探索）の実装・評価」が求められる。アルゴリズム設計パターン（分割統治法・動的計画法・貪欲法）の理解は応用情報（AP）以上で本格的に問われる。

選択肢の発展補足

選択肢aの「0」はx＝yで終了という終了条件を「x-y=0」と誤解して「最終的なx-yの値」と誤算した場合の誤答である。終了時はx＝y＝14であり、x自体の値は14であってx-yの値（0）ではない。

選択肢cの「28」はトレースの途中値（y=28となる直前のステップ）であり、「y←y-x=42-14=28」のステップをトレースして途中で停止してしまった場合の誤答である。選択肢dの「56」は「x←x-y=98-42=56」という最初の更新後の値であり、1ステップ目で計算を停止した場合の誤答である。このように誘導値が計算過程の途中値として配置されているため、完全にトレースを完了することが正答の唯一の方法となる。

ユークリッドアルゴリズムと関連してフィボナッチ数列との深い関係が知られている。F(n)とF(n+1)（連続するフィボナッチ数）のユークリッドアルゴリズムは最も多くのステップを要する「最悪ケース」の入力値であり、これがフィボナッチ数列の数学的性質（黄金比φ≒1.618への収束）と結びついている。Knuth「The Art of Computer Programming」ではこの分析が詳細に論じられており、アルゴリズム解析の古典的な題材として数学・CS両分野で引用される。