目次

基本テクニック

平成30年春期 午後問8 解説
設問1
設問2

平成29年秋期 午後問8 解説
平成29年春期 午後問8 解説

平成28年秋期 午後問8 解説
平成28年春期 午後問8 解説
設問1
設問2

平成27年秋期 午後問8 解説
平成27年春期 午後問8 解説
設問1
設問2
設問3

平成26年秋期 午後問8 解説
平成26年春期 午後問8 解説

平成25年秋期 午後問8 解説
設問1
設問2
平成25年春期 午後問8 解説
設問1
設問2

平成24年秋期 午後問8 解説
平成24年春期 午後問8 解説

平成23年秋期 午後問8 解説
平成23年特別 午後問8 解説

平成22年秋期 午後問8 解説
平成22年春期 午後問8 解説

※表計算対策
関数の暗記
※データベース問題対策
命令文の暗記
※計算問題の単位
まとめ中
ホームに戻るボタン↓

基本情報技術者過去問題 平成30年春期 午後問8 設問2　解説

「heapSort」をトレース

このプログラムは「本プログラム heapSort」から、副プログラム「makeHeap」と「downHeap」を順に呼び出して、数列を昇順（小さい順）に整列させます。
３行目の「makeHeap」が終わった時点で、各関数の数値は以下のようになっています。

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 30 45 15 5 10 20

hnum = 7

4行目からトレースします。

・last:hnum-1, last ＞ 0, -1
last の初期値を hnum-1 として、繰り返すごとに -1　しながら、 0 より大きい間ループします。

last
6

・swap(heap, 0, last)
最大の数値であることが確定しているheap[0]を数列のお尻に移動します。

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 30 45 15 5 10 20 60

空欄cはエです。

downHeapをトレースする

「makeHeap」の６行目を見ると「downHeap」に「heap」と「last-1」を入れています。
「downHeap」の１行目で「heap[]」と「hlast」として受けていますので、hlast の初期値は 5 になります。
n tmp hlast
　 　 5

・n ← 0
n tmp hlast
0 　 5

・lchild(n) ＜＝ hlast
左の子が整列対象領域内のあいだ、５行目から１５行目の処理をループします。

・tmp ← lchild(n)
n tmp hlast
0 1 5

・rchild(n) ＜＝ hlast
右側の子が整列対象領域内で、

・heap[tmp] ＜＝ heap[rchild(n)]
右側の子が左側の子以上だった場合、

・tmp ← rchild(n)
を実行します。

n tmp hlast
0 1 2 5

空欄dはイです。

・heap[tmp] ＞ heap[n]
最大の子と親を比べ、子のほうが大きいときは上の処理をします。

・swap(heap, n, tmp)
親と子を交換します。
heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 30 45 20 15 5 10 20 60

・n ← tmp
n tmp hlast
0 2 1 2 5

空欄eはイです。

「downHeap」のループ２回目

設問は以上で終わりですが、以下にその後の処理を記します。

・lchild(n) ＜＝ hlast
左の子が整列対象領域内なので５行目以降の処理をします。

・tmp ← lchild(n)
n tmp hlast
0 2 1 2 5 5

・rchild(n) ＜＝ hlast
右側の子が整列対象領域内ではないので内側の処理はしません。

・heap[tmp] ＜＝ heap[rchild(n)]
左側の子が親以上ではないので、下の処理をします。
「downHeap」を抜けます。

「heapSort」のループ２回目

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 45 20 15 5 10 45 20 60

last
6 5

２回目の「downHeap」

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 30 10 45 20 15 5 10 45 20 60

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 30 10 15 45 20 15 10 5 10 45 20 60

「heapSort」のループ３回目

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 30 10 15 45 20 15 10 5 30 10 45 20 60

last
6 5 4

３回目の「downHeap」

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 30 10 15 45 20 5 15 10 5 30 10 45 20 60

「heapSort」のループ４回目

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 10 30 10 15 45 20 5 15 10 20 5 30 10 45 20 60

last
6 5 4 3

４回目の「downHeap」

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 10 15 30 10 15 10 45 20 5 15 10 20 5 30 10 45 20 60

「heapSort」のループ５回目

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 10 15 5 30 10 15 10 45 20 5 15 15 10 20 5 30 10 45 20 60

last
6 5 4 3 2

５回目の「downHeap」

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 10 15 5 10 30 10 15 10 5 45 20 5 15 15 10 20 5 30 10 45 20 60

「heapSort」のループ６回目

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 10 15 5 10 5 30 10 15 10 5 10 45 20 5 15 15 10 20 5 30 10 45 20 60

last
6 5 4 3 2 1

６回目の「downHeap」

変化なし

以上です。
heap[0]から[6]まで、小さい順に並べなおすことができました。

ホームに戻るボタン↓

