午後問題対策 プログラミング

はじめに

本稿は，応用情報技術者試験 午後の出題分野の一つである「プログラミング」の対策についてまとめたものである。

より実践的な対策となるよう，各テーマについてプログラムを作成している。なお，プログラムには，Python，または，フリーの高機能数値計算ツールである Octave を使用している。

目次

• 令和5年度 秋期 午後 問3　2 分探索木
• 令和5年度 春期 午後 問3　多倍長整数の演算
• 令和4年度 秋期 午後 問3　迷路の探索処理
• 令和4年度 春期 午後 問3　パズルの解答を求めるプログラム
• 令和3年度 秋期 午後 問3　一筆書き
• 令和3年度 春期 午後 問3　クラスタ分析に用いる k-means 法
• 令和2年度 午後 問3　誤差拡散法による減色処理
• 令和元年度 秋期 午後 問3　ニューラルネットワーク
• 平成31年度 春期 午後 問3　券売機の注文の状態を判定するプログラム
• 平成30年度 秋期 午後 問3　ウェーブレット木
• 平成30年度 春期 午後 問3　ナイトの巡歴問題
• 平成29年度 秋期 午後 問3　ナップザック問題
• 平成29年度 春期 午後 問3　探索アルゴリズム
• 平成28年度 秋期 午後 問3　魔法陣
• 平成28年度 春期 午後 問3　ライフゲーム
• 平成27年度 秋期 午後 問3　2 分探索木
• 平成27年度 春期 午後 問3　データ圧縮の前処理として用いられる Block-sorting
• 平成26年度 秋期 午後 問3　マージソート
• 平成26年度 春期 午後 問3　循環小数の循環節を検出するアルゴリズム
• 平成25年度 秋期 午後 問2　リストによるメモリ管理
• 平成25年度 春期 午後 問2　一般的な表記法の数式を逆ポーランド表記法に変換するアルゴリズム
• 平成24年度 秋期 午後 問2　N クイーン問題
• 平成24年度 春期 午後 問2　文字列を圧縮するアルゴリズム
• 平成23年度 秋期 午後 問2　ハッシュ法と排他制御
• 平成23年度 春期 午後 問2　集計表を HTML に変換して出力するプログラム
• 平成22年度 秋期 午後 問2　構文解析
• 平成22年度 春期 午後 問2　アプリケーションで使用するデータ構造とアルゴリズム
• 平成21年度 秋期 午後 問2　文字列照合処理
• 平成21年度 春期 午後 問2　チェイン法（探索アルゴリズムであるハッシュ法の一つ）
• 本稿の参考文献

令和5年度 秋期 午後 問3　2 分探索木

2 分探索木とは，木に含まれる全てのノードがキー値をもち，各ノード N が次の二つの条件を満たす 2 分木のことである。ここで，重複したキー値をもつノードは存在しないものとする。

• N の左側の部分木にある全てのノードのキー値は，N のキー値よりも小さい。
• N の右側の部分木にあるすべてのノードのキー値は，N のキー値よりも大きい。

2 分探索木の例を図 1 に示す。図中の数字はキー値を表している。

2 分探索木をプログラムで表現するために，ノードを表す構造体 Node を定義する。構造体 Node の構成要素を表 1 に示す。

構造体 Node を新しく生成し，その構造体への参照を変数 p に代入する式を次のように書く。

ここで，引数 k は生成するノードのキー値であり，構成要素 key の初期値となる。構成要素 left 及び right は，参照するノードがないこと（以下，空のノードという）を表す NULL で初期化される。また，生成した p の各構成要素へのアクセスには "." を用いる。例えば，キー値は p.key でアクセスする。

2 分探索木におけるノードの探索・挿入

キー値 k をもつノードの探索は次の手順で行う。

(1) 探索対象の 2 分探索木の根を参照する変数を t とする。

(2) t が空のノードであるかを調べる。

(2-1) t が空のノードであれば，探索失敗と判断して探索を終了する。

(2-2) t が空のノードでなければ，t のキー値 t.key と k を比較する。

• t.key = k の場合，探索成功と判断して探索を修了する。
• t.key > の場合，t の左側の子ノードを新たな t として (2) から処理を行う。
• t.key < の場合，t の右側の子ノードを新たな t として (2) から処理を行う。

キー値 k をもつノード K の挿入は，探索と同様の手順で根から順にたどっていき，空のノードが見つかった位置にノード K を追加することで行う。ただし，キー値 k と同じキー値をもつノードが既に 2 分探索木中に存在するときは何もしない。

これらの手順によって探索を行う関数 search のプログラムを図 2 に，挿入を行う関数 insert のプログラムを図 3 に示す。関数 search は，探索に成功した場合は見つかったノードへの参照を返し，失敗した場合は NULL を返す。関数 insert は，得られた木の根への参照を返す。

// t が参照するノードを根とする木からキー値が k であるノードを探索する
function search(t, k)
	if(t が NULL と等しい)
		return NULL
	elseif(t.key が k と等しい)
		return t
	elseif(t.key が k より大きい)
		return search(t.left, k)
	else // t.key が k より小さい場合
		return search(t.right, k)
	endif
endfunction

// t が参照するノードを根とする木にキー値が k であるノードを挿入する
function insert(t, k)
	if (t が NULL と等しい)
		t ← new Node(k)
	elseif(t.key が k より大きい)
		t.left ← insert(t.left, k)
	elseif(t.key が k より小さい)
		t.right ← insert(t.right, k)
	endif
	return t
endfunction

関数 search を用いてノードの総数が n 個の 2 分探索木を探索するとき，探索に掛かる最悪の場合の時間計算量（以下，最悪時間計算量という）は O(ア) である。これは葉を除くすべてのノードについて左右のどちらかにだけ子ノードが存在する場合である。一方で，葉を除く全てのノードに左右両方の子ノードが存在し，また，全ての葉の深さが等しい完全な 2 分探索木であれば，最悪計算時間量は O(イ) となる。したがって，高速に探索するためには，なるべく左右両方の子ノードが存在するように配置して，高さができるだけ低くなるように構成した木であることが望ましい。このような木のことを平衡 2 分探索木という。

2 分探索木における回転操作

2 分探索木中のノード X と X の左側の子ノード Y について，X を Y の右側の子に，元の Y の右側の部分木を X の左側の部分木にする変形操作を右回転といい，逆の操作を左回転という。回転操作後も 2 分探索木の条件は維持される。木の回転の様子を図 4 に示す。ここで，t₁ ～ t₃ は部分木を表している。また，根から t₁ ～ t₃ の最も深いノードまでの深さを，図 4 (a) では d₁ ～ d₃，図 4 (b) では d₁' ～ d₃' でそれぞれ表している。ここで，d₁' = d₁ - 1，d₂' = d₂，d₃' = d₃ + 1 が成り立つ。

右回転を行う関数 rotateR のプログラムを図 5 に，左回転を行う関数 rotateL のプログラムを図 6 に示す。これらの関数は，回転した結果として得られた木の根への参照を返す。

// t が参照するノードを根として木に対して右回転を行う
function rotateR(t)
	a ← t.left
	b ← a.right
	a.right ← t
	t.left ← b
	retrun a
endfunction

// t が参照するノードを根として木に対して左回転を行う
function rotateL(t)
	a ← t.right
	b ← a.left
	a.left ← t
	t.right ← b
	retrun a
endfunction

回転操作を利用した平衡 2 分探索木の構成

全てのノードについて左右の部分木の高さの差が 1 以下という条件（以下，条件 bal という）を考える。条件 Bal を満たす場合，完全ではないときでも比較的左右均等にノードが配置された木になる。

条件 Bal を満たす 2 分探索木 W に対して図 3 の関数 insert を用いてノードを挿入した 2 分探索木を W' とすると，ノードが挿入される位置によっては左右の部分木の高さの差が 2 になるノードが生じ野で，W' は条件 Bal を満たさなくなることがある。その場合，挿入したノードから根まで，親をたどった各ノード T に対して順に次の手順を適用することで，条件 Bal を満たすように W' を変形することができる。

(1) T の左側の部分木の高さが T の右側の部分木の高さより 2 大きい場合

T を根とする部分木に対して右回転を行う。ただし，T の左側の子ノード U について，U の右側の部分木の方が U の左側の部分木よりも高い場合は，先に U を根とする部分木に対して左回転を行う。

(2) T の右側の部分木の高さが T の左側の部分木の高さより 2 大きい場合

T を根とする部分木に対して左回転を行う。ただし，T の右側の子ノード V について，V の左側の部分木の方が V の右側の部分木よりも高い場合は，先に V を根とする部分木に対して右回転を行う。

この手順 (1)，(2) によって木を変形する関数 balance のプログラムを図 7 に，関数 balance を適用するように関数 insert を修整した関数 insertB のプログラムを図 8 に示す。ここで，関数 height は，引数で与えられたノードを根とする木の高さを返す関数である。関数 balance は，変形の結果として得られた木の根への参照を返す。

// t が参照するノードを根とする木を条件 Bal を満たすように変形する
function balance(t)
	h1 ← height(t.left) - height(t.right)
	if (ウ)
		h2 ← エ
		if (h2 が 0 より大きい)
			t.left ← rotateL(t.keft)
		endif
		t ← rotateR(t)
	endif(オ)
		h3 ← カ
		if (h3 が 0 より大きい)
			t.right ← rotateR(t.right)
		endif
		t ← rotateL(t)
	endif
	return t
