AP過去問令和7年度春期午後問3 プログラミング

AP過去問_令和7年度春期_午後_問4_システムアーキテクチャの同じ回の次の問題へ移動。

AP過去問_令和6年度秋期_午後_問3_プログラミングの前の回の同じカテゴリの問題へ移動。

令和7年度春期午後問3 プログラミング(AIプロンプト向け)

■スライドパズルを解くプログラムに関する次の記述を読んで、設問に答えよ。

　表1 のルールで定義されるスライドパズルについて考える。

<div><div class="table-container"><div class="table-header"><span class="table-title">表1 スライドパズルのルール</span><span class="table-unit"></span></div>

<tr>

</tr>

<tr>

<td align="center" style="border: 2px solid;">正方形の面に、1から順に1ずつ大きくなる数字の書かれた駒が配置されている。1か所だけ駒の置かれていない空白のマス(以下、空白マスという)がある。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">開始時点の盤面</td>

<td align="center" style="border: 2px solid;">開始時点では、駒と空白マスはランダムに配置されている。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">ゴールの盤面</td>

<td align="center" style="border: 2px solid;">盤面左上に数字が1の駒があり、右の駒の数字は1ずっ増えていき、その行の右端の駒に書かれた数字より1 大きい数字が、次の行の左端の駒の数字となる。盤面右下のマスが空白マスとなる。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">駒の上下左右いずれかに空白マスがある場合、駒を空白マスに移動することができる。駒が移動した場合、駒が置かれていたマスが空白マスになる。駒を空白マスに移動させて盤面を変化させ、ゴールの盤面と同じにすることを目指す。</td>

</tr>

</table>

</div>

　―辺が3マスのスライドパズルの例を図1 に示す。

　図1 一辺が3マスのスライドパズルの例ここから

開始時点の盤面

縦方向に1行目、2行目、3行目

開始時点の盤面

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

　ゴールの盤面

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

　図1 一辺が3マスのスライドパズルの例ここまで

　本問では、ー辺のマスの個数が任意のスライドパズルにおいて、ゴールの盤面になるまでの駒の移動回数が最小となる移動方法(以下、最小解という)をーつ求めるプログラムを作成する。

〔一辺がNマスのスライドパズルの最小解をを用いて求る方法〕　幅優先探索を行ったときの、スライドパズルの盤面の遷移を、グラフで表現する。開始時点の盤面をルートノード、ある時点の盤面をノード、駒の移動に伴う盤面の遷移をエッジで表現する。また、ゴールの盤面をゴールノードとして定義する。

　幅優先探索で最小解を求める方法を次のように考える。ここで、Nは2以上とする。

　探索対象のノードに対して、移動できる駒ごとにその駒を移動した後のノードを作成して、探索対象のノードの子ノードとし、探索対象のノードは探索済みとなる。このとき、子ノードが表す盤面が既に探索したノード(以下、探索済みノードという)と同じであれば、この子ノードは終端ノードとして、以降の探索は行わない。また、子ノードがゴールノードと同じであれば、最小解が見つかったと判断して探索を終了する。

〔Nが3の場合の例〕

　ー辺が3マスのスライドパズルの最小解を求める過程の例を図2に示す。

　図2 一辺が3マスのスライドパズルの最小解を求める過程の例ここから

ルートノード

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

1回目としてルートノードの子ノード①～③がある。

子ノード①

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

子ノード②

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

子ノード③

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

2回目として子ノード①の子ノード④、⑤がある。2回目として子ノード②の子ノード⑥、⑦、⑧、⑨がある。2回目として子ノード③の子ノード⑩、⑪がある。⑤、⑥、⑩は終端ノード

子ノード④

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

子ノード⑤

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

子ノード⑥

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

子ノード⑦

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

子ノード⑧

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

子ノード⑨

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

子ノード⑩

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

子ノード⑪

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

以降の子ノードは省略。

n回目として、いづれかの子ノードの子ノード⑫をゴールノードとして

子ノード⑫

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

　図2 一辺が3マスのスライドパズルの最小解を求める過程の例ここまで

(1) 1回目の駒の移動では、ルートノードを探索対象のノードとする。ここでは、移動できる駒が三つあるので、ルートノードから深さが1となる①～③の子ノードを作成し、ルートノードは探索済みノードとなる。ここで、①～③の子ノードに対して、ゴールノードの判定及び終端ノードの判定を行う。

