プログラムの設計と読解

1. 文字列とデータの加工

文字の並びや表（二次元配列）を1つずつ見ていって、数える・比べる・作り替える型が読めるようになります。

科目Bの擬似言語では、配列の要素番号（添字）が1から始まります。先頭が a[1] で、最後が a[aの要素数] です。多くのプログラミング言語が0から始まるので、ここを取り違えると答えがすべてずれます。まず「1から要素数まで」が全要素を1回ずつ見る書き方だと体に入れてください。for (i を 1 から aの要素数 まで 1 ずつ増やす) は、終わりの値である aの要素数 も含めて実行されます。逆に for (i を 1 から 0 まで 1 ずつ増やす) のように、始まりが終わりより大きいときは1回も実行されません。要素数が0の配列を渡したときにこの形になるので、空の配列の扱いを考えるときの手がかりになります。

文字列は、文字型の配列として扱われることがよくあります。s[1] が1文字目、s[sの要素数] が最後の文字です。文字どうしを比べるときは = と ≠ を使います（多くの言語で使う二重の等号は、擬似言語では使いません）。文字列をつなぐときは + を使います。文字の並びを1つずつ見ていく処理を走査（トラバース）といい、「特定の文字を数える」「最初に現れる位置を探す」「条件に合う文字だけを取り出す」といった処理は、すべてこの走査の上に作られています。

走査には型があります。1つ目は累算です。cnt ← 0 や sum ← 0 のように結果をためる変数を先に用意し、繰返しの中で少しずつ足していきます。この変数を累算変数といいます。初期値を何にするかが要注意で、合計なら0、積なら1、最大値なら「先頭の要素」にするのが安全です。最大値の初期値を0にしてしまうと、すべての要素が負のときに0という存在しない値を返してしまいます。2つ目は状態の記憶です。論理型の変数（フラグ）に「いま単語の途中かどうか」「まだ条件を満たしているか」を覚えさせ、繰返しの外で最終判断をします。3つ目は2本の添字です。先頭から進む i と末尾から戻る j を同時に動かし、i < j の間だけ繰り返せば、回文の判定や配列の反転が書けます。

回文とは、前から読んでも後ろから読んでも同じ並びのことです。s[i] と s[n - i + 1] が対になります。n - i + 1 という式は、i = 1 のとき n、i = n のとき 1 になる「折り返しの式」で、反転でも頻出します。反転を破壊的に行うときは、必ず作業用の変数を1つ用意して三角形に値を移します。tmp を使わずに a ← b、b ← a と書くと、1行目で a の元の値が消えてしまい、両方が b の値になります。これは科目Bで実際によく出るバグです。

数値と文字の変換もよく出ます。文字の "7" と数値の 7 は別物なので、そのままでは計算できません。数字の並びを数値にするときは、v ← v × 10 + その桁の数値 を先頭の桁から繰り返します。"2047" なら 0→2→20→204→2047 と育っていきます。逆に数値を文字にするときは、10 で割った余りを取り出して対応する文字に置き換え、商が0になるまで繰り返します（この場合は下の桁から出てくるので、最後に反転が要ります）。

二次元配列は表です。m[i][j] は i 行目 j 列目を指します。行数は mの要素数、i 行目の列数は m[i]の要素数 で表します。外側の繰返しで行を、内側の繰返しで列を回すのが基本形で、これを行優先の走査といいます。外と内を入れ替えれば列優先になります。行ごとの合計を出してから、その中の最大や最小を求めるといった二段構えの集計は定番です。このとき、行の集計用変数を内側の繰返しに入る直前で必ず初期化しないと、前の行の値が残って誤った結果になります。初期化の位置が繰返しの内か外かは、必ず行番号で確かめてください。