endfunction

// t が参照するノードを根とする木にキー値が k であるノードを挿入する
function insertB(t, k)
	if (t が NULL と等しい)
		t ← new Node(k)
	elseif(t.key が k より大きい)
		t.left ← insertB(t.left, k)
	elseif(t.key が k より小さい)
		t.right ← insertB(t.right, k)
	endif
	t ← balance(t) //追加
	return t
endfunction

条件 Bal を満たすノードの総数が n 個の 2 分探索木に対して関数 insertB を実行した場合，挿入に掛かる最悪時間計算量は O(キ) となる。

設問

設問 1

本文中の ア，イ に入れる適切な字句を答えよ。

アは n，イは log n である。

設問 2

［回転操作を利用した平衡 2 分探索木の構成］について答えよ。

(1) 図 7 中の ウ ～ カ に入れる適切な字句を答えよ。

• ウ：h1 が 2 と等しい
• エ：height(t.left.right) - height(t.left.left)
• オ：h1 が -2 と等しい
• カ：height(t.right.left) - height(t.right.right)

(2) 図 1 の 2 分探索木の根を参照する変数を r としたとき，次の処理を行うことで生成される 2 分探索木を図示せよ。2 分探索木は図 1 に倣って表現すること。

(3) 本文中の キ に入れる適切な字句を答えよ。なお，図 7 中の関数 height の処理時間は無視できるものとする。

log n である。

令和5年度 春期 午後 問3 多倍長整数の演算

コンピュータが一度に処理できる整数の最大桁には，CPU が一度に扱える情報量に依存した限界がある。一度に扱える桁数を超える演算を行う一つの方法として，10 を基数とした多倍長整数（以下，多倍長整数という）を用いる方法がある。

多倍長整数の加減算

多倍長整数の演算では，整数の桁ごとの値を，1 の位から順に 1 次元配列に格納して管理する。例えば整数 123 は，要素数が 3 の配列に {3, 2, 1} を格納して表現する。

多倍長整数の加算は，“桁ごとの加算” の後，“繰り上がり” を処理することで行う。456 + 789 を計算した例を図 1 に示す。

“桁ごとの加算” を行うと，配列の内容は {15, 13, 11} とんる。1 の位は 15 になるが，15 は 10 × 1 + 5 なので，10 の位である 13 に 1 を繰り上げて {5, 14, 11} とする。これを最上位まで繰り返す。最上位で繰り上がりが発生する場合は，配列の要素数を増やして対応する。減算も同様に “桁ごとの減算” と “繰り下がり” との処理で計算できる。

多倍長整数の乗算

多倍長整数の乗算については，計算量を削減するアルゴリズムが考案されており，その中の一つにカラツバ法がある。ここでは，桁数が 2 のべき乗で，同じ桁数をもった正の整数同士の乗算について，カラツバ法を適用した計算を行うことを考える。桁数が 2 のべき乗でない整数や，桁数が異なる整数同士の乗算を扱う場合は，上位の桁を 0 で埋めて処理する。例えば，123 × 4 は 01234 × 0004 として扱う。

ツリー構造の構築

カラツバ法を適用した乗算のアルゴリズムは，計算のためのツリー構造（以下，ツリーという）を作る処理と，ツリーを用いて演算をする処理から成る。ツリーは，多倍長整数の乗算の式を一つのノードとし，一つのノードは 3 個の子ノードをもつ。

M 桁 × M 桁の乗算の式について，乗算記号の左右にある値を，それぞれ M/2 桁ずつに分けて A，B，C，D の四つの多倍長整数を作る。これらの整数を使って，① A × C，② B × D，③(A + B) × (C + D) の 3 個の子ノードを作り，M/2 桁 × M/2 桁の乗算を行う層を作る。(A + B)，(C + D) は多倍長整数の加算であるが，ここでは “桁ごとの加算” だけを行い，“繰り上がり” の処理はツリーを用いて行う演算の最後でまとめて行う。生成した子ノードについても同じ処理を繰り返し，1 桁 × 1 桁の乗算を行う最下層のノードまで展開する。

1234 × 5678 についてのツリーを図 2 に示す。図 2 の層 2 の場合，① は 12 × 56，② は 34 × 78 となる。③ の (C + D) は，“桁ごとの加算” だけの処理を行うと，10 の位が 5 + 7 = 12，1 の位が 6 + 8 = 14 となるので，12 × 10 + 14 = 134 となる。

ツリーを用いた演算

ツリーの最下層ノードは，整数の乗算だけで計算できる。最下層以外の層は，子ノードの計算結果を使って，次の式で計算できることがわかっている。ここで，α，β，γ は，それぞれ子ノード ①，②，③ の乗算の計算結果を，K は対象のノードの桁数を表す。

図 2 のルートノードの場合，K = 4，α = 672，β 2652，γ = 6164 なので，計算結果は次のとおりとなる。

多倍数整数の乗算のプログラム

桁数が 2 のべき乗の多倍数整数 val1，val2 の乗算を行うプログラムを作成した。

プログラム中で利用する多倍数整数と，ツリーのノードは構造体で取り扱う。構造体の型と要素を表 1 に示す。構造体の各要素には，構造体の変数名，要素名でアクセスできる。また，配列の添字は 1 から始まる。

多倍長整数の操作を行う関数を表 2 に，プログラムで使用する主な変数，配列及び関数を表 3 に，与えられた二つの多倍長整数からツリーを構築するプログラムを図 3 に，そのツリーを用いて演算を行うプログラムを図 4 に，それぞれ示す。表 2，表 3 中の p，q，v1，v2 の型は多倍長整数である。また，図 3，図 4 中の変数は全て大域変数である。

令和4年度 秋期 午後 問3 迷路の探索処理

始点と終点を任意の場所に設定する n × m の 2 次元のマスの並びから成る迷路の解を求める問題を考える。本問の迷路では次の条件で解を見つける。

• 迷路内には障害物のマスがあり，n × m のマスを囲む外壁のマスがある。障害物と外壁のマスを通ることはできない。
• 任意のマスから，そのマスに隣接し，通ることのできるマスに移動できる。迷路の解とは，この移動の繰返しで始点から終点にたどり着くまでのマスの並びである。ただし，迷路の解では同じマスを 2 回以上通ることはできない
• 始点と終点は異なるマスに設定されている。

5 × 5 の迷路の例を示す。解が一つの迷路の例を図 1 に，解が複数（四つ）ある迷路の例を図 2 に示す。

迷路の解を見つける探索

迷路の解を全て見つける探索の方法を次のように考える。

迷路の外壁と各マスの位置を x 座標と y 座標で表し，各マスについてそのマスに関する情報（以下，マス情報という）を考える。与えられた迷路に対して，障害物と外壁のマス情報には NG フラグを，それ以外のマス情報には OK フラグをそれぞれ設定する。マス情報全体の迷路図情報という。

探索する際の "移動" には，"進む" と "戻る" の二つの動作がある。"進む" は，現在いるマスから ① y 座標を 1 増やす，② x 座標を 1 増やす，③ y 座標を 1 減らす，④ x 座標を 1 減らす，のいずれかの方向に動くことである。マスに "進む" と同時にそのマスのマス情報に足跡フラグを入れる。足跡フラグが入ったマスには "進む" ことはできない。"戻る" は，今いるマスから "進んで" きた一つ前のマスに動くことである。マスに "移動" したとき，移動先のマスを "訪問" したという。

探索は，始点のマストマス情報に足跡フラグを入れ，始点のマスを "訪問" したマスとして，始点のマスから開始する。現在いるマスから次のマスに "進む" 試みを ① ～ ④ の順に行い，もし試みた方向のマスに "進む" ことができないならば，次の方向に "進む" ことを試みる。4 方向いずれにも "進む" ことができないときには，現在いるマスのマス情報を OK フラグに戻し，一つ前のマスに "戻る"。これを終点に到達するまで繰り返す。終点に到達したとき，始点から終点まで "進む" ことでたどってきたマスの並びが迷路の解の一つとなる。

迷路の解を見つけた後も，他の解を見つけるために，終点から一つ前のマスに "戻り"，迷路の探索を続け，全ての探索を行ったら終了する。迷路を探索している間，それまでの経過をスタックに格納しておく。終点にたどり着いた時点でスタックの内容を順番にたどると，それが解の一つになる。

図 1 の迷路では，始点から始めて，(1,1) → (1,2) → (1,3) → (1,4) → (1,5) → (2,5) → (1,5) → (1,4) のように "移動" する。ここまででマスの "移動" は 7 回起きていて，このときスタックには経過を示す 4 個の座標が格納されている。さらに探索を続けて，始めから 13 回目の "移動" が終了した時点では，スタックには ア 個の座標が格納されている。

迷路の解を全て求めて表示するプログラム

迷路の解を全て求めて表示するプログラムを考える。プログラム中で使用する主な変数，定数及び配列を表 1 に示す。配列の添字は全て 0 から始まり，要素の初期値は全て 0 とする。迷路を探索してマスを "移動" する関数 visit のプログラムを図 3 に，メインプログラムを図 4 に示す。メインプログラム中の変数及び配列は大域変数とする。