(2) 次に、作成した子ノードで終端ノード以外のノードをそれぞれ探索対象のノードとし、駒の移動にあわせて子ノードを作成する。図2では、①～③のノードから④～⑪の子ノードを作成し、①～③は探索済みノードとなる。ここで、④～⑪の子ノードに対して、ゴールノードの判定及び終端ノードの判定を行う。図2では、盤面が探索済みノードと一致する⑤、⑥及び⑩は終端ノードとなり、以降の探索は行わない。

(3) 以降、(2)で作成したノードの子ノードの作成と、ゴールノードの判定及び終端ノードの判定を繰り返す。図2の⑫は、n回目の移動でゴールノードに至ったことを示している。なお、全てのリーフノードが終端ノードと判定された場合、ゴールの盤面に至る駒の移動方法がないことを意味しているので、その旨のメッセージを出力して探索を終了する。

　次に、配列を用いた盤面の表現方法を図3に示す。ここで、空白マスを表す値は最も大きい駒の数字である8に1を加えた9とする。なお、配列の要素番号は1から始まるものとする。

　図3 配列を用いた盤面の表現方法ここから

盤面を次の例に示すように配列を用いて表現する。

(1) 盤面の行ごとに並ぶ駒の数字を整数型の配列で表す。

横方向に1列目、2列目、3列目

配列表現サンプル

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

1行目を表す配列 {8, 6, 7}、2行目を表す配列 {2, 5, 4}、3行目を表す配列 {3, 9, 1}

(2) (1)で行ごとに定義した配列を整数型配列の配列(以下、盤面配列という)で表す。

{{8, 6, 7}, {2, 5, 4}, {3, 9, 1}}

(3) 1行目の3列目の駒の数字は、盤面配列名をboardとするとboard[1][3]として参照する。

　図3 配列を用いた盤面の表現方法ここまで

〔ー辺がNマスのスライドパズルの最小解を求めるプログラム〕

　一辺がNマスのスライドパズルにおいて、開始時点の盤面をランダムに作成し、最小解を求め、開始時点の盤面からの遷移及び駒の移動回数を出力するプログラムを作成する。開始時点の盤面からの遷移を保持する単方向連結リストの要素となるクラスBoardStateの説明を図4に、キューを実現するクラスQueueの説明を図5に、リストを実現するクラスListの説明を図6に、プログラムで使用する主な関数を表2に、最小解を求めるプログラムを図7に示す。

<div><div class="table-container"><div class="table-header"><span class="table-title">図4 クラスBoardStateの説明</span><span class="table-unit"></span></div>

<tr>

<td align="center" style="border: 2px solid; width: 5em;">メンバ変数</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">board</td>

<td align="center" style="border: 2px solid;">整数型配列の配列</td>

<td align="center" style="border: 2px solid;">盤面配列。初期状態は未定義</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">space</td>

<td align="center" style="border: 2px solid;">整数型の配列</td>

<td align="center" style="border: 2px solid;">空白のマスの場所を示す行番号と列番号の二つの要素から成る配列。初期状態は未定義。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">BoardState</td>

<td align="center" style="border: 2px solid;">駒が1回移動する前のBoardStateのインスタンスへの参照。開始時点の盤面からの遷移を出力する際に用いる。初期状態は未定義。</td>

</tr>

</table>

</div>

<div><div class="table-container"><div class="table-header"><span class="table-title">図4 クラスBoardStateの説明</span><span class="table-unit"></span></div>

<tr>

<td align="center" style="border: 2px solid; width: 5em;">コンストラクタ</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">BoardState()</td>

<td align="center" style="border: 2px solid;">インスタンスを初期化する。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">BoardState(BoardState: st)</td>

<td align="center" style="border: 2px solid;">インスタンスを初期化し、メンバ変数に次の処理を行う。</br> (1) メンバ変数boardに引数で渡されたBoardStateのインスタンスのboardの値を格納する。</br> (2) メンバ変数spaceに引数で渡されたBoardStateのインスタンスのspaceの値を格納する。</br> (3) メンバ変数prevに引数で渡されたBoardStateのインスタンスへの参照stを格納する。</br> </td>

</tr>

</table>

</div>

<div><div class="table-container"><div class="table-header"><span class="table-title">図5 クラスQueueの説明</span><span class="table-unit"></span></div>

<tr>

<td align="center" style="border: 2px solid; width: 5em;">コンストラクタ</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">Queue()</td>

<td align="center" style="border: 2px solid;">可変長のキューを生成する。</td>

</tr>

</table>

</div>

<div><div class="table-container"><div class="table-header"><span class="table-title">図5 クラスQueueの説明</span><span class="table-unit"></span></div>

<tr>

</tr>

<tr>