/* 例1: 文字型の配列 s の中の文字 c の個数を数える */○整数型: countChar(文字型の配列: s, 文字型: c)  整数型: i  整数型: cnt ← 0  for (i を 1 から sの要素数 まで 1 ずつ増やす)    if (s[i] = c)      cnt ← cnt + 1    endif  endfor  return cnt /* 例2: 2本の添字で配列を反転する（tmp が必須） */○reverse(文字型の配列: s)  整数型: i ← 1  整数型: j ← sの要素数  文字型: tmp  while (i < j)    tmp ← s[i]    s[i] ← s[j]    s[j] ← tmp    i ← i + 1    j ← j - 1  endwhile /* 例3: 二次元配列を行優先で走査して全体の合計を出す */○整数型: total(整数型の二次元配列: m)  整数型: i, j  整数型: s ← 0  for (i を 1 から mの要素数 まで 1 ずつ増やす)    for (j を 1 から m[i]の要素数 まで 1 ずつ増やす)      s ← s + m[i][j]    endfor  endfor  return s

用語

添字（そえじ）

配列の何番目かを表す番号。擬似言語では1から始まり、a[1] が先頭、a[aの要素数] が末尾。0から始まる言語の感覚のまま読むと、答えが1つずれる原因になる。

走査（トラバース）

配列や文字列の要素を先頭から末尾まで1つずつ順に見ていくこと。数える、探す、集計する、作り替えるといった処理は、ほとんどがこの走査を土台にして書かれている。

累算変数

繰返しの中で結果をためていく変数。合計なら0、積なら1、最大値なら先頭の要素で初期化するのが安全。初期値の選び方を誤ると、要素がすべて負のときなどに誤った値を返す。

フラグ変数

論理型の変数で、処理の途中の状態（見つかったか、単語の途中か など）を覚えておくために使う。繰返しの中で true や false を設定し、繰返しを抜けた後で最終判断をする。

回文

前から読んでも後ろから読んでも同じになる並び。s[i] と s[n - i + 1] を対にして比べる。要素数が0や1のときは比較が1回も起きず、定義上は回文として扱われる。

折り返しの式 n - i + 1

要素数 n の配列で、先頭から i 番目に対応する末尾からの位置を表す式。i が1のとき n、i が n のとき1になる。反転・回文・左右対称の判定でくり返し登場する。

二次元配列

行と列をもつ表の形のデータ。m[i][j] が i 行 j 列の要素。行数は mの要素数、i 行目の列数は m[i]の要素数 で表す。外側で行、内側で列を回すのが行優先の走査。

破壊的な入替え

配列の要素そのものを書き換えて並びを変えること。a[i] と a[j] を入れ替えるには作業用変数 tmp が必須で、tmp を使わないと片方の値が上書きされて消える。

例題

出典・根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論　中分類2：アルゴリズムとプログラミング／IPA 基本情報技術者試験 試験要綱 Ver.5.6 出題範囲（科目B試験）アルゴリズムとプログラミング

2. オブジェクト指向の擬似言語

クラス定義の擬似言語を、メンバ変数・コンストラクタ・メソッド・継承の順に落ち着いて読めるようになります。

科目Bでは、手続きだけでなくクラスの形で書かれたプログラムも出ます。クラスとは、データ（メンバ変数）と、そのデータを扱う操作（メソッド）をひとまとめにした型の定義です。設計図にあたるものなので、それ自体は値を持ちません。設計図から実際に値をもつ実体を作ったものがインスタンス（オブジェクト）で、作る操作をインスタンス化といいます。1つのクラスから、値の違うインスタンスをいくつでも作れます。データと操作をまとめて外から中身を直接いじれないようにする考え方をカプセル化といい、外に見せる操作の入口をインタフェースといいます。

クラス定義の書き方は問題ごとに冒頭で説明されるので、その場で読み取るのが基本です。この教材では、クラス: クラス名 で定義を始め、その中に メンバ変数の宣言、クラス名と同じ名前の手続き（コンストラクタ）、そのほかの手続き（メソッド）を字下げして並べる形で書きます。コンストラクタはインスタンスを作るときに1回だけ自動で呼ばれる特別なメソッドで、メンバ変数に初期値を入れる役目を持ちます。戻り値の型は書きません。c ← Counter(10) と書けば、Counter のコンストラクタに10が渡され、できたインスタンスが c に入ります。

