＝＝＝ 平成24年秋 問2 ＝＝＝

---

平成24年秋目次　 前の問題　 次の問題

---

問２

与えられた正の整数Ｘ₀,Ｘ₁(Ｘ₀＞Ｘ₁)の最大公約数を、次の手順で求める。Ｘ₀＝175、Ｘ₁＝77の場合、手順(2)は何回実行するか。ここで、"A→B"は、AをBに代入することを表す。

[手順]
(1)2→i
(2)Ｘ_i-2をＸ_i-1で割った剰余→Ｘ_i
(3)Ｘ_i＝０ならばＸ_i-1を最大公約数として終了する
(4)i+1→iとして(2)に戻る

ア　３　　　　イ　４　　　　ウ　６　　　　エ　７

解説

1回目
　 i=2、Ｘ₀＝175、Ｘ₁＝77
175を77で割った余り21をＸ₂とする
i=3とする

2回目
　 i=3、Ｘ₁＝77、Ｘ₂＝21
77を21で割った余り14をＸ₃とする
i=4とする

3回目　
i=4、Ｘ₂＝21、Ｘ₃＝14
21を14で割った余り7をＸ₄とする
i=5とする

4回目
　 i=5、Ｘ₃＝14、Ｘ₄＝7
14を7で割った余り0をＸ₄とする
Ｘ₄=0なので終了

結局(2)を4回通った

答

イ


にほんブログ村