<td align="center" style="border: 2px solid;">add(BoardState: st)</td>

<td align="center" style="border: 2px solid;">キューにBoardStateのインスタンスへの参照stを追加する。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">isEmpty()</td>

<td align="center" style="border: 2px solid;">キューが空の場合はtrueを返し、空でない場合はfalseを返す。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">BoardState</td>

<td align="center" style="border: 2px solid;">先頭のBoardStateのインスタンスへの参照を取り出して返す。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">BoardState</td>

<td align="center" style="border: 2px solid;">先頭のBoardStateのインスタンスへの参照を返す。</td>

</tr>

</table>

</div>

<div><div class="table-container"><div class="table-header"><span class="table-title">図6 クラスQueueの説明</span><span class="table-unit"></span></div>

<tr>

<td align="center" style="border: 2px solid; width: 5em;">コンストラクタ</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">可変長のリストを生成する。</td>

</tr>

</table>

</div>

<div><div class="table-container"><div class="table-header"><span class="table-title">図6 クラスListの説明</span><span class="table-unit"></span></div>

<tr>

</tr>

<tr>

<td align="center" style="border: 2px solid;">add(整数型配列の配列: b)</td>

<td align="center" style="border: 2px solid;">リストに盤面配列bを追加する。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">isEmpty()</td>

<td align="center" style="border: 2px solid;">リストが空の場合はtrueを返し、空でない場合はfalseを返す。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">整数型配列の配列</td>

<td align="center" style="border: 2px solid;">リストの先頭に存在する盤面配列を返す。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">BoardState</td>

<td align="center" style="border: 2px solid;">先頭のBoardStateのインスタンスへの参照を返す。</td>

</tr>

</table>

</div>

<div><div class="table-container"><div class="table-header"><span class="table-title">表2 プログラムで使用する主な関数</span><span class="table-unit"></span></div>

<tr>

</tr>

<tr>

<td align="center" style="border: 2px solid;">createGoal(整数型: board_size)</td>

<td align="center" style="border: 2px solid;">整数型配列の配列</td>

<td align="center" style="border: 2px solid;">引数board_sizeの値を一辺のマス数としたスライドパズルのゴールの盤面を表す配列(以下、ゴールの盤面配列という)を作成して返す。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">createStart(整数型: board_size)</td>

<td align="center" style="border: 2px solid;">整数型配列の配列</td>

<td align="center" style="border: 2px solid;">引数board_sizeの値を一辺のマス数としたスライドパズルの開始時点の盤面配列をランダムに作成し、出力して返す。なお、ゴールの盤面配列と同じものが作成されることはない。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">getSpace(整数型配列の配列: b)</td>

<td align="center" style="border: 2px solid;">整数型の配列</td>

<td align="center" style="border: 2px solid;">盤面配列bを用いて、空白マスの場所と行番号と列番号から成る配列で返す。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">checkGoal(整数型配列の配列: b, 整数型配列の配列: g)</td>

<td align="center" style="border: 2px solid;">第一引数の盤面配列bと第二引数のゴールの盤面配列gを用いて両者が一致しているかどうかを判定して結果を返す。一致する場合はtrueを返し、一致しない場合はfalseを返す。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">printResult(BoardState: st)</td>

<td align="center" style="border: 2px solid;">引数として与えられたBoardStateのインスタンスへの参照stを用いて、開始時点の盤面からの遷移及び駒の移動回数を出力する。</td>

</tr>

<tr>

<td align="center" style="border: 2px solid;">checkSameBoard(整数型配列の配列: b, List: l)</td>

<td align="center" style="border: 2px solid;">引数で渡される探索済みの盤面配列のリストへの参照lを用いて、盤面配列bが探索済みの盤面配列のリストに存在するかどうかを判定して結果を返す。存在する場合はtrueを返し、存在しない場合はfalseを返す。</td>

</tr>

</table>

</div>

<style>

.line {

position: relative;

padding-left: 2.5em;

}

.line::before {

content: attr(data-line);

position: absolute;

left: 0;

width: 2em;

text-align: right;

user-select: none;

}

</style>

<span class="line" data-line="01:">〇solveNPuzzle(整数型: board_size)</span>

<span class="line" data-line="02:"> BoardState: start_state /* 開始時点の盤面を保持するBoardStateのインスタンスへの参照 */</span>

<span class="line" data-line="03:"> 整数型配列の配列: goal_board /* ゴールの盤面配列 */</span>

<span class="line" data-line="04:"> 整数型配列の配列: direction /* 駒の移動に伴う空白マスの移動方向を行番号の増減を1番目の要素、列番号の増減を2番目の要素で表現する配列 */</span>