メソッドの中では、自分のインスタンスのメンバ変数を名前だけで参照できます。ただし引数の名前がメンバ変数と同じだと、どちらを指すのか分からなくなります。そこで「自分自身」を表す this を付けて this.price と書き、引数のほうは price と書いて区別します。this.price ← price は「メンバ変数の price に、引数の price の値を代入する」という意味で、逆ではありません。この向きを取り違えると、メンバ変数がいつまでも初期値のままになります。インスタンスのメソッドを外から呼ぶときは、c.add(5) のように インスタンス名.メソッド名(引数) と書きます。

変数にインスタンスを代入したときの動きにも注意が要ります。p ← Box(3) の後に q ← p と書くと、インスタンスがもう1つ複製されるのではなく、p と q が同じ1つのインスタンスを指すようになります。この状態で q.set(8) を呼ぶと、p から見た値も8に変わります。別の実体が欲しいなら、q ← Box(3) のようにもう一度コンストラクタを呼ばなければなりません。配列やインスタンスは参照として渡されるという前提は、科目Bの引っ掛けどころです。

継承は、既にあるクラスの性質を引き継いで新しいクラスを作る仕組みです。引き継がれる側をスーパクラス（親クラス）、引き継ぐ側をサブクラス（子クラス）といいます。サブクラスは、スーパクラスのメンバ変数とメソッドをそのまま使えるうえに、自分だけの追加もできます。スーパクラスと同じ名前・同じ引数のメソッドをサブクラスで定義し直すことを、オーバーライド（上書き）といいます。名前が同じでも引数の並びが違うものを用意するオーバーロード（多重定義）とは別物なので、混同しないでください。

オーバーライドがあると、同じ呼出しの書き方でも、実際に動くメソッドはインスタンスの本当のクラスによって決まります。これが多相性（ポリモーフィズム）です。スーパクラス Animal に show() があり、その中から name() を呼んでいるとき、サブクラス Dog のインスタンスに対して show() を呼ぶと、中の name() は Dog のほうが動きます。show() 自体は Dog で上書きしていなくても、呼ばれる name() は上書きされたものになるという点が要注意です。逆に、サブクラスで上書きしていないメソッドは、スーパクラスのものがそのまま使われます。Animal 型の配列に Animal と Dog と Cat を混ぜて入れ、同じ書き方で回すだけで、それぞれに応じた結果が並ぶのが多相性の効き目です。

クラス: Counter  /* メンバ変数 */  整数型: value  /* コンストラクタ（クラスと同名・戻り値の型を書かない） */  ○Counter(整数型: value)    this.value ← value  /* メソッド */  ○add(整数型: d)    value ← value + d  ○整数型: get()    return value クラス: TwiceCounter（Counter を継承する）  ○TwiceCounter(整数型: value)    this.value ← value  /* add を上書きする（オーバーライド） */  ○add(整数型: d)    value ← value + d × 2 ○整数型: main()  Counter: a  TwiceCounter: b  a ← Counter(10)  b ← TwiceCounter(10)  a.add(3)  b.add(3)  return a.get() + b.get()

用語

クラス

データ（メンバ変数）と操作（メソッド）をひとまとめにした型の定義。設計図にあたり、それ自体は値を持たない。同じクラスから値の異なるインスタンスをいくつでも作れる。

インスタンス（オブジェクト）

クラスから作られた、実際に値をもつ実体。作る操作をインスタンス化という。同じクラスの別インスタンスどうしは、メンバ変数の値を独立に持つ。

メンバ変数

クラスが持つデータを入れる変数。インスタンスごとに別の値を保持する。メソッドの中からは名前だけで参照でき、引数と名前が重なるときは this を付けて区別する。

コンストラクタ

インスタンスを作るときに1回だけ自動で呼ばれる特別なメソッド。クラスと同じ名前で、戻り値の型を書かない。メンバ変数に初期値を設定するのが主な役目。

this（自分自身）

