No.51 与えられた正の整数x0，x1(x0＞x1)の最大公約数を，次の手順で求める。
x0＝175，x1＝77の場合，手順(2)は何回実行するか。
ここで，"A→B"は，AをBに代入することを表す。
〔手順〕2→ixi－2をxi－1で，割った剰余→xixi＝Oならばxi－1を最大公約数として終了する。
i＋1→i として(2)に戻る。
x0＝175，x1＝77の場合，手順(2)は何回実行するか。
ここで，"A→B"は，AをBに代入することを表す。
〔手順〕2→ixi－2をxi－1で，割った剰余→xixi＝Oならばxi－1を最大公約数として終了する。
i＋1→i として(2)に戻る。
⭕️
❌
💾
| 🖊 | ☑️ |
| ⭕️ | [[ AnswerCalc[0] ]] % | A | [[ AnswerCalc[1] ]] |
|
|
|
|
|
|
|
|
問題文の手順に従って処理をトレースしていきます。
- 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
💾
✔️
| [[ d.CommentTxt ]] |
| < | > |
| 🥇 |