最大公約数を求める手順の実行回数を理解しよう

与えられた正の整数

の最大公約数を，次の手順で求める。

の場合，手順(2)は何回実行するか。

ここで，"A→B"は，AをBに代入することを表す。

〔手順〕

• ① 2 → i
• ② x_i - 2をx_i - 1で割った剰余 → x_i
• ③ x_i = 0ならばx_i - 1を最大公約数として終了する
• ④ i + 1 → i として②に戻る

Xiが非常にややこしいですが、気長に白紙に書いていけば簡単に解けます。

ここで最大公約数が7であることが分かりましたが、問題は何回②を実行したかということです。本番環境では時間がないので、答えが7と分かった瞬間、選択肢の7を選んでしまいがちです。落ち着いていきましょう。