基本情報技術者過去問題 平成30年春期 午後問8 設問1　解説

本問を最初に解いたとき、筆者はある重大なミスをしてしまうのですが、そこからどうリカバリーすればよいかも含めて、参考にしていただければと思います。

引数を設定する

図１を見ると、親と子の関係は正しいのですが、根の子は左側が小さく、左側の子の子は右側が小さいので、きちんと整列されていない状態なのがわかると思います。
そしてプログラム１の関数名が「makeHeap（ヒープを作る）」であることから、図１で引数を作り、プログラム１を走らせて整列させると判断し、引数を用意しました。

data[]
[0] [1] [2] [3] [4] [5] [6]
60 30 45 15 5 10 20

hnum = 7

makeHeapをトレースする

このような箱を作ります。

heap[]
[0] [1] [2] [3] [4] [5] [6]
　 　 　 　 　 　 　

i k
　 　

１回目のループ

・i: 0, i ＜ hnum, 1
ループはデータ数回繰り返します。
i の初期値は 0 です。

heap[]
[0] [1] [2] [3] [4] [5] [6]
　 　 　 　 　 　 　

i k
0 　

・heap[ i ] ← data[ i ]

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 　 　 　 　 　 　

i k
0 　

・k ← i

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 　 　 　 　 　 　

i k
0 0

k が 0 なので内側のループには入らず、１回目のループは終了です。

２回目のループ

・i: 0, i ＜ hnum, 1
・heap[ i ] ← data[ i ]
・k ← i

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 30 　 　 　 　 　

i k
0 1 0 1

k が 0 より大きいので内側のループに入ります。
空欄ａですが、そもそもいまだ入力されていない子の値を参照することはできないので、 アウエカは消えます。
そして、子が親より大きければ上の処理（親と子を交換する処理）を、子が親以下の値なら下の処理をしたいので、空欄ａはイです。

子より親のほうが大きいので下の処理をします。
break とあるので、何もせず内側のループを抜け、外側のループの２回目は終了です。

３回目のループ

・i: 0, i ＜ hnum, 1
・heap[ i ] ← data[ i ]
・k ← i

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 30 45 　 　 　 　

i k
0 1 2 0 1 2

と、ここまで来てようやく私は自分の勘違いに気づきます。
このままでは最後まで内側のループの上の処理に入れません。

問題を読み進めてみると、私は本プログラムを、
data[]を、副プログラム「makeHeap」を使って完璧に整列させるものと勘違いしたのですが、
実際は、
data[]を、副プログラム「makeHeap」で、まずは親子の関係を整列させ、
副プログラム「downHeap」でヒープの特性を利用して、数列を昇順に整列させるものだと判明するのです。

兄弟関係は並べ直ししません。

引数を自分で作る

なぜこのようなミスを犯したかと言うと、 実は本問には makeHeap を検査する引数は用意されていないのです。
すでに整列し終わった状態の数値しかありません。
結構いじわるですよね。
ではどうすればよいでしょうか？
引数が問題文にないときは自分で作ります。
このテクニックを覚えてください。
過去にも数問ですが、架空の引数を自分で作らなければならない問題があります。

ここでリカバリーのテクニックなのですが、馬鹿正直に独創的な引数を考える必要はありません。
ようは内側のループの上の処理を通ればいいだけなのですから、いままで使ってきた引数をほんのちょこっと加工してしまえばいいのです。

data[3] の値を 5 から 70 に変更します。

４回目のループ

・i: 0, i ＜ hnum, 1
・heap[ i ] ← data[ i ]
・k ← i

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 30 45 70 　 　 　

i k
0 1 2 3 0 1 2 3

k が 0 より大きいので内側のループに入ります。
heap[3] が heap[parent(3)] より大きいので上の処理をします。

副プログラム「swap」は、現在の状態の数列 heap[] と、２つの添え字を引数として与えれば、それを交換してくれます。

空欄ｂは k の親を意味するエです。

・swap[heap, k, parent(k)]
heap[]
[0] [1] [2] [3] [4] [5] [6]
60 30 70 45 70 30 　 　 　

・k ← parent(k)
一番大きい子が親に移動したので、 k も親の要素番号に書き換えます。

i k
0 1 2 3 0 1 2 3 1

k が 0 より大きいのでループします。

heap[1] が heap[parent(1)] より大きいので上の処理をします。

・swap[heap, k, parent(k)]
heap[]
[0] [1] [2] [3] [4] [5] [6]
60 70 30 70 60 45 70 30 　 　 　

・k ← parent(k)
i k
0 1 2 3 0 1 2 3 1 0

ｋ が 0 なのでループを抜けます。

これ以上続けても無意味なので、以降の処理は割愛します。