メソッドの中で、そのメソッドが動いているインスタンス自身を指す書き方。this.x ← x は「メンバ変数 x に引数 x の値を入れる」意味で、代入の向きを逆に読まないよう注意する。

継承

既存のクラス（スーパクラス）の性質を引き継いで新しいクラス（サブクラス）を作る仕組み。共通部分を親にまとめられるので、同じ記述の重複を減らせる。

オーバーライド（上書き）

スーパクラスと同じ名前・同じ引数のメソッドを、サブクラスで定義し直すこと。呼び出したときはサブクラスのほうが動く。引数の並びを変えて別に定義するオーバーロードとは異なる。

多相性（ポリモーフィズム）

同じ呼出しの書き方でも、インスタンスの実際のクラスに応じて動くメソッドが変わる性質。スーパクラス型の配列に子クラスを混ぜても、同一の記述でそれぞれの動作をさせられる。

カプセル化

データと、それを扱う操作を1つにまとめ、外部からはメソッドを通じてしか触れないようにすること。内部の作りを変えても外側に影響が出にくくなる。

例題

出典・根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類4：開発技術　中分類12：システム開発技術（オブジェクト指向設計）／IPA 基本情報技術者試験 試験要綱 Ver.5.6 出題範囲（科目B試験）アルゴリズムとプログラミング

3. 仕様から手続きを組み立てる

仕様どおりに動くかを机上で確かめ、境界と計算量を押さえ、バグの位置を突き止める手順が身につきます。

科目Bの問題文には、たいてい「この手続きは何をするものか」という仕様が日本語で書かれています。まずこの仕様を、入力・出力・前提条件の3つに分けて書き出してください。入力は引数の型と意味、出力は戻り値の型と意味、前提条件は「要素数は1以上とする」「配列は昇順に整列済みとする」といった、成り立っていることにしてよい条件です。前提条件が書かれていない部分は、こちらで守らなければならない部分です。たとえば「要素数が0のときは0を返す」と仕様に書いてあるのに、手続きにその分岐が無ければ、それだけで仕様違反になります。

次に、実際に値を入れて手で動かします。これをトレースといいます。おすすめは表を作る方法です。左端に行番号または繰返しの回数、その右に変数を1列ずつ並べ、値が変わったところだけ書き込みます。頭の中だけで追うと必ずどこかで取り違えるので、面倒でも書くほうが速くて確実です。トレースする値の選び方にはこつがあり、答えが一目で分かる小さな入力（要素数3程度）と、境界の入力の2種類を用意します。

境界とは、動きが切り替わる境目のことです。科目Bで問われる境界はだいたい決まっています。要素数が0のとき、要素数が1のとき、探しているものが先頭にあるとき、末尾にあるとき、まったく無いとき、同じ値が複数あるとき、値がすべて負のとき、の7つです。要素数が0なら for (i を 1 から 0 まで 1 ずつ増やす) となって繰返しは1回も実行されず、累算変数の初期値がそのまま返ります。合計なら0で正しくても、平均なら0による除算になって破綻します。要素数が1なら、隣どうしを比べる繰返し（1 から n - 1 まで）はやはり0回です。探しているものが先頭にあるときは、繰返しの1回目で return できるか、末尾にあるときは最後の要素まで届くかを確かめます。同じ最大値が複数あるときは、比較に > を使うか ≧ を使うかで「最初の位置」か「最後の位置」かが変わります。この1文字が正解と誤答を分けます。

計算量は、入力の大きさ n が増えたときに手間がどう増えるかの見積りです。繰返しが1重なら n に比例して O(n)、二重で内側が n 回なら O(n^2)、二重でも内側が i + 1 から n までなら回数は n(n - 1) / 2 なので、やはり O(n^2) です。半分ずつ候補を捨てていく二分探索は O(log n) で、要素数1000なら最悪10回の比較で終わります（2の9乗が512、2の10乗が1024なので、1024以下なら10回で足りる）。整列は、単純な交換法（バブルソート）や選択法・挿入法が O(n^2)、クイックソートやマージソート、ヒープソートが平均 O(n log n) です。定数倍は無視して、n が大きくなったときの増え方だけを見るのが計算量の考え方です。

