アルゴリズム・データ構造
ゆーくりっどのごじょほう
2 つの自然数の最大公約数を求める古典的アルゴリズム。大きい数 a を小さい数 b で割った余り r を取り、(b, r) のペアで再帰的に処理することを r が 0 になるまで続け、その時点の b が最大公約数となる。引き算で代用する減算版もあるが、剰余版のほうがはるかに高速で、現在も標準的に使われる。
基本情報では、処理手順、計算量、データの保持方法を読み取る問題で出ます。ITパスポートでも、探索やソート、ビット演算の基本的な意味を問われることがあります。手順を図や小さな例で追えるようにすると安定します。
ユークリッドの互除法と同じ「アルゴリズム・データ構造」の用語では、オートマトン、基数変換、逆ポーランド記法などが近い文脈で問われます。扱うデータの並び、更新のしやすさ、探索の速さ、手順の停止条件を分けて比較してください。