いちおうの最終結果はこうなります。
heap[]
[0] [1] [2] [3] [4] [5] [6]
60 70 30 70 60 45 70 30 5 10 20

ホームに戻るボタン↓

基本情報技術者過去問題 平成29年秋期 午後問8 解説

引数を設定する

文字列「ipa␣␣」でトレースします。
表2の仕様に基づいて引数を作ります。

input
[1]		 input
[2]		 input
[3]		 input
[4]		 input
[5]
i p a ␣ ␣

len = 5

calcCheckCharacter

・N ← 30
N に 30 をいれます。
これは表1の文字種が30種だからです。

・sum ← 0
sum に 0 をいれます。
これは初期化のためです。

・is_even ← false
is_even は現在検査している文字が、文字列の偶数番目かどうかを判定するための変数です。
1文字目は奇数番目の文字なのですから false で初期化します。

ループ

・i: len, i ＞ 0, -1
ループは、文字列のお尻から順に、文字数回繰り返します。

・value ← getValue(input[i])
これは input[i] を引数として副プログラム「getValue」を走らせて、戻ってきた値を value に代入する、という意味です。
input[5] は文字「␣」なので表1から value には「0」が代入されます。

・is_even = 空欄a1
偶数ならそのまま足し合わせ、奇数なら２倍してうんぬんということなのですから、空欄a1 は true です。

is_even は false なので下の処理をします。

0を2倍してNで割ると
(0 × 2 ) ÷ 30 = 0 余り 0

sum は　sum + 0 + 0 で 0 になりました。

・is_even ← not is_even
not is_even は is_even を逆にして上書きしろ、という意味です。
is_even が false だったら true に、true だったら false に書き換えます。

ループの２回目から５回目

ループして２回目、今度もvalue には「0」が代入されます

is_even は true なので上の処理をします。

sum は　sum + 0 で 0 になりました。

is_even をfalseにします。

このようにして最後までループを繰り返すと以下のような結果になります。

␣　：　(0 × 2 ) ÷ 30 = 0 余り 0
␣　：　0
a　：　(4 × 2 ) ÷ 30 = 0 余り 8
p　：　19
i 　：　(12 × 2 ) ÷ 30 = 0 余り 24

sum は 51 になりました。

後処理

・check_value ← 空欄ｂ
Nから、sum を N で割った余りを引き、さらにその結果を N で割り余りを求めたいのですから、空欄ｂはウです。

sum を N で割る。
51 ÷ 30 = 1 余り 21

N から余りを引く
30 - 21 = 9

さらに N で割り余りを求める。
9 ÷ 30 = 0 余り 9

よって check_value は 9 になります。

・return getChar(check_value)
これは check_value を引数として副プログラム「getChar」を走らせて、戻ってきた値を「返す」という意味です。
getChar に　9　をいれると「f」が戻ってきますので、「f」を返してプログラムは終了です。

validateCheckCharacter

文字列「ipa␣␣f」でトレースします。

N と sum は先ほどと同じです。

・is_odd ← true
is_oddは現在検査している文字が、文字列の奇数番目かどうかを判定するための変数です。
1文字目は奇数番目の文字なのですから true で初期化します。

・ret_value ← true
ret_value はリターンバリューの略で、このプログラムを実行したときの最終的な検査結果のことです。
初期値を true としています。

ループのアルゴリズムは先ほどとほとんど同じです。

・is_even = 空欄a2
奇数ならそのまま足し合わせ、偶数なら２倍してうんぬんということなのですから、空欄a2 は true です。

ループを繰り返すと以下のような結果になります。

f　：　9
␣　：　(0 × 2 ) ÷ 30 = 0 余り 0
␣　：　0
a　：　(4 × 2 ) ÷ 30 = 0 余り 8
p　：　19
i 　：　(12 × 2 ) ÷ 30 = 0 余り 24

sum は 60 になりました。

・空欄c
sum が N で割り切れないとき、検査文字付文字列に誤りがあると判定したいのですから、 空欄ｃはエです。

60　÷　30　=　2　余り　0

余りが 0 なので ret_value は true のままです。

・return ret_value
true を返してプログラムは終了です。

設問2

「ipa␣␣f」を奇数番目の文字と偶数番目の文字に分け、アルファベット順に並べて直してみます。
奇数：␣ai
偶数：␣fp

ケース１
奇数：␣bi
偶数：␣fp

ケース２
奇数：␣ai
偶数：␣fp

ケース３
奇数：␣ap
偶数：␣fi

ケース４
奇数：␣ai
偶数：␣fp

ケース２と４は「ipa␣␣f」と同じなので誤りがないと判定されてしまいます。

空欄ｄはオです。

設問3

␣　：　(0 × 2 ) ÷ 30 = 0 余り 0
␣　：　0
s　：　(22 × 2 ) ÷ 30 = 1 余り 14
␣　：　0