<span class="line" data-line="05:"> Queue: explore_queue /* 探索対象の盤面を保持するキューのインスタンスへの参照 */</span>

<span class="line" data-line="06:"> List: check_list /* 探索済みの盤面配列を保持するリストのインスタンスへの参照 */</span>

<span class="line" data-line="07:"> BoardState: state /* 駒が移動する前の盤面を保持するBoardStateのインスタンスへの参照 */</span>

<span class="line" data-line="08:"> BoardState: new_state /* 駒が移動した後の盤面を保持するBoardStateのインスタンスへの参照 */</span>

<span class="line" data-line="09:"> 整数型: change_num /* 移動する駒の数字 */</span>

<span class="line" data-line="10:"> 整数型: i /* forループ内で使用するカウンタ変数 */</span>

<span class="line" data-line="11:"> start_state ← BoardState() </span>

<span class="line" data-line="12:"> goal_board ← createGoal(board_size) </span>

<span class="line" data-line="13:"> start_state.board ← createStart(board_size) </span>

<span class="line" data-line="14:"> start_state.space ← getSpace(start_state.board) </span>

<span class="line" data-line="15:"> direction ← {{1, 0}, {0, -1}, {-1, 0}, {0, 1}} </span>

<span class="line" data-line="16:"> explore_queue ← Queue() </span>

<span class="line" data-line="17:"> explore_queue.add(start_state) </span>

<span class="line" data-line="18:"> check_list ← List() </span>

<span class="line" data-line="19:"> check_list.add(start_state.board) </span>

<span class="line" data-line="20:"> while(【ア】がfalseと等しい) </span>

<span class="line" data-line="21:"> state ← explore_queue.【イ】</span>

<span class="line" data-line="22:"> for(iを1からdirectionの要素数まで1ずつ増やす) </span>

<span class="line" data-line="23:"> if((state.space[1] +【ウ】が1以上) かつ </span>

<span class="line" data-line="24:"> (state.space[1] +【ウ】が【エ】以下) かつ </span>

<span class="line" data-line="25:"> (state.space[2] +【オ】が1以上) かつ </span>

<span class="line" data-line="26:"> (state.space[2] +【オ】が【エ】以下)) </span>

<span class="line" data-line="27:"> new_state ← BoardState(state) </span>

<span class="line" data-line="28:"> new_state.space[1] ← state.space[1] + 【ウ】</span>

<span class="line" data-line="29:"> new_state.space[2] ← state.space[2] + 【オ】</span>

<span class="line" data-line="30:"> change_num ← new_state.board[new_state.space[1]][new_state.space[2]]</span>

<span class="line" data-line="31:"> new_state.board[new_state.space[1]][new_state.space[2]] ← board_size * board_size </span>

<span class="line" data-line="32:"> new_state.boart[state.space[1]][state.space[2]] ← change_num </span>

<span class="line" data-line="33:"> if(【カ】がtrueと等しい) </span>

<span class="line" data-line="34:"> printResult(new_state) </span>

<span class="line" data-line="35:"> return </span>

<span class="line" data-line="36:"> endif </span>

<span class="line" data-line="37:"> if(checkSameBoard(new_state.board, check_list)がfalseと等しい) </span>

<span class="line" data-line="38:"> explore_queue.【キ】 </span>

<span class="line" data-line="39:"> check_list.【ク】 </span>

<span class="line" data-line="40:"> endif </span>

<span class="line" data-line="41:"> endif </span>

<span class="line" data-line="42:"> endfor </span>

<span class="line" data-line="43:"> endwhile </span>

<span class="line" data-line="44:"> ゴールの盤面に至る駒の移動方法がない旨のメッセージを出力 </span>

<span class="line" data-line="45:"> return </span>

</code></pre>

令和7年度春期午後問3 プログラミング(問題原文)

■

回答・解説

AP過去問_令和7年度春期_午後_問2_経営戦略の同じ回の前の問題へ移動。

AP過去問_令和7年度春期_午後_問4_システムアーキテクチャの同じ回の次の問題へ移動。

AP過去問_令和6年度秋期_午後_問3_プログラミングの前の回の同じカテゴリの問題へ移動。

AP 過去問題午後に戻る。

令和7年度春期 午後 問3 プログラミング(AIプロンプト向け)

令和7年度春期 午後 問3 プログラミング(問題原文)

回答・解説

令和7年度春期午後問3 プログラミング(AIプロンプト向け)

令和7年度春期午後問3 プログラミング(問題原文)