基本情報技術者講座
★ 猫本 4-01 アルゴリズム(その1) ★
基本情報技術者 平成31年春期 問7
次の流れ図は，2数 A，B の最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。Aが876，Bが204のとき，何回の比較で処理は終了するか。
| ア | 4 |
| イ | 9 |
| ウ | 10 |
| エ | 11 |
解説
地道にトレースをする。
| 初期値 | L←876，S←204 | |
| 1回目 | 876＞204 | L←876－204＝672 |
| 2回目 | 672＞204 | L←672－204＝468 |
| 3回目 | 468＞204 | L←468－204＝264 |
| 4回目 | 264＞204 | L←264－204＝60 |
| 5回目 | 60＜204 | S←204－60＝144 |
| 6回目 | 60＜144 | S←144－60＝84 |
| 7回目 | 60＜84 | S←84－60＝24 |
| 8回目 | 60＞24 | L←60－24＝36 |
| 9回目 | 36＞24 | L←36－24＝12 |
| 10回目 | 12＜24 | S←24－12＝12 |
| 11回目 | 12＝12 | A，B，Lの出力 |
よって，エである。
解答
エ
基本情報技術者 令和元年度秋期 問9
配列Aが図2の状態のとき，図1の流れ図を実行すると，配列Bが図3の状態になった。図1のaに入れるべき操作はどれか。ここで，配列A，Bの要素をそれぞれ A(i，j)，B(i，j) とする。
| ア | B(7－i，7－j) ← A(i，j) |
| イ | B(7－j，i) ← A(i，j) |
| ウ | B(i，7－j) ← A(i，j) |
| エ | B(j，7－i) ← A(i，j) |
解説
(頭の準備体操)
具体例を想定して考えれば，問題がやさしくなる。
A(0,1)がB(1,7)へ移動する場合を想定する。
A(0,1),つまりi＝0，j＝1のとき，
| ア | B(7－i，7－j)＝B(7－0，7－1)＝B(7，6) |
| イ | B(7－j，i)＝B(7－1，0)＝B(6，0) |
| ウ | B(i，7－j)＝B(0，7－1)＝B(0，6) |
| エ | B(j，7－i)＝B(1，7－0)＝B(1，7) |
よって，エである。
解答
エ
基本情報技術者 令和元年度秋期 問1
次の流れ図は，10進整数j(0＜j＜100)を8桁の2進数に変換する処理を表している。2進数は下位桁から順に，配列の要素NISHIN(1)からNISHIN(8)に格納される。流れ図のa及びbに入る処理はどれか。ここで，j div 2はjを2で割った商の整数部分を，j mod 2はjを2で割った余りを表す。
解説
(頭の準備体操)
具体例を想定して考えれば，問題がやさしくなる。
10進数jを10とし，2進数に基数変換する。
| j | 商：j div 2(整数部分) | 余り：j mod 2 | |
| 10 | ÷2 | 5 | 0 |
| 5 | ÷2 | 2 | 1 |
| 2 | ÷2 | 1 | 0 |
| 1 | ÷2 | 0 | 1 |
| 0 | ÷2 | 0 | 0 |
| 0 | ÷2 | 0 | 0 |
| 0 | ÷2 | 0 | 0 |
| 0 | ÷2 | 0 | 0 |
2進数に変換すると00001010となるが，2進数下位桁から順に，配列の要素NISHIN(1)からNISHIN(8)に配列に格納される。
配列 NISHIN
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
以上から，アかエである。トレースをして確かめる。
ア
【 a 】 j ← 10 div 2， jには5が格納される。
【 b 】 NISHIN(1) ← 5 mod 2， NISHIN(1)には1が格納される。
誤り
エ
【 a 】 NISHIN(1) ← 10 mod 2， NISHIN(1)には0が格納される。
【 b 】 j ← 10 div 2， jには5が格納される。
正しい
よって，エである。
解答
エ