sum = 15

15 ÷ 30 = 0 余り 15
30 - 15 = 15
15 ÷ 30 = 0 余り 15

よって check_value は 15 になります。

getChar に　15　をいれると「l」が返ってきます。

空欄eはウです。

設問4

行（横軸）の検査文字は、設問２にあるように、ケース２と４で同一になってしまいますが、 列（縦軸）の検査文字は、すべての列で同一となるケースはありません。

空欄ｆはカです。

ホームに戻るボタン↓

基本情報技術者過去問題 平成23年秋期 午後問13 解説

問題文は他のサイトを別ウインドウで開いてご覧ください。

問題文の表にある数値を引数として、トレースします。

問題文の日本語が難しい

問題文には、

「本部に属する社員の賞与の合計(以下，本部賞与合計という)が，本部利益の15%の金額(以下，本部賞与合計上限という)以下となる条件を満足する1～20の整数があるときは，その最大値を本部加点とする。無いときは，本部加点を0とする。」

とありますが、意味わかるでしょうか？

あなただけでなく多くの人がわかりません。もちろん私も。
マクロをトレースすることでようやく「ああそういうことか」と気づくことができるので、とにかく読み進めるしかありません。

空欄ｆ

空欄ｆにはループ条件がはいります。
第一本部、第二本部、第三本部と３回繰り返したいので、ループ回数が３回の選択肢を選べばいいだけです。

空欄ｆはウです。

DeptPoint の初期値を 0 に設定します。
DeptPoint ← 0

メインループ

ループ条件が後にあるタイプのループです。

まず DeptPoint をプラス1します。

相対(L1, row, 0) に DeptPoint をいれます。
L
1 本部加点
2 1

こうなりますよね。
すると次にどうなるでしょう？
ここが想像できないから問題文を読んだだけではピンとこないのです。
トレースしてみてようやく気付きます。

L2が上書きされるとすぐさま自動更新されて、L6～L112までの社員ごとの本部加点が上書きされます。
続いて、M6～M112までの社員ごと給与額も更新されます。
そしてさらに、M2の合計額が更新されます。

こうして自動で更新された M2 を、空欄 g で K2 と比較します。

「前者が後者を上回る、又は、本部加点が20を超えたとき」にループを抜けるようにしたいのですから、空欄 g はエとなります。

こうして、
L2 を 2 にして自動更新、比較。
L2 を 3 にして自動更新、比較。
L2 を 4 にして自動更新、比較。
と繰り返していき、
L2 を 21 にして自動更新、比較したときに条件が合わずループを抜けます。

空欄h

手順５に「このときの本部加点から1を減じた値を第1本部の本部加点とし，対応するセルに代入する。」とあるとおり、アルゴリズムの整合性を取るために、最終的に DeptPoint から 1 引いた数値を L2 に入力します。

空欄 h はウです。

ホームに戻るボタン↓

基本情報技術者過去問題 平成28年秋期 午後問13 解説

問題文は他のサイトを別ウインドウで開いてご覧ください。

問題文の表にある数値を引数として、トレースします。

最初のループ

最初のループは20回繰り返します。
ループを開くと以下になります。

相対(A2, 1, 0)　←　null
相対(A2, 2, 0)　←　null
相対(A2, 3, 0)　←　null
相対(A2, 4, 0)　←　null
相対(A2, 5, 0)　←　null
相対(A2, 6, 0)　←　null
相対(A2, 7, 0)　←　null
相対(A2, 8, 0)　←　null
相対(A2, 9, 0)　←　null
相対(A2, 10, 0)　←　null
相対(A2, 11, 0)　←　null
相対(A2, 12, 0)　←　null
相対(A2, 13, 0)　←　null
相対(A2, 14, 0)　←　null
相対(A2, 15, 0)　←　null
相対(A2, 16, 0)　←　null
相対(A2, 17, 0)　←　null
相対(A2, 18, 0)　←　null
相対(A2, 19, 0)　←　null
相対(A2, 20, 0)　←　null

表の値を書き換えます。
A
3 null
4 null
5 null
6 null
7 null
8 null
9 null
10 null
11 null
12 null
13 null
14 null
15 null
16 null
17 null
18 null
19 null
20 null
21 null
22 null

これは繰り返し使ったときに前の値が残らないように、初期化しているだけです。

準備

相対(I2, F3, 0) ＜ 9999 なら状態遷移列が存在するので、以下の行を実行します。
相対(I2, F3, 0) は 相対(I2, 13, 0) すなわち セルI15（値は47）です。
なお列Iの値は、本問には記述されていない CalculateMinimum という、このマクロとは別のマクロにより自動入力されているので、気にする必要はありません。

初期値を設定します。
NumWork ← 0
Current ← 13

作業数 NumWork を算出する

