基本情報技術者令和4年免除 問7
問7
与えられた正の整数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)に戻る。
- 3
- 4
- 6
- 7
- [出典]
- 午前免除試験 R4-6月 問5
- 基本情報技術者 H24 問2と同題
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
イ
解説
問題文の手順に従って処理をトレースしていきます。
- 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