アルゴリズム(全80問中2問目)
No.2解説へ
与えられた正の整数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)に戻る。
出典：令和4年免除 問 7
- 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
広告