ループするたびに NumWork をプラス1してループ回数を数えることにより、作業数 NumWork を算出します。

現状態ID から 前状態IDを順に辿っていくことによって数えますので、空欄eはアとなります。

Current が開始状態IDになった時点でループを抜けますので、ループ条件は「Currentが開始状態IDではない限りループし続ける」となりますので、空欄dはカです。

トレースさせてもらえない

具体的に追ってみます。
状態ID 13 の前状態IDは 11 です。
状態ID 11 の前状態IDは、、、

省略されて書いてないんです。
トレースさせてもらえません。
結構イジワルですよね。

しかし、列Aを見れば 自動入力する行数は 8 であることがわかります。
そして、IDの遷移は 13,11,10,9,8,6,4,3であることも推測できます。

以上から NumWork が 7 であることがわかります。

状態遷移列を格納する

初期値を設定します。
Current ← 13

空欄 f ですが、I の初期値は NumWork となります。
このために前の工程で算出したのですから。

相対(A3, 7, 0) ← 13 をいれます。
Current ← 11 をいれます。

表の値を書き換えます。
A
3 null
4 null
5 null
6 null
7 null
8 null
9 null
10 13

これを8回繰り返します。

相対(A3, 6, 0) ← 11 をいれます。
Current ← 10 をいれます。
相対(A3, 5, 0) ← 10 をいれます。
Current ← 9 をいれます。
相対(A3, 4, 0) ← 9 をいれます。
Current ← 8 をいれます。
相対(A3, 3, 0) ← 8 をいれます。
Current ← 6 をいれます。
相対(A3, 2, 0) ← 6 をいれます。
Current ← 4 をいれます。
相対(A3, 1, 0) ← 4 をいれます。
Current ← 3 をいれます。
相対(A3, 0, 0) ← 3 をいれます。
Current ← 0 をいれます。

表の値を書き換えます。
A
3 3
4 4
5 6
6 8
7 9
8 10
9 11
10 13

空欄 f の選択肢のうち、
エは7回、
オは7回、
カは8回繰り返します。

よって空欄 f はカです。

ホームに戻るボタン↓

基本情報技術者過去問題 平成29年春期 午後問13 解説

問題文は他のサイトを別ウインドウで開いてご覧ください。

問題文の表にある数値を引数として、トレースします。

最初のループ

最初のループは３回繰り返します。
ループを開くと以下になります。

相対(B9, 0, 0)　←　相対(B4, 0, 0)
相対(B9, 0, 1)　←　相対(B4, 0, 1)
相対(B9, 0, 2)　←　相対(B4, 0, 2)

これを、左側は該当セルに、右側は入力する数値に置き換えます。

B9　←　10
C9　←　36
D9　←　30

表の値を書き換えます。
A B C D
9 残数量 010 036 030

トレースによりここでは、入力されている発送数量を、梱包作業表（作業に使うために用意された領域）にコピーしていることがわかりました。

荷物番号の初期値を設定します。
packge_no　←　1

荷物を作る

1ループにより1つ荷物を作ります。
残重量(E9)が0になったら終了です。

まず、表示する行を表に作ります。

相対(A15, packge_no, 0)　←　packge_no
相対(F15, packge_no, 0)　←　F9
相対(G15, packge_no, 0)　←　G9

これを、左側は該当セルに、右側は入力する数値に置き換えます。

A16　←　1
F16　←　5
G16　←　1,944

表の値を書き換えます。
A B C D E F G
16 1 5 1,944

重量計算用の変数の初期値を設定します。
work_weight　←　0

内側のループ

商品Xの梱包数をカウントするのですが、まずは0個としてさらに内側のループへ。
B10　←　0

商品Yの梱包数をカウントするのですが、まずは0個としてさらに内側のループへ。
C10　←　0

商品Zの梱包数をカウントするのですが、まずは0個とします。
D10　←　0

E10は自動で計算され更新されます。

表の値を書き換えます。
A B C D E
10 作業数量 0 0 0 0

空欄e

一番大きい箱でも28,680gまでしかはいらないので、それを越えて商品を詰めることはできないのですから、 「E10≦重量区分!E8」とする必要があり、空欄eの選択肢のうち、アとウは消えます。

イとエの選択肢を見ると、いずれも work_weight と E10 を比較していますが、この時点では work_weight も E10 も 0 なので、どちらだったとしても条件に当てはまりません。

よって、１回目は false となり内側の処理を行いません。

ループして商品Zの数が1つ増え、同時にE10の値も更新されます。

D10　←　1
E10は自動で計算され更新されます。

A B C D E
10 作業数量 0 0 01 01,200

そして、また空欄eの判定を行いますが、今度はE10が更新されたので work_weight と E10 を比較する意味が出来ました。
ループすることによって、常にE10が先行して大きくなっていくのですから、もし選択肢がエだったら、永遠に一番内側のループには入れません。
よって空欄eはイとなります。

