トレースの最後の回です。今回は配列が出てくるプログラムを追います。前回までのやり方はそのまま使えます。新しく覚えるのは、配列を表のどこに書くかだけです。
第2部 定番処理の型 全27回
A1-1トレース表の書き方A1-2繰返しのトレースA1-3配列のトレースA2-1配列を全部見るA2-2最大・最小を見つけるA2-3探す(線形探索)A2-4入れる・消すA2-52つの配列を突き合わせるA3-12次元配列の走査A3-22次元配列の集計A4-1文字列を1文字ずつA4-2文字列照合A5-1交換して並べるA5-2挿入ソートA6分割して並べるA7-12分探索A7-2ハッシュ表探索A8-1再帰とはA8-2再帰のトレースA9スタックとキューA10-1リストを読むA10-2リストの挿入と削除A11木構造A12木の巡回A13グラフA14AI・データを題材にしたプログラムA15ファイル処理
まず、通しで見る
2分ほどの動画です(音声つき)。配列が出てきたときに新しく要るのは、たった1つ ── その周に、配列のどの値を読んだのかを表に残すことです。これが無いと、行を見ても何を足したのかが分かりません。そこを押さえたうえで、本番で書く量を減らすところまで進みます。
動画で追いかけるのは、このプログラムです。
整数型の配列: ten ← {80, 65, 90}
整数型: goukei ← 0
整数型: i
for (i を 1 から tenの要素数 まで 1 ずつ増やす)
goukei ← goukei + ten[i]
endfor
3人の点数を全部足して、goukei は最後に 235 になります。
配列のトレース(2分43秒・音声つき)
再生できないときは、この下の図と説明で同じ内容を追えます。
ここから、同じ内容を1つずつ確かめていきます。
追いかけるプログラム
今回追うのは、これです。
整数型の配列: ten ← {80, 65, 90}
整数型: goukei ← 0
整数型: i
for (i を 1 から tenの要素数 まで 1 ずつ増やす)
goukei ← goukei + ten[i]
endfor
やっていることは3つです。
このプログラムがすること
① ten に3人の点数 80・65・90 が入っている
② for が3周まわり、i が 1 → 2 → 3 と変わる
③ 毎周 ten[i] を1つ取り出して、goukei に足す
ten[i] は「ten の i 番目」です(G4-1)。1周目の i は 1 なので ten[1]、つまり 80 を読みます。
ですから goukei は 0 → 80 → 145 → 235 と増え、終わったときの値は 235 です。
この回の目的は、この 235 という答えではありません。いまの動きを紙の上でどう書きとめるかが主題です。まず動かして、動きのほうを先に確かめておきます。
配列のトレースを1行ずつ動かす
当サイトオリジナルの例題
ループ開始前
配列
いま計算していること
変数の状態
出力
トレース表(進めると1行ずつ積み上がります)
大事なのは「その周に、どの要素を読んだか」
ここからは、紙に書く表の話
プログラムが何をするかは、上で分かりました。ここから先は、それを書きとめる表をどう作るかの話です。
前回までと違うのは、たった1つです。ten[i] の i が、周ごとに変わります。
i が 1 → 2 → 3 と動くと、ten[i] が指す箱も1つずつ動きます。1周目は ten[1] の 80、2周目は ten[2] の 65、3周目は ten[3] の 90 です。
i が動くと、ten[i] が指す箱も動く
整数型の配列: ten ← {80, 65, 90}
1周目(i が 1) ten[1] は 80
180▲
265
390
2周目(i が 2) ten[2] は 65
180
265▲
390
3周目(i が 3) ten[3] は 90
180
265
390▲
変わるのは i だけ。だから表に書くのは「その周に読んだ値」
ですから、表に書くべきなのは その周に読んだ値です。列の名前は ten[i] にします。
その周に読んだ値の列をつくる
goukei ← goukei + ten[i]
列の名前は ten[i]
| 周 | i | ten[i] | goukei |
|---|---|---|---|
| はじめ | ー | ー | 0 |
| 1周 | 1 | 80 | 80 |
| 2周 | 2 | 65 | 145 |
| 3周 | 3 | 90 | 235 |
2周目の行だけを見れば、65 を足して 145 になったと分かる
この列が無いと、何を足したのかを配列まで見に戻ることになる
この列があると、行だけで意味が取れる
2周目の行を見れば、65 を足して 145 になったと分かります。ten[i] の列が無いと、何を足したのかを配列まで見に戻ることになります。
あとは前回までと同じです。1周につき1行。列が1本増えただけで、書き方は変わりません。
擬似言語の配列は1番目から数えます。ten[0] はありません。
配列の中身が書き換わるプログラム
ここまでのプログラムは ten を読んでいるだけでした。ten に書き込む行が1つも無いので、中身は最初から最後まで 80・65・90 のままです。だから配列は、いちばん上に1回書けば足ります。
次のプログラムは、同じ for の中で ten を書き換えます。
整数型の配列: ten ← {80, 65, 90}
整数型: i
for (i を 1 から tenの要素数 まで 1 ずつ増やす)
ten[i] ← ten[i] + 5
endfor
tenの全要素の値を要素番号の順に空白区切りで出力する
出力は 85 70 95 です。3人の点数に、5点ずつ足しています。
解き方
←の左を見る。ten[i]が出てくるなら、配列が書き換わる- 表に
tenの中身をまるごと書く列を作る - 1周ごとに、その周で書き換えた1マスだけを新しい値にして、行を下に1本足す
1周ずつ確かめます。変わるのは、毎周たった1マスだけです。
1周目(i が 1)
ten[1] を読むと 80。5 を足して 85。これを ten[1] に書き戻します。ten は {85, 65, 90} になります。
2番目と3番目はまだ触っていないので、65 と 90 のままです。
2周目(i が 2)
ten[2] を読むと 65。5 を足して 70。ten は {85, 70, 90} になります。
1番目の 85 は、そのまま残っています。前の周で書いた結果は消えません。
3周目(i が 3)
ten[3] を読むと 90。5 を足して 95。ten は {85, 70, 95} になります。
書き換えるプログラムは、中身の列も作る
ten[i] ← ten[i] + 5
読んだ値と、書いたあとの中身を分けて書く
| 周 | 読んだ値 | 書いた値 | ten の中身 |
|---|---|---|---|
| はじめ | ー | ー | {80, 65, 90} |
| 1周 | 80 | 85 | {85, 65, 90} |
| 2周 | 65 | 70 | {85, 70, 90} |
| 3周 | 90 | 95 | {85, 70, 95} |
同じ ten[1] でも、読むときは 80、書いたあとは 85。1本の列だと何に足したのか分からなくなる
前の周で書いた結果は消えない。だから中身は少しずつ変わっていく
ten[1] でも、読むときと書いたあとで値が違う
1周目の ten[1] は、読むときは 80、書いたあとは 85 です。表に 85 とだけ書くと、何に 5 を足したのかが分からなくなります。
だから列を2本作ります。その周に読んだ値の列と、書き換えたあとの中身の列です。読むだけのプログラムで ten[i] の列を作ったのと、同じ理由です。
実際に1行ずつ動かして、毎周1マスだけが書き換わるところを確かめてください。
配列が書き換わるプログラムを1行ずつ動かす
当サイトオリジナルの例題
ループ開始前
配列
いま計算していること
変数の状態
出力
トレース表(進めると1行ずつ積み上がります)
どちらか迷ったら
プログラムを見て、← の左に配列が出てくるかを確かめます。出てこなければ読むだけ。出てくるなら、周ごとに中身を書きます。
書き換えるプログラムは、途中の状態を答えさせる形で出ます。「2周目が終わったとき ten はどうなっているか」のような問いです。
このとき、最後の答えまで進めてしまうと戻れません。周ごとに1行ずつ残しておけば、聞かれた周の行をそのまま読むだけで済みます。
本番では、書く量を減らす
ここまでの書き方は正しく追うための書き方です。試験本番では、これを全部書く時間はありません。
本番では、書く量を減らす
ここまでの書き方は「正しく追うため」の書き方。本番では全部書く時間がない
その1 ── 値が変わらないマスは書かない
| 周 | i | ten[i] | goukei |
|---|---|---|---|
| 1周 | 1 | 80 | 80 |
| 2周 | 2 | 65 | 145 |
| 3周 | 3 | 90 | 235 |
空いたマスは「上と同じ」。ここでは毎周変わるので、あまり減らない
その2 ── 問われている変数だけ書く
| 周 | goukei |
|---|---|
| 1周 | 80 |
| 2周 | 145 |
| 3周 | 235 |
答えが goukei だけなら、i と ten[i] の列は要らない
その3 ── 最初の2周と、最後の周だけ書く
| 周 | i | goukei |
|---|---|---|
| 1周 | 1 | 80 |
| 2周 | 2 | 145 |
| … | … | … |
| 最後 | 3 | 235 |
いちばん効くのがこれ。最初の2周で規則が見えたら、あとは最後の周だけ確かめる
減らしてよいのは、答えに関係しないところだけ。迷ったら書く
いちばん効くのは3つめです。周が10回、20回と続く問題でも、最初の2周を丁寧に書けば規則が見えます。見えたら、あとは最後の周だけ確かめれば足ります。
迷ったら書く。書かずに間違えるほうが、書いて時間を使うより高くつきます。
とくに規則が見えないうちに飛ばさないこと。「たぶんこうなる」で飛ばした周に、答えが入っています。
3回のまとめ
| 回 | 覚えること |
|---|---|
| A1-1 | 1行実行したら1行足す。書くのは値が変わったマスだけ |
| A1-2 | 繰返しは1周を1行。抜けたあとの行も書く |
| A1-3 | 表に「その周に読んだ値」の列を作る。i が動けば読む先も動く |
この3つだけで、科目Bのプログラムはすべて追えます。あとは、追う対象のアルゴリズムを1つずつ覚えていくだけです。
つまずきポイントまとめ
| まちがえ方 | 正しい書き方 |
|---|---|
| 配列の中身だけ書いて、その周に読んだ値を書かない | ten[i] の列を作る。行だけで何を足したか分かるようにする |
| 要素番号を 0 から数える | 擬似言語は1番目から |
| 規則が見える前に周を飛ばす | 最初の2周は丁寧に書く。飛ばすのはそのあと |
| 答えに関係ない変数の列まで作る | 問われている変数だけでよい |
次に読む
| A2-1 | 配列を全部見る ─ ten[i] と for の読み方 |
| A1-2 | 繰返しのトレース ─ 1周を1行に書く |
| G4-1 | 配列と要素番号 ─ 1番目から数える |
| 目次 | 基本情報技術者試験 科目B 攻略ガイド |
この記事で引用した資料
いずれも独立行政法人情報処理推進機構(IPA)が公表したものです。IPAは公表済みの試験問題について、教育目的での使用に許諾および使用料を不要としていますが、著作権は放棄していません。本記事では問題文を改変せずに引用しています。
本文の例題は当サイトのオリジナルです。