function visit(x,y)
	maze[x][y] ← VISITED           //足跡フラグを入れる
	stack_visit[stack_top] ← (x,y) //スタックに座標を入れる
	if(x が goal_x と等しい かつ y が goal_y と等しい)
		for (k を 0 から stack_top まで 1 ずつ増やす)
			［イ］ ← stack_visit[k]
		endfor
		sol_num ← sol_num+1
	else
		stack_top ← stack_top + 1
		if(maze[x][y+1] が OK と等しい)
			visit(x,y+1)
		endif
		if(maze[x+1][y] が OK と等しい)
			visit(x+1,y)
		endif
		if(maze[x][y-1] が OK と等しい)
			visit(x,y-1)
		endif
		if(maze[x-1][y] が OK と等しい)
			visit(x-1,y)
		endif
		stack_top ← ［ウ］
	endif
	[エ] ← OK
endfunction

function main
  stack_top ← 0
	sol_num → 0
	maze[x][y] に迷路図情報を設定する。
	start_x, start_y, goal_x, goal_y に始点と終点の座標を設定する。
	visit(start_x, start_y)
	if ( オ が 0 と等しい)
	  "迷路の解が見つからなかった" と印字する
  else
	  paths[][] を順に全て印字する
  endif
endfunction

解が複数ある迷路

図 2 は解が複数ある迷路の例で，一つ目の解が見つかった後に，他の解を見つけるために，迷路の探索を続ける。一つ目の解が見つかった後で，最初に実行される vist の引数の値は カ である。この引数の座標を起点として二つ目の解が見つかるまでに，マスの "移動" は キ 回起き，その間に座標が (4,2) のマスは ク 回 "訪問" される。

解答

設問１

• ア：board[x] が 0 でない
• イ：x+1
• ウ：check_ok(n, x) が true と等しい
• エ：0

設問２

• オ：div(x, 9)*9
• カ：board[row_top+i] が n と等しい
• キ：mod(x, 9)
• ク：board[column_top+9*i] が n と等しい
• ケ：mod(div(x,9)*9, 27)

設問３

• 処理 A：データ構造 Z を退避する
• 処理 B：退避したデータ構造 Z を取り出す

解答例

解が一つの迷路の例

解が一つの迷路の例の経路を下図に示す。

令和4年度 春期 午後 問3 パズルの解答を求めるプログラム

太線で 3×3 の枠に区切られた 9×9 のマスから成る正方形の盤面に，1～9 の数字を入れるパズルの解答を求めるプログラムを考える。このパズルは，図 1 に示すように幾つかのマスに数字が入れられている状態から，数字の入っていない各升に，1～9 のうちのどれか一つの数字を入れていく。このとき，盤面の横 1 行，縦 1 列，及び太線で囲まれた 3×3 の枠内の全てにおいて，1～9 の数字が一つずつ入ることが，このパズルのルールである。パズルの問題例を図 1 に，図 1 の解答を図 2 に示す。

このパズルを解くための方針を次に示す。

この方針に沿ってパズルを解く手順を考える。

パズルを解く手順

1. 盤面の左上端から探索を開始する。マスは左端から順に右方向に探索し，右端に達したら一行下がり，左端から順に探索する。
2. 空白のマスを見つける。
3. 2. で見つけた空白のマスに，1～9 の数字を順番に入れる。
4. 数字を入れたときに，その状態がパズルのルールにのっとっているかどうかをチェックする。
   1. ルールにのっとっている場合は，2. に進んで次の空白のマスを見つける。
   2. ルールにのっとっていない場合は，3. に戻って次の数字を入れる。このとき，入れる数字がない場合には，マスを空白に戻して一つ前に数字を入れたマスに戻り，3. から再開する
5. 最後のマスまで数字が入り，空白のマスがなくなったら，それが解答となる。

盤面の表現

この手順をプログラムに実装するために，9×9 の盤面を次のデータ構造で表現することにした。

• 9×9 の盤面を 81 個の要素をもつ 1 次元配列 board で表現する。添字は 0 から始まる。各要素にはマスに入れられた数字が格納され，空白の場合は 0 を格納する。

配列 board による盤面の表現を図 3 に示す。ここで括弧内の数字は配列 board の添字を表す。

ルールのチェック方法

パズルのルールにのっとっているかどうかのチェックでは，数字を入れたマスが含まれる横 1 行の左端のマス，縦 1 列の上端のマス，3×3 の枠内のマスを特定し，行，列，枠内のマスに既に格納されている数字と，入れた数字がそれぞれ重複していないことを確認する。このチェックを "重複チェック" という。

解法のプログラム

プログラムで使用する配列，関数，変数及び定数の一部を表 1 に示す。なお，表 1 の配列及び変数は大域変数とする。

解放プログラムのメインプログラムを図 4 に，関数 solve のプログラムを図 5 に，重複チェックを行うプログラムの一部を図 6 に示す。

function main()
  board[] を初期化する  //問題を盤面に設定する。
  solve(0)              //盤面の左上端のマスを示す添字を引数として関数 solve を呼び出す
endfunction

function solve(x)
  if (x が MAX_BOARD-1 より大きい)
    print_board()      //解答を出力する
    exit()             //メインプログラムの処理を終了する
  else
    if( ア )           //対象のマスが空白でない場合（ア：board[x] が 0 でない）
      sovle( イ )      //次の探索（イ：x+1）
    else
      for(n を 1 から 9 まで 1 ずつ増やす) //1～9 の順にマスに入れる
        if( ウ )       //（ウ：check_ok(n,x) が true と等しい）
          board[x]←n
          solve(イ)    //次の探索
          board[x]←エ //再帰から戻った場合のマスの初期化（エ：0）
        endif
      endfor
    endif
  endif
endfunction

function row_ok(n,x) //横 1 行の重複チェック
  row_top ← オ //行の左端のマスを示す添字を求める（div(x,9)*9）
  for(i を 0 から 8 まで 1 ずつ増やす)
    if( カ )   //（カ：board[row_top + i] が n と等しい）
      return false
    endif
  endfor
  return true
endfunction

function column_ok(n,x) //縦 1 列の重複チェック
  column_top ← ( キ )   //（キ：mod(x,9)）
  for(i を 0 から 8 まで 1 ずつ増やす)
    if( ク )            //（ク：board[column_top+9*i] が n と等しい）
      return false
    endif
  endfor
  return true
endfunction

function frame_ok(n,x) //3×3の枠内の重複チェック
  frame_top ← x - ケ - mod(x,3) //枠内の左上端のマスを示す添字を求める（ケ：mod(div(x,9)*9,27)）
  for(i を 0 から 2 まで 1 ずつ増やす)
    for(j を 0 から 2 まで 1 ずつ増やす)
      if(board[frame_top + 9*i + j] が n と等しい)
        return false
      endif
    endfor
  endfor
  return true
endfunction

プログラムの改善

解法のプログラムは深さ優先探索であり，探索の範囲が広くなるほど，再帰呼出しの回数が指数関数的に増加し，重複チェックの実行回数も増加する。

そこで，重複チェックの実行回数を少なくするために，各マスに入れることができる数字を保持するためのデータ構造 Z を考える。データ構造 Z は 盤面のマスの数 × 9 の要素をもち，添字 x は 0 から，添字 n は 1 から始まる 2 次元配列とする。Z[x][n] は，ゲームのルールにのっとって board[x] に数字 n を入れることができる場合は要素に 1 を，できない場合は要素に 0 を格納する。データ構造 Z の初期化処理と更新処理を表 2 のように定義した。

なお，データ構造 Z は大域変数として導入する。

「パズルを解く手順」の 1. の前にデータ構造 Z の初期化処理を追加し，「パズルを解く手順」の 2. ～ 5. を次の 2. ～ 4. のように変更した。

2. 空白のマスを見つける。
3. データ構造 Z を参照し，2. で見つけた空白のマスに入れることができる数字のリストを取得し，リストの数字を順番に入れる。
   1. 入れる数字がある場合，① 処理 A「データ構造 Z を退避する」を行った後，マスに数字を入れる。その後，データ構造 Z の更新処理を行い，2. に進んで次の空白のマスを見つける。
   2. 入れる数字がない場合，マスを空白に戻し，② 処理 B「退避したデータ構造 Z を取り出す」を行った後，一つ前に数字を入れたマスに戻り，戻ったマスで取得したリストの次の数字から再開する。
4. 最後のマスまで数字が入り，空白のマスがなくなったら，それが解答となる。

解説

ナンプレ（数独）の解答を求めるプログラムを実装する問題である。

Python で実装したプログラム

Python で実装したプログラムを以下に示す。

import sys

board = [2,0,1,0,9,0,7,0,0,
         0,4,0,2,0,0,3,0,0,
         5,0,0,0,0,8,0,2,9,
         0,9,0,6,7,0,2,0,0,
         6,0,0,3,0,5,0,0,4,
         0,0,7,0,4,9,0,1,0,
         7,6,0,9,0,0,0,0,3,
         0,0,9,0,0,6,0,4,0,
         0,0,4,0,1,0,6,0,0]

MAX_BOARD = 81

# board[] の内容を 9×9 の形に出力する関数
def print_board(board):
    for m in range(0,73,9):
        print(board[m],board[m+1],board[m+2],'|',board[m+3],board[m+4],board[m+5],'|',board[m+6],board[m+7],board[m+8])
        if(m==18 or m==45):
            print('---------------------')