変数 k のループ

ループを開くと以下になります。

相対(B15, 1, 0) ← 相対(B10, 0, 0)
相対(B15, 1, 1) ← 相対(B10, 0, 1)
相対(B15, 1, 2) ← 相対(B10, 0, 2)
相対(B15, 1, 3) ← 相対(B10, 0, 3)

これを、左側は該当セルに、右側は入力する数値に置き換えます。
E10には説明文(5)から、B10～D10に格納された数量の合計が計算により入力されます。

B16　←　0
C16　←　0
D16　←　1
E16　←　1,200

work_weightの値を更新します。
work_weight　←　1,200

表の値を書き換えます。
A B C D E F G
16 1 0 0 1 1,200 5 1,944

以上の処理を30回繰り返して変数kのループを抜けます。

この箱には、28,680gまでしかはいらないので、結果はこうなります。
A B C D E F G
16 1 0 0 23 27,600 5 1,944
work_weight　←　27,600

後述しますが、実はここまでの処理は商品Xと商品Yが0個だったときの、商品Zの最大個数を求めているにすぎません。

変数 j のループ

変数jのループに戻って商品Yを1つ増やします。
変数kに入って30回繰り返し、また変数jに戻って商品Yを1つ増やし、といった具合に、36×30回ループを繰り返し、 商品総重量がより大きくなったときに表を更新します。

後述しますが、実はここまでの処理は商品Yと商品Zの、箱にできるだけ多く詰められる組み合わせを求めているにすぎません。

変数 i のループ

もうわかったと思いますが、今度は商品Xを1づつ増やして全通りの組み合わせを試し、最大となる値を探します。

つまり、このマクロでは10×36×30＝10800回ループして全通り試しているのです。
処理が重くてビックリしますが、どうやらそれ以外に方法がないです。

最後のループ

現在の値はこうなっています。
A B C D
9 残数量 10 36 30

3回ループして B C D を更新しますが、1回目だけ空欄 f の選択肢を比較してみます。

ア　相対(B9,0,0) ← 相対(B4,0,0)－相対(B10,0,0)
イ　相対(B9,0,0) ← 相対(B4,0,0)－相対(B15,package_no,0)
ウ　相対(B9,0,0) ← 相対(B9,0,0)－相対(B10,0,0)
エ　相対(B9,0,0) ← 相対(B9,0,0)－相対(B15,package_no,0)

左辺の 相対(B9,0,0) は残数量です。この処理では残数量を更新したいということがわかります。

右辺の (B4,0,0) と (B9,0,0) を比較します。
相対(B4,0,0) は、もともとの発送商品数量のことで変化しません。
2箱目、3箱目となったときに、前の箱で差し引いた値からひき続き減算しなければならないのですから、選択肢アとイは消えます。

相対(B10,0,0) と 相対(B15,package_no,0) を比較します。

相対(B10,0,0) は作業に利用する変数が保存されているセルで、最善個数が保存されているとは限りません。
決定した最善個数は相対(B15,package_no,0) に表示されています。

空欄 f はエです。

package_noを1増やして、ループします。
すべての商品の残数量が 0 になったらマクロを終了します。

ホームに戻るボタン↓

基本情報技術者過去問題 平成29年春期 午後問8 解説

問題文は他のサイトを別ウインドウで開いてご覧ください。

最初にやること

この問題、はじめてアルゴリズム問題にチャレンジする人は、おそらく解き方すらわからないと思います。
しかし、どんな問題であろうともやることは一緒で、まずは引数を用意します。

その引数ですが、どこにも書いてありませんよね。一部はありますが、すべては用意されていません。
実はこの問題では、図1を見ながら自分で作ることを暗に要求されているのです。

さらに本問では変数の種類がかなり多いので、記憶に頼るのではなく、各変数が何を意味しているかを押さえながら、表を作って行きたいと思います。

引数を用意する

引数を図1から作ります。

Distance[ ][ ]は表2に用意されています。これで大丈夫な人はこのままでいいですが、私の表の作り方とは感性がだいぶ違うので、すこし加工したいと思います。

Distance[ ][ ]　：地点間の距離
[0][0] [0][1] [0][2] [0][3] [0][4] [0][5] [0][6]
0 2 8 4 -1 -1 -1
[1][0] [1][1] [1][2] [1][3] [1][4] [1][5] [1][6]
2 0 -1 -1 3 -1 -1
[2][0] [2][1] [2][2] [2][3] [2][4] [2][5] [2][6]
8 -1 0 -1 2 3 -1
[3][0] [3][1] [3][2] [3][3] [3][4] [3][5] [3][6]
4 -1 -1 0 -1 8 -1
[4][0] [4][1] [4][2] [4][3] [4][4] [4][5] [4][6]
-1 3 2 -1 0 -1 9
[5][0] [5][1] [5][2] [5][3] [5][4] [5][5] [5][6]
-1 -1 3 8 -1 0 3
[6][0] [6][1] [6][2] [6][3] [6][4] [6][5] [6][6]
-1 -1 -1 -1 9 3 0

