アルゴリズム (全80問中34問目)
No.34
与えられた正の整数x0，x1(x0＞x1)の最大公約数を，次の手順で求める。x0＝175，x1＝77の場合，手順(2)は何回実行するか。ここで，"A→B"は，AをBに代入することを表す。
〔手順〕
〔手順〕
- 2→i
- xi－2をxi－1で，割った剰余→xi
- xi＝0ならばxi－1を最大公約数として終了する。
- i＋1→i として(2)に戻る。
出典：平成24年秋期 問2
- 3
- 4
- 6
- 7
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
イ
解説
問題文の手順に従って処理をトレースしていきます。
- x0＝175、x1＝77
- (1)2→i //i＝2
- (2)…1回目
x0÷x1＝175÷77＝2 余り21
21→x2 //x2＝21 - (3)x2は0ではないので処理続行
- (4)i＋1＝2＋1→i //i＝3
- (2)…2回目
x1÷x2＝77÷21＝3 余り14
14→x3 //x3＝14 - (3)x3は0ではないので処理続行
- (4)i＋1＝3＋1→i //i＝4
- (2)…3回目
x2÷x3＝21÷14＝1 余り7
7→x4 //x4＝7 - (3)x4は0ではないので処理続行
- (4)i＋1＝4＋1→i //i＝5
- (2)…4回目
x3÷x4＝14÷7＝2
0→x5 //x5＝0 - (3)x5は0なので処理終了
最大公約数＝x4＝7