# 横 1 行の重複チェックを行う関数
def row_ok(n,x):
    row_top = x//9*9
    for i in range(0,9,1):
        if(board[row_top+i]==n):
            return False
    return True

# 縦 1 列の重複チェックを行う関数
def column_ok(n,x):
    column_top = x % 9
    for i in range(0,9,1):
        if(board[column_top+9*i]==n):
            return False
    return True

# 3×3 の枠内の重複チェックを行う関数
def frame_ok(n,x):
    frame_top = x - (x//9*9)%27 - x%3
    for i in range(0,3,1):
        for j in range(0,3,1):
            if(board[frame_top+9*i+j]==n):
                return False
    return True

# row_ok，column_ok，frame_ok を呼び出し，全ての重複チェックを実行する関数
def check_ok(n,x):
    if row_ok(n,x)==True and column_ok(n,x)==True and frame_ok(n,x)==True :
        return True
    else:
        return False

# パズルを解くための手順を実行する関数
def solve(x):
    if (x > MAX_BOARD-1):
        print_board(board)
        sys.exit()
    else:
        if(board[x] != 0):
            solve(x+1)
        else:
            for n in range(1,10,1):
                if(check_ok(n,x)==True):
                    board[x] = n
                    solve(x+1)
                    board[x] = 0

print_board(board)

print('start solve !')

solve(0)

令和3年度 秋期 午後 問3 一筆書き

グラフは，有限個の点の集合と，その中の 2 点を結ぶ辺の集合から成る数理モデルである。グラフの点と点の間をつなぐ辺のことを経路という。本問では，任意の 2 点間で，辺をたどることで互いに行き来することができる経路が存在する（以下，強連結という）有向グラフを扱う。強連結な有向グラフの例を図 1 に示す。辺は始点と終点の組で定義する。各辺には 1 から始まる番号が付けられている。

一筆書き

本問では，グラフの全ての辺を 1 回だけ通り，出発点から出て出発点に戻る閉じた経路をもつグラフを，一筆書きができるグラフとする。

一筆書きの経路の求め方

一筆書きの経路を求めるためには，出発点から辺の向きに従って辺を順番にたどり，出発点に戻る経路を見つける探索を行う。たどった経路（以下，探索済の経路という）については，グラフ全体が通過していない辺（以下，未探索の辺という）がない場合は，この経路が一筆書きの経路となる。未探索の辺が残っている場合は，探索済の経路を，未探索の辺が接続する点まで遡り，その点を出発点として，同じ点に戻る経路を見つけて，遡る前までの経路に連結することを繰り返す。

各点を始点とする辺を接続辺という。グラフの各点に対して接続辺の集合が決まり，辺の番号が一番小さい接続辺を最初の接続辺という。同じ始点をもつ接続辺の集合で，辺の番号を小さいものから順番に並べたときに，辺の番号が次に大きい接続辺を次の接続辺ということにする。

図 1 のグラフの各点の接続辺の集合を表 1 に示す。図 1 において，点 b の最初の接続辺は辺 2 である。辺 2 の次の接続辺は辺 5 となる。辺 5 の次の接続辺はない。

一筆書きの経路の探索において，一つの点に複数の辺がある場合には，最初の接続辺から順にたどることにする。

図 1 のグラフで点 a を出発とした一筆書きの経路の求め方を図 2 に示す。

経路を構成する辺とその順番が，これ以上変わらない場合，確定済の経路という。

一筆書きの経路を求める手順

点 a から探索する場合は，点 a の最初の接続辺である辺 1 から始め，辺 1 の終点 b の最初の接続辺である辺 2 をたどり，同様に辺 3，辺 4 をたどる。辺 4 の終点 a からたどれる未探索の辺は存在しないので，これ以上探索が進められない（図 2 [1]）。

しかし，未探索の辺 5，辺 6，辺 7，辺 8 が残っているので，未探索の辺が接続する点まで遡る。

終点 a から辺 4 を遡ると，辺 4 の始点 d で未探索の辺 7 が接続している。遡った経路は途中で未探索の辺が存在しないので，これ以上，辺の順番が変わらず，辺 4 は，一筆書きの経路の一部として確定済の経路となる（図 2 [2]）。

点 d から同様に辺 7 → 辺 8 → 辺5 → 辺 6 と探索できるので，辺 3 までの経路と連結した新しい探索済の経路ができる（図 2 [3]）。

辺 6 の終点からは，辺 6 → 辺 5 → 辺 8 → 辺 7 → 辺 3 → 辺 2 → 辺 1 と出発点の点 a まで遡り，これ以上，未探索の辺がないことが分かるので，全ての辺が確定済の経路になる（図 2 [4]）。

一筆書きの経路は，次の 1. ～ 4. の手順で求められる。

1. 一筆書きの経路の出発点を決める。
2. 出発点から，未探索の辺が存在する限り，その辺をたどり，たどった経路を探索済の経路に追加する。
3. 探索済の経路を未探索の辺が接続する点又は一筆書きの経路の出発点まで遡る。遡った経路は，探索済の経路から確定済の経路にする。未探索の辺が接続する点がある場合は，それを新たな出発点として，2. に戻って新たな経路を見つける。
4. 全ての辺が確定済の経路になった時点で探索が完了して，その確定済の経路が一筆書きの経路になる。

一筆書きの経路を求めるプログラム

一筆書きの経路を求める関数 directedE のプログラムを作成した。

実装に当たって，各点を点 n（n は 1 ～ N）と記す。例えば，図 1 のグラフでは，点 a は点 1，点 b は点 2 と記す。

グラフの探索のために，あらかじめ，グラフの点に対する最初の接続辺の配列 edgefirst 及び接続辺に対する次の接続辺の配列 edgenext を用意しておく。edgenext において，次の接続辺がない場合は，要素に 0 を格納する。

図 1 のグラフの場合の配列 edgefirst，edgenext を図 3 に示す。

edgefirst によって点 2 の最初の接続辺が辺 2 であることが分かり，点 2 から最初にたどる接続辺は辺 2 となる。edgenext によって，辺 2 の次の接続辺が 5 であることが分かるので，点 2 から次にたどる接続辺は辺 5 となる。辺 5 の次の接続点はないので，点 2 からたどる接続辺はこれ以上ないことが分かる。

プログラム中で使用する定数と配列を表 2 に，作成した関数 directedE のプログラムを図 4 に示す。

全ての配列の添字は 1 から始まる。

function directedE()
	for (i を 1 から N まで 1 ずつ増やす)		// 各点での未探索の辺の番号を初期化
		current[i] ← edgefirst[i]
	endfor
	top  ← 1			//探索済の経路の辺の格納位置を初期化
	last ← M			//確定済の経路の辺の格納位置を初期化
	x    ← 1			//出発点は 1
	while ( ① last が 1 以上)
		if (current[x] が ア でない)
			temp ← current[x]	// 点 x からたどる接続辺は temp
			searched[top] ← temp	//接続辺 temp を探索済の経路に登録
			current[x] ← イ	//点 x から次にたどる未探索の辺を格納
			x ← end[temp]	// 接続辺 temp の終点を点 x にする
			top ← top+1
		else
			top ← ウ				//探索済の辺を遡る
			temp ← searched[top] // 遡った辺は temp
			path[last] ← temp		// 辺 temp を確定済にする
			x ← エ
			last ← last - 1
		endif
	endwhile
endfunction

設問 1

図 4 中の ア ～ エ に入れる適切な字句を答えよ。

• ア：0
• イ：edgenext[temp]
• ウ：top - 1
• エ：start[temp]

Octave での実装

一筆書きのプログラムを Octave で実装する。

N=6;
M=8;
start1=[1,2,3,4,2,5,4,6];
end1=[2,3,4,1,5,4,6,2];
edgefirst=[1,2,3,4,6,8];
edgenext=[0,5,0,7,0,0,0,0];

function directedE(N,M,start1,end1,edgefirst,edgenext)
  for i=1:1:N
    current(1,i)=edgefirst(1,i);
  endfor
  top=1;
  last=M;
  x=1;
  while last >= 1
    if current(1,x) ~=0
      temp=current(1,x);
      searched(1,top)=temp;
      current(x)=edgenext(1,temp);
      x=end1(temp);
      top=top+1;
    else
      top=top-1;
      temp=searched(1,top);
      path(last)=temp;
      x=start1(temp);
      last=last-1;
    endif
  endwhile
  path
endfunction

directedE(N,M,start1,end1,edgefirst,edgenext)

上記のプログラムを実行した結果は，以下のとおり。

令和3年度 春期 午後 問3 クラスタ分析に用いる k-means 法

k-means 法によるクラスタ分析は，異なる性質のものが混ざり合った母集団から互いに似た性質をもつものを集め，クラスタと呼ばれる互いに素な部分集合に分類する手法である。新聞記事のビッグデータ検索，店舗の品ぞろえの分類，教師なし機械学習などで利用されている。ここでは，2 次元データを扱うこととする。

分類方法と例

N 個の点を K 個（N 未満）のクラスタに分類する方法を 1. ～ 5． に示す。

1. N 個の点（1 から N までの番号が付いている）からランダムに K 個の点を選び（以下，初期設定という），それらの点をコアと呼ぶ。コアには 1 から K までのコア番号を付ける。なお，K 個のコアの座標は全て異なっていなければならない。
2. N 個の点と K 個のコアとの距離をそれぞれ計算し，各点から見て，距離が最も短いコア（複数存在する場合は，番号が最も小さいコア）を選ぶ。選ばれたコアのコア番号を，各点が所属する 1 回目のクラスタ番号（1 から K）とする。ここで，二つの点を XY 座標を用いて P=(a, b) と Q=(c, d) とした場合，P と Q の距離を $\sqrt{(a-c)^2 + (b-d)^2}$ で計算する。
3. K 個のクラスタのそれぞれについて，クラスタに含まれる全ての点を使って重心を求める。ここで，重心の X 座標をクラスタに含まれる点の X 座標の平均，Y 座標をクラスタに含まれる点の Y 座標の平均と定義する。ここで求めた重心の番号はクラスタの番号と同じとする。
4. N 個の点と各クラスタの重心 (G₁，…，G_K) との距離をそれぞれ計算し，各点から見て距離が最も短い重心（複数存在する場合は，番号が最も小さい重心）を選ぶ。選ばれた重心の番号を，各点が所属する次のクラスタ番号とする。
5. 重心の座標が変わらなくなるまで，3. と 4. を繰り返す。

次の座標で与えられる 7 個の点を，この分類方法に従い，二つのクラスタに分類する例を図 1 に示す。

クラスタ分析のプログラム

この手法のプログラム，プログラムで使う主な変数，関数及び配列を表 3 に示す。ここで，配列の添字は全て 1 から始まり，要素の初期値は全て 0 とする。

初期設定の改良

このアルゴリズムの最終結果は初期設定に依存し，そこでのコア間の距離が短いと適切な分類結果を得にくい。そこで，関数 initial において一つ目のコアはランダムに選び，それ以降はコアの距離が長くなる点が選ばれやすくなるアルゴリズムを検討した。検討したアルゴリズムでは，t 番目までのコアが決まった後，t+1 番目のコアを残った点から選ぶときに，それまでに決まったコアから離れた点を，より高い確率で選ぶようにする。具体的には，それまでに決まったコア（コア 1 ～ コア t）と，残った N-t 個の点から選んだ点 P_s との距離の和を T_s とする。N-t 個の全ての点について，T_s を求め，T_s が大きいほど高い確率で点 P_s が選ばれるようにする。このとき，点 P_s が t+1 番目のコアとして選ばれる確率として T_s/Sum を適用する。

令和2年度 午後 問3 誤差拡散法による減色処理

画像の情報量を落として画像ファイルのサイズを小さくしたり，モノクロの液晶画面に画像を表示させたりする際に，減色アルゴリズムを用いた画像変換を行うことがある。誤差拡散法は減色アルゴリズムの一つである。誤差拡散法を用いて，階調ありのモノクロ画像を，黒と白だけを使ったモノクロ 2 値の画像に画像変換した例を図 1 に示す。

階調ありのモノクロ画像の場合は，各ピクセルが色の濃淡をもつことができる。濃淡は輝度で表す。輝度が 0 のとき色は黒に，輝度が最大になると色は白になる。モノクロ 2 値の画像は，輝度が 0 か最大かの 2 値だけを使った画像である。

令和元年度 秋期 午後 問3 ニューラルネットワーク

AI 技術の進展によって，機械学習に利用されるニューラルネットワークは様々な分野で応用されるようになってきた。ニューラルネットワークが得意とする問題に分類問題がある。例えば，ニューラルネットワークによって手書きの数字を分類（認識）することができる。

分類問題には線形問題と非線形問題がある。図 1 に線形問題と非線形問題の例を示す。2 次元平面上に分布した白丸（〇）と黒丸（●）について，線形問題（図 1 の (a)）では 1 本の直線で分類できるが，非線形問題（図 1 の (b)）では 1 本の直線では分類できない。機械学習において分類問題を解く機構を分類器と呼ぶ。ニューラルネットワークを使うと，線形問題と非線形問題の両方を解く分類器を構成できる。

2 入力の論理演算を分類器によって解いた例を図 2 に示す。図 2 の論理演算の結果（丸数字）は，論理積（AND），論理和（OR）及び否定論理積（NAND）では 1 本の直線で分類できるが，排他的論理和（XOR）では 1 本の直線では分類できない。この性質から，前者は線形問題，後者は非線形問題と考えることができる。

注記　横軸（x1）及び横軸（x2）は論理演算の入力値（0 又は 1）。
丸数字は論理演算の出力値（演算結果）。破線は出力値を分類する境界。

平成31年度 春期 午後 問3 券売機の注文の状態を判定するプログラム

T 社では，U 社が経営する飲食店の店舗に設置する券売機のシステムを開発している。U 社が店舗で提供する商品には，丼物や定食などのメイン商品のほか，みそ汁やサラダなどのサイドメニューがある。

U 社では，特定の種類の商品を組み合わせたものをセットメニューとし，単品で注文した場合よりも安く提供している。

食券購入時の要件

食券購入時の主な要件を以下に示す。

食券購入時の主な要件

食券購入時の操作の流れ

• 利用者は，券売機の画面上に表示されるボタンを押すことで食券を購入する。
• 食券の購入は 1 名ずつ行う。
• 利用者は，購入したい全ての商品を指定後，合計金額を投入し，発見ボタンを押す。

メニューの構成

• 商品はメイン商品，サイドメニュー１，サイドメニュー２，オプションに分類される。商品には，サイズやドレッシングの種類など，オプションの指定が必要なものがある。
• メイン商品は必ず 1 品注文する必要がある。サイドメニューの注文は任意である。
• メイン商品 1 品に対し，サイドメニューは複数注文することができる。
• 券売機の画面は，メイン商品の選択画面，サイドメニュー１の選択画面，サイドメニュー２の選択画面の順に遷移する。サイドメニュー１を注文しない場合は，サイドメニュー１の選択画面での注文をスキップできる。オプションは，オプションの指定が必須の商品の選択画面で指定できる。

発券ボタンの制御

• 発券ボタンはメイン商品の注文後，任意のタイミングで押すことができる。ただし，オプションの指定が必須な商品でオプションが未指定の場合は，押すことができない。

セットメニューの値引きのルール

• セットメニューに適用できるメイン商品，サイドメニュー１，サイドメニュー２を，それぞれ 1 品以上選んだ場合，50 円値引きする。値引きは食券購入ごとに 1 回だけ適用される。

平成30年度 秋期 午後 問3 ウェーブレット木

ウェーブレット木は，文字列内の文字の出現頻度を集計する場合などに用いられる 2 分木である。ウェーブレット木は，文字列内に含まれる文字を符号化して，それを基に構築される。特に計算に必要な作業領域を小さくできるので，文字列が長大な場合に効果的である。

例えば，DNA は A（アデニン），C（シトシン），G（グアニン），T（チミン）の 4 種類の文字の配列で表すことができ，その配列は長大になることが多いので，ウェーブレット木は DNA の塩基配列（以下，DNA 配列という）の構造解析に適している。

ウェーブレット木において，文字の出現回数を数える操作と文字の出現位置を返す操作を組み合わせることによって，文字列の様々な操作を実現することができる。本問では，文字の出現回数を数える操作を扱う。

平成30年度 春期 午後 問3 ナイトの巡歴問題

ナイトの巡歴問題とは，M 列 N 列（以下，M × N マスという）の盤面上でチェスの駒の一種であるナイトを移動させ，全てのマスを 1 回ずつ通過する経路を発見する問題である。

ナイト（K）が 1 回で移動できるマス（以下，移動先という）の位置を図 1 に示す。また，4 × 3 マスの場合のナイトの巡歴問題の解の一つを図 2 に示す。図 2 に示す，ナイトの移動する順序を表す数を，移動順序という。

なお，行番号は上から下，列番号は左から右に増加する。

注記　マス内の "K" はナイトの位置を表す。
① ～ ⑧ はナイトの移動先を表す。

注記　マス内の数はナイトが移動する順序を表す。

M × N マスのナイトの巡歴問題について，行 1 列 1 のマスを起点とする全ての経路を求める処理の概要を示す。この処理は，再起による深さ優先探索として実現されている。

平成29年度 秋期 午後 問3 ナップザック問題

ナップザック問題

幾つかの種類の品物があり，それぞれの容積と価値が与えられているとき，選んだ品物の容積の合計が定められた値以下であるという条件（容量制限）を満たし，かつ，価値の合計（以下，価値合計という）が最大になるような品物の組合せを求める問題をナップザック問題（Knapsack Problem）という。

この問題では，一つの品物を選ぶ個数には制限がないものとする。

例えば，容積，価値を表h29a-1 に示した 2 種類の品物 A，B があり，容量制限が 5 である問題を考える。この場合，品物 A を 1 個，品物 B を 2 個選ぶと，容積の合計は 5，価値の合計は 14 となり，選んだ品物の価値合計が最大となる。

動的計画法によるナップザック問題の解法

品物の容積や価値を正の整数に限定したナップザック問題に対して，動的計画法（Dynamic Programming）による解法が知られている。この問題に対する動的計画法は，元の容量制限以下の全ての値を容量制限としたときの，品物の種類を限定した問題（以下，小問題という）をあらかじめ解いておき，それらの解を用いることによって，元の問題の解を得る方法である。表h29a-2 に示すような，選んだ品物の最大の価値合計を求める表に対して順に数値を埋めて考えると，この解法の手順は理解しやすい。

表h29a-2 において，例えば，表h29a-1 に示す品物 A，B を選べる場合の容量制限 3 までの小問題が解けているとする。この状態で，容量制限が 4 で品物 A，B を選べる場合の解法は，次の考え方で求めることができる。

• 容量制限が 4 で品物 A だけを選べる小問題の解は，表h29a-2 から 8 であることがわかる（下線 ① 部分）。
• 品物 A，B を選べる場合，品物 B の容積が 2 であるので，4 から 2 を減じた容量制限 2 で品物 A，B を選べる小問題の価値合計 6（下線 ② 部分）に，品物 B の価値 6 を加えた 12 の価値合計を得られることが分かる。
• 8 と 12 を比較し，大きい方の 12 を，容量制限 4 の場合の価値合計として表h29a-2 に記入する。これは，最後に品物 B を選んだことを意味する。

表h29a-2 の空白の部分をこの手順に従って順に埋めていくと，容量制限が 5 のときの価値合計は 14 であることが分かる。

容量制限 4 の場合に最後に品物 B を選んだように，各容量制限の小問題を解いたときに最後に選んだ品物を表h29a-3 に示す。

容量制限 5 では，最後に品物 B を選んだことが分かる。次に，品物 B の容積を引いた容量制限 3 では，最後に品物 B を選んでいる。これを続けていくと，価値合計 14 を実現する品物の組合せは，品物 A が 1 個，品物 B が 2 個であることがわかる。

表 1 の問題に対して，新たに，容積が 3 で価値が 9 である品物 C が追加されたときの問題を解くには，表 2 に品物 A，B，C を選べる場合の行を追加した表 4 を順に埋めていけばよい。

ナップザック問題に対する動的計画法によるプログラム

ナップザック問題に対する動的計画法によるプログラムを以下に示す。なお，全ての配列の添字は 1 から始まる。

プログラム

V=5;
N=3;
size=[1,2,3];
value=[2,6,9];

# 初期化
maxvalue=zeros(1,V+1);
choice(1,1:V+1)=-1;

# 動的計画法メイン。
for s=1:N
	for t=size(s):V
		temp=maxvalue(t-size(s)+1)+value(s);
		if temp > maxvalue(t+1)
			maxvalue(t+1)=temp;
			choice(t)=s;
		endif
	endfor
endfor

# 選んだ品物を出力
choice(1:V)

# 価値合計を出力する
maxvalue(V+1)
			

出力結果

上記のプログラムを実行したとき，選んだ品物，価値の合計は，以下のように出力される。

計算量に関する検討

動的計画法を用いてナップザック問題を解く場合の計算量のオーダは，品物の種類の数を N，ナップザックの容量制限を V とすると，O(NV) である。

平成29年度 春期 午後 問3 探索アルゴリズム

1 個ずつの重さが異なる商品を組み合わせ，合計の重さが指定された値になるようにしたい。

この問題を次のように簡略化し，解法を考える。

例えば，指定された n 個の数が (10, 34, 55, 77)，目標 X が 100 とすると，選択した数の組合せは (10, 34, 55)，選択した数の合計は（以下，合計という）は 99 となる。

この問題を解くためのアルゴリズムを考える。

指定された n 個の数の中から任意の個数を選択することから，各数に対して，選択する，選択しない，の二つのケースがある。数を一つずつ調べて，次の数がなくなるまで "選択する"，"選択しない" の分岐を繰り返すことで，任意の個数を選択する全ての組合せを網羅できる。この場合分けを図 1 に示す。

平成28年度 秋期 午後 問3 魔法陣

魔法陣とは，正方形のマス目（方陣）に数を配置し，縦・横・対角線のいずれにおいても，その並びの数の合計が同じになるものである。ここでは，N × N の方陣（N は 3 以上の自然数）に 1 から N² までの数を過不足なく配置したものとする。このとき，縦・横・対角線の N 個のマスの合計値は，いずれも (N³ + N) ÷ 2 となる。

平成28年度 春期 午後 問3 ライフゲーム

ライフゲームとは，数学者コンウェイが考案した，生命の誕生，生存，死滅などを再現したシミュレーションゲームである。マス目状の盤上の各升に生命が存在でき，そのマス自身及び隣接するマスの状態によって次世代の誕生，生存，死滅が決まる。その条件を表 1 に示す。

なお，隣接するマスには，斜め方向のマスも含む。また，生命が存在するマスを“生のマス”，生命が存在しないマスを“死のマス”と呼ぶ。

平成27年度 秋期 午後 問3 2 分探索木

2 分探索木とは，全てのノード N に対して，次の条件が成立している 2 分岐のことである。

• N の左部分木にある全てのノードのキー値は，N のキー値よりも小さい。
• N の右部分木にある全てのノードのキー値は，N のキー値よりも大きい。

ここで，ノードのキー値は自然数で重複しないものとする。2 分探索木の例を図 1 に示す。図中の数はキー値を表している。

2 分探索木を実現するために，ノードを表す構造体 Node を定義する。構造体 Node の構成要素を表 1 に示す。

構造体の実態を生成するためには，次のように書く。

生成した構造体への参照が戻り値となる。構造体の構成要素のうち，key は引数 key の値で初期化され，left と right は null で初期化される。

変数 p が参照するノードをノード p という。ノードを参照する変数からそのノードへの構成要素へのアクセスには “.” を用いる。例えば，ノード p のキー値には，p.key でアクセスできる。

なお，変数 p の値が null の場合，木は空である。

平成27年度 春期 午後 問3 データ圧縮の前処理として用いられる Block-sorting

Block-sorting は，文字列に対する可逆変換の一種である。変換後の文字列は，変換前の文字列と比較して同じ文字が多く続く傾向があるので，その後に行う圧縮処理において圧縮率を向上させることができる。

Block-sorting は，変換処理と復元処理の二つの処理で構成される。変換処理は，入力文字列を受け取って，変換結果の文字列と，入力文字列がソート後のブロックで何行目にあるか（以下，入力文字列の行番号という）を出力する。一方，復元処理は，変換結果の文字列と入力文字列の行番号を受け取って入力文字列を出力する。

データ圧縮における Block-sorting の使用方法を図 1 に示す。

平成26年度 秋期 午後 問3 マージソート

マージソートは，整列（ソート）したいデータ（要素）列を，細かく分割した後に，併合（マージ）を繰り返して全体を整列する方法である。

ここでは，それぞれの要素が 1 になるまでデータ列の分割を繰り返し，分割されたデータ列を昇順に並ぶように併合していくアルゴリズムを考える。例として，要素数が 8 の場合のアルゴリズムの流れを図 1 に示す。

再帰呼出しを使って記述したマージソートのアルゴリズムを以下に示す。

マージソートのアルゴリズム

1. 与えられたデータ列の要素数が 1 以下であれば，整列済みのデータ列とし，呼出し元に処理を戻す。要素数が 2 以上であれば，2 に続く。
2. データ列を，要素数がほぼ同じになるよう前半と後半のデータ列に分割する。
3. 前半と後半のデータ列に対し，それぞれマージソートのアルゴリズムを再帰的に呼び出す。
4. 前半と後半の二つのマージソート済みのデータ列を，要素が昇順に並ぶよう一つのデータ列に併合する。

平成26年度 春期 午後 問3 循環小数の循環節を検出するアルゴリズム

与えられた自然数 $n$ について，$1/n$ の小数表現を考える。$1/n$ は，割り切れない場合，必ず循環小数となる。本問において，循環小数は，図 1 に示すように，繰り返し現れる数の並びである循環節の先頭から末尾までを括弧でくくる表記法で表す。

1 を $n$ で割る割り算で現れる余りは，1 から $n-1$ までの数に限られる。循環小数となる場合は，割り算を小数第 1 位から行っていくと，どこかでそれまでに現れた余りと同じ値の余りが現れる。以降の割り算で得られる小数は，同じ数の並びが繰り返されることとなり，その数の並びが循環節となる。循環節の桁数は最大 $n-1$ である。

1/56 の計算で商を 1 桁ずつ求めていくと，余りの遷移は図 2 のようになる。ここでは，前のマスの中の値を 10 倍してから 56 で割った余りが次のマスの中の値となる。余りとして 48 が再度現れることから，1/56 では小数第 4 位から第 9 位までが循環節となることが分かる。

平成25年度 秋期 午後 問2 リストによるメモリ管理

与えられたメモリ空間（以下，ヒープ領域という）の中に，可変長のメモリブロックを動的に割り当てるためのデータ構造及びアルゴリズムを考える。

ヒープ領域は，一つ以上の連続したメモリブロックで構成する。メモリブロックは，固定長のヘッダ部分と可変長のデータ部分で構成される。ヘッダ部分は構造体で，prev，next，status 及び size のメンバによって構成される。メモリブロックの構造を図 1 に，ヘッダ部分のメンバの意味を表 1 にそれぞれ示す。メモリブロックを指すポインタ変数には，メモリブロックの先頭アドレスをセットする。あるメモリブロックを指すポインタ変数を q とするとき，そのメンバ prev の参照は，q->prev と表記する。また，ヘッダ部分のバイト数は，HSIZE とする。

ヘッダ部分と同じ構造体の変数 EDGE をヒープ領域の外に定義する。そのメンバ prev 及び next には，それぞれヒープ領域の最後尾及び先頭のメモリブロックの先頭アドレスをセットする。ヒープ領域の先頭のメモリブロックのメンバ prev と最後尾のメモリブロックのメンバ next には，ともに EDGE の先頭アドレスをセットする。これによって，EDGE を含むメモリブロックが双方向の循環リストを構成する。EDGE にはデータ部分はなく，メンバ size には 0 が設定されている。データ構造の全体像を図 2 に示す。

平成25年度 春期 午後 問3 一般的な表記法の数式を逆ポーランド表記法に変換するアルゴリズム

逆ポーランド表記法とは，演算子を二つの演算対象の後ろに配置することによって，数式を表現する表記法である。例えば，一般的な表記法の数式 1 + 2 × 3 を，逆ポーランド表記法では 1 2 3 × + と表記する。

逆ポーランド表記法で表記した数式は，数値や演算子を左から順に処理すればよく，括弧を使う必要もないので，コンピュータが数式を取り扱うのに都合が良い。

一般的な表記法の数式から逆ポーランド表記法への変換は，スタックを用いることで容易に実現できる。

平成24年度 秋期 午後 問2　N クイーン問題

N クイーン問題とは，N × N マスの盤上で互いの利き筋に当たらないような N 個のクイーンの配置を見つける問題である。クイーンは，縦・横・斜めのいずれか一方向にどこまでも移動することができ，一度に移動できる範囲をクイーンの利き筋という。8 × 8 マスの盤上の行 5 列 6 に配置したクイーンの利き筋を，図 1 に示す。また，8 × 8 マスの場合の N クイーン問題の解の一つを図 2 に示す。

なお，N クイーン問題の解は存在しないこともあるし，複数存在することもある。

N クイーン問題に対し，空の盤上にクイーンを配置し，その配置したクイーンの利き筋に当たらない位置を探索しながら，行順にクイーンを配置するという，次のような解放を考えた。

平成24年度 春期 午後 問2　文字列を圧縮するアルゴリズム

データを圧縮するアルゴリズムの一つにランレングス法がある。ランレングス法とは，同じデータが連続して現れる箇所を，そのデータと連続している回数との組に変換する方法である。文字 "a" ～ "z" だけから成る文字列を圧縮する方法として，圧縮の表現形式の違う二つのプログラムを比較検討する。

圧縮前と圧縮後のデータを管理する方法として配列を用いる。配列の各要素には，文字データの場合は 8 ビット表現の文字コードが，数値データの場合は 0 ～ 255 の整数が格納される。圧縮前の配列を in，圧縮後の配列を out とする。配列 in の大きさは文字列の長さと等しく，2 以上，255 以下である。配列 out には圧縮後のデータを格納する十分な領域が確保されている。配列の添字は 0 から始まる。

圧縮方法その 1

圧縮の表現方法として，［圧縮対象文字］［連続回数］を用いる方法の処理手順を次の 1. ～ 5. に，そのプログラムを図 1 に示す。例えば，文字列 "abbcccddddeeeee" を圧縮すると，a1b2c3d4e5 となる。ここで，a ～ z は文字データを表し，数字は対応する数値データを表す。

1. 配列 in の初めの 1 文字を変数 prev に取り出す。連続回数を 1 にする。
2. 配列 in から次の 1 文字を取り出し，変数 prev と比較する。配列 in から取り出す文字がない場合，処理手順 5. へ進む。
3. 比較した二つの文字が等しい場合，連続回数に 1 を加える。等しくない場合，変数 prev と連続回数を配列 out に追加し，2. で取り出した文字を変数 prev にコピーして，連続回数を 1 に戻す。
4. 処理手順 2. に戻る。
5. 変数 prev と連続回数を配列 out に追加する。

図 1 中の関数 encode1 はプログラムのメイン処理であり，配列 out に追加されたデータの大きさを返す。

function encode1 (in, out)
  prev ← in[0]
	runLength ← 1
	k ← 0
	for (i を 1 から（配列 in の大きさ -1）まで 1 ずつ増やす)
	  if ( ア )
		  runLength ← runLength + 1
		else
		  out[k] ← prev
			out[k+1] ← runLength
			k ←  イ 
			prev ← in[i]
			runLength ← 1
		endif
	endfor
	out[k] ← prev
	out[k+1] ← runLength
	k ←  イ 
	return k
endfunction

平成23年度 秋期 午後 問2　ハッシュ法と排他制御

T 社は，ソフトウェア開発を行う会社である。現在，LAN 環境で利用するクライアントサーバシステム（以下，本システムという）を開発中である。

本システムは，クライアント PC 上で画面にデータを表示する画面プログラムと，画面プログラムが使用するデータをサーバ上で管理するデータ管理プログラムから構成される。

データ構造

配列 array は，クライアント PC で使用するデータ info を格納する配列であり，配列の添え字は 1 ～ N である。info のデータ型は構造体 INFO である。表 1 に構造体 INFO のメンバを示す。構造体メンバの初期値は，全て 0（未使用を意味する）を設定する。

ハッシュ関数 Hash(key) は，key を基にデータの格納位置を算出して，戻り値として戻す。格納位置は 1 ～ N の整数となる。関数 Hash(key) が，異なる key から同じ格納位置を算出することを，シノニムの発生という。この影響で，格納位置の配列要素が既に使用されていて，データを格納できないことがある。この場合は，配列 array を格納位置の次から順次検索し，最初に見つかった未使用の配列要素にデータを格納する。配列 array の最後に到達しても未使用の配列要素がない場合には，配列 array の先頭に戻り，未使用の配列要素の検索を続ける。

データ管理プログラム

図 1 のデータ格納関数 Set()，図 2 のデータ取得関数 Get()，図 3 のデータ削除関数 Delete() をデータ管理プログラムと呼ぶ。

関数 Get() は，データ取得に成功すると，取得したデータを引数 info に格納する。関数 Set() と関数 Get() は戻り値として格納位置を戻す。処理結果が正しくない場合は，戻り値として 0 を戻す。

平成23年度 春期 午後 問2　集計表を HTML に変換して出力するプログラム

図 1 に示すような，都道府県及び支店ごとに整理された売上高一覧の CSV ファイルを入力し，表 1 のような都道府県ごとの売上高の集計表を HTML で出力するプログラムがある。ここで，一つの都道府県における支店数は 500 未満とする。

東京都,千代田店,23500
東京都,中央店,33500
東京都,港店,18500
埼玉県,川口店,28000
埼玉県,さいたま店,9500

使用する HTML について

使用する HTML タグ及びその属性を表 2 に示す。

表 1 を HTML で記述した例を図 2 に示す。

プログラムの概要

プログラムの処理手順の概要を次の 1. ～ 5. に，使用する構造体，配列，変数及び関数の一部を表 3 に，構造体及び配列の使い方を表 4 に示す。

1. CSV ファイルを配列 CSVArray に読み込む
2. <table> 開始タグ及び集計表のヘッダ行を出力する。
3. 配列 CSVArray の先頭要素から末尾まで 1 件ずつ読み，配列 shitenArray に支店名と売上高を追加していく。途中で都道府県が変わった場合，支店名と売上高を追加する前に，① 都道府県，支店名，売上高，小計の HTML タグ及びデータを出力し，配列 shitenArray の全要素を削除する。
4. ② 都道府県，支店名，売上高，小計の HTML タグ及びデータを出力する。
5. 合計及び <table> の終了タグを出力する。

平成22年度 秋期 午後 問2　構文解析

宣言部と実行部からなる図 1 のような記述をするプログラム言語がある。その構文規則を，括弧記号で表記を拡張した BNF によって，図 2 のように定義した。

図 2 において，引用符「‘」と「’」で囲まれた記号や文字列，＜数＞，及び＜識別子＞は終端記号を表す。そのほかの「＜」と「＞」で囲まれた名前は非終端記号を表す。＜数＞は 1 文字以上の数字の列を表し，＜識別子＞は英字で始まる 1 文字以上の英字又は数字からなる文字列を表す。

また，A | B は A と B のいずれかを選択することを表し，{A} は A を 0 回以上繰り返すことを表す。

＜プログラム＞::=＜宣言部＞＜実行部＞
＜宣言部＞::=＜宣言部記述＞｛＜ア＞｝
＜実行部＞::=＜文＞｛＜文＞｝
＜宣言部記述＞::=＜宣言記述子＞＜イ＞‘;’
＜宣言記述子＞::=‘short’ | ‘long’
＜文＞::=＜識別子＞ ‘=’ ＜式＞ ‘;’
＜式＞::=＜項＞｛‘+’ ＜項＞ | ‘-’ ＜項＞｝
＜項＞::=＜ウ＞ ｛‘*’ ＜因子＞ ｜ ‘/’ ＜因子＞｝
＜因子＞::=＜数＞ | ＜識別子＞

例えば，図 1 の最初の行 “short aa ;” は，図 2 の＜宣言部記述＞の定義に従っていて，＜宣言記述子＞と ‘short’，＜イ＞ と ‘a’，更に ‘;’ 同士がそれぞれ対応していることが分かる。

平成22年度 春期 午後 問2　アプリケーションで使用するデータ構造とアルゴリズム

PC のデスクトップ上の好きな位置に付箋を配置できるアプリケーションの実行イメージを図 1 に，付箋 1 枚のデータイメージを図 2 に示す。

複数の付箋データを管理する方法として，配列と双方向リスト（以下，リストという）のいずれがよいか検討することにした。そこで，図 1 の付箋 ③ のようにほかの付箋の背後にある付箋を一番手前に移動するアルゴリズムを，配列とリストそれぞれで実装して比較検討する。使用する構造体，配列，定数，変数及び関数を表に示す。また，図 1 の付箋 ① ～ ⑤ を順番に，配列及びリストにそれぞれ格納した際のイメージを図 3，4 に示す。

なお，配列及びリストの末尾に近い付箋データほど，デスクトップ上の手前に表示される。

平成21年度 秋期 午後 問2　文字列照合処理

ある文字列（テキスト）中で特定の文字列（パターン）が最初に一致する位置を求めることを文字列照合という。そのための方法として，次の二つを考える。ここで，テキストとパターンの長さは，どちらも 1 文字以上とする。

方法１　単純な照合方法

テキストを先頭から 1 文字ずつパターンと比較して，不一致の文字が現われたら，比較するテキストの位置（比較位置）を 1 文字分進める。この方法による処理例を図 1 に示す。

この手順を基に，テキストとパターンを与えると，最初に一致した文字位置を返すアルゴリズムを作成した。このアルゴリズムを図 2 に示す。

なお，テキストは配列 T，パターンは配列 P に格納されており，T[n] 及び P[n] はそれぞれの n 番目の文字を，T.length 及び P.length はそれぞれの長さを示す。

function search1(T,P)
	for i を 1 から ア まで 1 ずつ増やす
		for j を 1 から イ まで 1 ずつ増やす
			if T[i+j-1] と P[j] が等しい ⇐ α
				if j と イ が等しい
					return i
				endif
			else
				break
			endif
		endfor
	endfor
	return -1  // パターンが見つからない場合は -1 を返す
end function

方法２　効率的な照合方法

方法 1 では，パターンとテキストの文字が不一致となった場合，比較位置を 1 文字分進めている。ここでは，比較位置をなるべく多くの文字数文進めることで，照合における比較回数を減らすことを考える。

パターンの末尾に対応する位置にあるテキストの文字（判定文字）に着目すると，次のように比較位置を進める文字数（スキップ数）が決定できる。

1. 判定文字がパターンに含まれていない場合は，判定文字とパターン内の文字の比較は常に不一致となるので，パターンの文字数分だけ比較位置を進める。また，判定文字がパターンの末尾だけに含まれている場合も，同様にパターンの文字数分だけ比較位置を進める。
2. 判定文字がパターンの末尾以外に含まれている場合は，判定文字と一致するパターン内の文字が，テキストの判定文字に対応する位置に来るように比較位置を進める。ただし，パターン内に判定文字と一致する文字が複数ある場合は，パターンの末尾から最も近く（ただし，末尾を除く）にある判定文字と一致するパターン内の文字が，判定文字に対応する位置に来るように比較位置を進める。

この方法の処理例を図 3 に示す。

パターンが与えられると，判定文字に対応するスキップ数を一意に決定することができる。例えば，パターン HIJ に対して判定文字とスキップ数の対応表を作成すると表 1 のようになる。

この考え方を基に作成したアルゴリズムを図 4 に示す。

なお，このテキストは配列 T，パターンは配列 P，スキップ数を決める表の判定文字は配列 C，スキップ数は配列 D に格納されており，T[n]，P[n]，C[n]，D[n] はそれぞれの n 番目の文字又は数値を，T.length 及び P.length はテキストとパターンの長さを示す。

このアルゴリズムは，三つの主要部分から成っている。一つ目は，与えられたパターンについて判定文字とスキップ数の対応表を作成する処理である。ここでは，配列 C に格納される空白文字は表 1 の “その他の文字” 及びパターンの末尾の文字 “J” を表現するために使用している。テキストとパターンは空白文字を含まないものとする。二つ目は，文字を比較する処理である。ここでは，現在の比較位置に対応したテキストとパターンを方法 1 と同様に 1 文字ずつ比較して，パターンに含まれる文字と対応するテキストの文字がすべて一致するか，不一致となる文字が見つかるまで繰り返す。三つ目は，判定文字とスキップ数の対応表を引いてスキップ数を決定する処理である。

平成21年度 春期 午後 問2　チェイン法（探索アルゴリズムであるハッシュ法の一つ）

配列に対して，データを格納すべき位置（配列の添字）をデータのキーの値を引数とする関数（ハッシュ関数）を求めることによって，探索だけではなく追加や削除も効率よく行うのがハッシュ法である。

通常，キーのとり得る値の数に比べて，配列の添字として使える値の範囲は狭いので，衝突（collision）と呼ばれる現象が起こり得る。衝突が発生した場合の対処方法の一つとして，同一のハッシュ値をもつデータを線形リストによって管理するチェイン法（連鎖法ともいう）がある。

8 個のデータを格納したときの例を図 1 に示す。

このとき，キー値は正の整数，配列の添字は 0 ～ 6 の整数，ハッシュ関数は引数を 7 で割った剰余を求める関数とする。

このチェイン法を実現するために，表に示す構造体，配列及び関数を使用する。

構造体を参照する変数からその構造体の構成要素へのアクセスには “.” を用いる。例えば，図 1 のキー値 25 のデータは table[4].data でアクセスできる。また，構造体の実体を生成するには，次のように書き，生成された構造体への参照が値になる。

探索関数 search

探索のアルゴリズムを実装した関数 search の処理手順を次の 1. ～ 3. に，そのプログラムを図 2 に示す。

1. 探索したいデータのキー値からハッシュ値を求める。
2. ハッシュ表中のハッシュ値を添字とする要素が参照する線形リストに着目する。
3. 線形リストのノードに先頭から順にアクセスする。キー値と同じ値が見つかれば，そのノードに格納されたデータを返す。末尾まで探して見つからなければ null を返す。

function search(key)
	hash ← hashValue(key);	// 探索するデータのハッシュ値
	node ← table[hash];		// 着目する線形リストへの参照
	while(node が null でない)
		if (ア)
			return node.date;				// 探索成功
		endif
		イ;	// 後続ノードに着目
	endwhile
	return ウ;	// 探索失敗
endfunction

追加関数 addNode

データの追加手続を実装した関数 addNode の処理手順を次の 1. ～ 3. に，プログラムを図 3 に示す。図 3 中の ア，イ には，図 2 中の ア，イ と同一のものが入る。

1. 追加したいデータのキー値からハッシュ値を求める。
2. ハッシュ表中のハッシュ値を添字とする要素が参照する線形リストに着目する。
3. 線形リストのノードに先頭から順にアクセスする。キー値と同じ値が見つかれば，キー値は登録済みであり追加失敗として false を返す。末尾まで探して見つからなければ，リストの先頭にノードを追加して true を返す。

function addNode(key,date)
	hash ← hashValue(key);	// 追加するデータのハッシュ値
	node ← table[hash];		// 着目する線形リストへの参照
	while(node が null でない)
		if (ア)	// このキー値は登録済み
			return false;
		endif
		イ;	// 後続ノードに着目
	endwhile
	tempNode ← new Node(エ);	// ノードを生成
	オ ← tempNode;	// ノードを追加
	return true;
endfunction

チェイン法の計算量

チェイン法の計算量を考える。

計算量が最悪になるのは，カ場合である。しかし，ハッシュ関数の作り方が悪くなければ，このようなことになる確率は小さく，実際上は無視できる。

チェイン法では，データの個数を n とし，表の大きさ（配列の長さ）を m とすると，線形リスト上の探索の際にアクセスするノードの数は，線形リストの長さの平均 n/m に比例する。m の選び方は任意なので，n に対して十分に大きくとっておけば，計算量が キ となる。この場合の計算量は 2 分探索木による $O(\log{n})$ より小さい。

本稿の参考文献

• 安藤正芳，武部健一，原田英生，清水美樹，「日経BPパソコンベストムック　難しそうなプログラミングをやさしく教えてくれる本」，日経BP社，2017年1月27日
• 廣野豪，「Python で学ぶアルゴリズムの教科書　一生モノの知識と技術を身につける」，インプレス，2021年3月21日
• 藤田聡，「グラフィック情報工学ライブラリ = GIE-4　アルゴリズムとデータ構造」，サイエンス社，2013年3月10日
• 松田晃一，「Python ライブラリの使い方　手軽に応用プログラミング」，カットシステム，2019年8月10日
• 松田七美男，「Octave の精義［第二版］　フリーの高機能数値計算ツールを使いこなす」，カットシステム，2019年10月25日

難しそうなプログラミングをやさしく教えてくれる本【電子書籍】 価格：2530円 (2021/9/11時点) 楽天で購入

世界でもっとも強力な9のアルゴリズム [ ジョン・マコーミック ] 価格：2200円（税込、送料無料) (2022/7/18時点) 楽天で購入

Octaveの精義第2版 フリーの高機能数値計算ツールを使いこなす [ 松田七美男 ] 価格：4620円（税込、送料無料) (2021/9/11時点) 楽天で購入