nPointは地点数ですので図1を見て数えます。

nPoint = 7　：地点数

同じく図1から地点番号を設定します。

sp = 0　：出発地点番号
dp = 6　：目的地点番号

初期値を設定する

行番号5～10で初期値を設定します。

sDist = ∞　：最短距離

sRoute[ ]　：最短経路
[0] [1] [2] [3] [4] [5] [6]
-1 -1 -1 -1 -1 -1 -1

pDist[ ]　：出発地からの最短距離
[0] [1] [2] [3] [4] [5] [6]
∞ ∞ ∞ ∞ ∞ ∞ ∞

pFixed[]　：確定状態（フラグ）
[0] [1] [2] [3] [4] [5] [6]
false false false false false false false

プログラム内で宣言している変数

その他にも行番号2～4で宣言している変数があります。

pRoute[ ]　：？？？
[0] [1] [2] [3] [4] [5] [6]
null null null null null null null

sPoint　：？？？
newDist　：？？？

トレース

行番号11から、
出発地から出発地（pDist[0]）までの距離を0に設定します。

pDist[ ]　：出発地からの仮の最短距離
[0] [1] [2] [3] [4] [5] [6]
0 ∞ ∞ ∞ ∞ ∞ ∞

ループ１回目

行番号14～19。
pFixed を検査して、いまだ数値が確定していない地点（値が false の地点）をひとつ選択します。
まだ最初なのですから i は 0 です。

行番号20～22。
すべての地点が確定していたらループを抜けます。
この判定にひっかかるのはループ８回目のときだけです。

行番号23～27。
説明文（5）の２に、「出発地からの最短距離が未確定の地点の中で、出発地からの距離が最も短い地点を探す」とあるので、空欄ａはイとなります。

pDist[ j ] が pDist[ i ] より小さければ i を j で上書きします。
j i pFixed[ j ] pDist[ j ] pDist[ i ]
1 0 false ∞ 0

この処理を j が nPoint より小さい間ループします。
j i pFixed[ j ] pDist[ j ] pDist[ i ]
1 0 false ∞ 0
2 0 false ∞ 0
3 0 false ∞ 0
4 0 false ∞ 0
5 0 false ∞ 0
6 0 false ∞ 0

結局 i は 一度も上書きされず 0 のままでした。

行番号28。
sPoint = 0　：このループ処理で判明した、出発点からいまだ数値が確定していない地点のうち距離が最短の地点

行番号29。
pFixed[0] を　true に書き換えます。
よって空欄ｂはオの sPoint です。

pFixed[ ]　：確定状態（フラグ）
[0] [1] [2] [3] [4] [5] [6]
true false false false false false false

行番号30～39。

31行目の >0 の意味ですが、
Distance[ ][ ] が -1 のときは　sPoint と隣接していない地点を表しています。
Distance[ ][ ] が 0 のときは　sPoint と同じ地点だということを表しています。
よって >0 のときは隣接地点である、となる訳です。

さらに and not(pFixed[j]) なのですから、pFixed[j] が false のとき（未確定のとき）に内側の処理をします。

j Distance
[ 0 ][ j ]		 pFixed
[ j ]		 newDist
0 0 true ×
1 2 false 0+2
2 8 false 0+8
3 4 false 0+4
4 -1 false ×
5 -1 false ×
6 -1 false ×

pDist[ ]　：出発地からの仮の最短距離
[0] [1] [2] [3] [4] [5] [6]
0 2 8 4 ∞ ∞ ∞

pRoute[ ]　：直前の経由地の地点番号
[0] [1] [2] [3] [4] [5] [6]
null 0 0 0 null null null

２回目

行番号14～22。
i は 1 になります。

行番号23～27。
j i pFixed[ j ] pDist[ j ] pDist[ i ]
2 1 false 8 2
3 1 false 4 2
4 1 false ∞ 2
5 1 false ∞ 2
6 1 false ∞ 2

やはり i は 一度も上書きされません。
これは、ようするに以下のことをやっているのです。
出発点から地点1までの距離は2。
（これを i として以下と比べます。）
出発点から地点2までの距離は8。
出発点から地点3までの距離は4。
地点4は隣接していない。
地点5は隣接していない。
地点6は隣接していない。
一番距離が短いのは地点1ですよね。
これをループ処理により導きだしているのです。

行番号28。
sPoint は 1 になります。