バグを直すときは、当てずっぽうに書き換えず、位置を絞ってから直します。手順は3段階です。1つ目は、仕様どおりの結果と実際の結果が食い違う最小の入力を見つけること。2つ目は、その入力でトレースし、変数の値が初めておかしくなる行を特定すること。3つ目は、その行だけを仕様に照らして直すことです。頻出のバグは型が決まっていて、添字の1ずれ（n と n - 1、i と i + 1 の取り違え）、初期化の位置ずれ（内側の繰返しに入る前で初期化すべき変数を外に置いた）、最大値の初期値を0にした、入替えで作業用変数を使わなかった、境界の分岐が抜けている、比較演算子の > と ≧ の取り違え、の6つです。選択肢に行番号が書いてあるときは、必ずその行を目で追って、書いてあるとおりの記述かどうかを先に確かめてください。

/* 仕様: 昇順に整列済みの配列 a から値 x を二分探索する。 *//*       見つかればその添字、見つからなければ0を返す。   */○整数型: bsearch(整数型の配列: a, 整数型: x)  整数型: lo ← 1  整数型: hi ← aの要素数  整数型: mid  while (lo ≦ hi)    mid ← (lo + hi) ÷ 2 の商    if (a[mid] = x)      return mid    elseif (a[mid] < x)      lo ← mid + 1    else      hi ← mid - 1    endif  endwhile  return 0 a ← {2, 5, 8, 11, 14, 17, 20}、x ← 17 のトレース  回  lo  hi  mid  a[mid]  判定  1    1   7    4     11    11 < 17 なので lo ← 5  2    5   7    6     17    一致するので 6 を返す 境界: aの要素数 が0のとき lo ← 1、hi ← 0 となり、      7行目の lo ≦ hi が最初から成り立たないので0が返る

用語

仕様

その手続きが何を受け取り、何を返し、どんな条件のもとで動くかを定めたもの。入力・出力・前提条件の3つに分けて読むと、確かめるべき点がはっきりする。

トレース（机上実行）

実際に値を入れて、プログラムを1行ずつ手で追いかけること。行番号と変数を表にして、値が変わったところだけ書き込むと、取り違えが起きにくい。

境界値

動きが切り替わる境目の入力。要素数0、要素数1、先頭・末尾に目的の値がある場合、該当なし、同じ値が複数ある場合などが代表例で、バグはここに集中する。

0による除算

0で割ろうとして処理が破綻すること。合計を要素数で割って平均を出す手続きでは、要素数が0のときに起きるため、割る前に要素数を調べる分岐が必要になる。

添字の1ずれ

n と n - 1、i と i + 1 のように、繰返しの範囲や参照位置が1つずれるバグ。末尾の要素を見落とす、または範囲外を参照する形で表れる。境界の入力で見つかりやすい。

計算量

入力の大きさ n に対して処理の手間がどう増えるかの見積り。1重の繰返しは O(n)、二重は O(n^2)、半分ずつ絞る二分探索は O(log n)。定数倍は無視して増え方だけを見る。

二分探索

昇順に整列済みの配列で、真ん中と比べて候補を半分ずつ捨てていく探索。1回の比較で候補が半減するので、要素数 n に対し最悪でも約 log2(n) 回の比較で終わる。

参照渡し

配列やインスタンスを引数として渡すとき、値の複製ではなく実体そのものを指す情報が渡されること。呼ばれた側で書き換えると、呼んだ側の配列も変わる。

例題

出典・根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論　中分類2：アルゴリズムとプログラミング（アルゴリズムの設計・計算量）／IPA 基本情報技術者試験 試験要綱 Ver.5.6 出題範囲（科目B試験）アルゴリズムとプログラミング

演習：この章の問題を解く

ランダム出題の演習ツールです（JavaScript が有効な場合に動きます）。上の「確認問題」はそのままでもすべて読めます。