LET'S TRY
問題文
与えられた正の整数x₀，x₁（x₀＞x₁）の最大公約数を求める手順において，x₀＝175，x₁＝77の場合，剰余を求める演算は何回行われるか。
fe-siken.com
IPAの公開問題について ↗
2012年秋 科目A
アルゴリズムとプログラミングの過去問
まずは自分で考えて、理由を確かめよう。
キホン猫と、理由を確かめよう。
自分で考えてから、解説を開いてみてね。
正解と解説を見る
正解は イ です。
ユークリッドの互除法のトレース：①175÷77＝2余り21、②77÷21＝3余り14、③21÷14＝1余り7、④14÷7＝2余り0。剰余が0になった時点で処理終了。最大公約数は7となり、剰余を求める演算の実行回数は4回です。
この問題を、学びのノートに。
学習ノートを読み込んでいます…