行番号29。
pFixed[ ]　：確定状態（フラグ）
[0] [1] [2] [3] [4] [5] [6]
true true false false false false false

行番号30～39。
j Distance
[ 1 ][ j ]		 pFixed
[ j ]		 newDist
0 2 true ×
1 0 true ×
2 -1 false ×
3 -1 false ×
4 3 false 2+3
5 -1 false ×
6 -1 false ×

pDist[ ]　：出発地からの仮の最短距離
[0] [1] [2] [3] [4] [5] [6]
0 2 8 4 5 ∞ ∞

pRoute[ ]　：直前の経由地の地点番号
[0] [1] [2] [3] [4] [5] [6]
null 0 0 0 1 null null

３回目

行番号14～22。
i は 2 になります。

行番号23～27。
j i pFixed[ j ] pDist[ j ] pDist[ i ]
3 2 false 4 8
4 3 false 5 4
5 3 false ∞ 4
6 3 false ∞ 4

出発点から地点2までの距離は8。
（これを i として以下と比べます。）
出発点から地点3までの距離は4。
地点4は隣接していない。
地点5は隣接していない。
地点6は隣接していない。
一番近い地点は3ですのでループの途中で i が 3 に変化しています。

行番号28。
sPoint は 3 になります。

行番号29。
pFixed[ ]　：確定状態（フラグ）
[0] [1] [2] [3] [4] [5] [6]
true true false true false false false

行番号30～39。
j Distance
[ 3 ][ j ]		 pFixed
[ j ]		 newDist
0 4 true ×
1 -1 true ×
2 -1 false ×
3 0 true ×
4 -1 false ×
5 8 false 4+8
6 -1 false ×

pDist[ ]　：出発地からの仮の最短距離
[0] [1] [2] [3] [4] [5] [6]
0 2 8 4 5 12 ∞

pRoute[ ]　：直前の経由地の地点番号
[0] [1] [2] [3] [4] [5] [6]
null 0 0 0 1 3 null

よって空欄ｆはカ、空欄ｇはアとなるのですが、、、

空欄ｇの選択肢には若干の戸惑いがあります。
pRoute[] の null値を 0 で初期化する命令文がどこかにあったでしょうか？
ちょっと私にはよくわかりません。

４回目以降

割愛させていただきます。本試でもトレースする時間はないはずです。
ただし、トレースしなくとも結果的に値がどうなるかがわからないと、残りの設問には感覚で回答することになります。
それが出題者の意図するところなので、仕方がないです。

後処理

行番号40。
判明した最短距離を sDist にいれます。
sDist = 13

行番号41。
j = 0

行番号42。
i = 6

行番号43。
i（目的地点） が sp（出発地点） になるまでループします。

なお、 pRoute は最終的に以下の値になっています。

pRoute[ ]
[0] [1] [2] [3] [4] [5] [6]
null 0 4 0 1 2 5

行番号44。
このループで sRoute[ ] を作成するのですが、 sRoute[ ] は「目的地点から出発地点の順に設定する」と引数の仕様に書いてありますので、まずは sRoute[0] に 目的地点を意味する i をいれます。

sRoute[ ]　：最短経路
[0] [1] [2] [3] [4] [5] [6]
6 -1 -1 -1 -1 -1 -1

よって空欄ｃはキになります。

行番号45。
次の地点に移動するため i を pRoute[ i ] に変更します。

j pRoute[ i ] i
0 5 6 5

よって空欄ｄはイになります。

行番号46。
j はループ処理するための軸に使っている意味のない変数です。
プラス1します。

j pRoute[ i ] i
0 5 6 5
1

以上の処理を出発地点まで繰り返すと以下のようになります。

sRoute[ ]　：最短経路
[0] [1] [2] [3] [4] [5] [6]
6 5 2 4 1 -1 -1

j pRoute[ i ] i
0 5 6 5
1 2 5 2
2 4 2 4
3 1 4 1
4 0 1 0
5

行番号48。
最後です。
sRoute[ j ] に sp をいれます。

sRoute[ ]　：最短経路
[0] [1] [2] [3] [4] [5] [6]
6 5 2 4 1 0 -1

感想

さてこの問題、３５分で解くことができるでしょうか？
私はこの原稿を作るのに１２時間以上かかりました。
問題に関係ないところまで完全トレースを試みましたが、申し訳ありませんが途中で断念いたしました。

断言できますが、この問題は絶対に時間内に解くことはできません。
完答できるのは、同種のアルゴリズムを以前に見聞きしたことがある人だけだと思います。

通常の問題でしたら、66％正解を目指したいところですが、この問題は半分答えられれば御の字といったところでしょう。
全部できなくても全く気にする必要はありません。
あなたができない問題は、周りの人たちもみんなできていないのです。

ホームに戻るボタン↓

登録: 投稿 (Atom)