応用情報技術者 2016年秋期午後問03

魔方陣に関する次の記述を読んで、設問1～3に答えよ。

　　魔方陣とは、正方形のマス目（方陣）に数を配置し、縦・横・対角線のいずれにおいても、その並びの数の合計が同じになるものである。ここでは、N×Nの方陣（Nは3以上の自然数）に1からN²までの数を過不足なく配置したものとする。このとき、縦・横・対角線のN個のマスの合計値は、いずれも(ア＋N)÷2となる。　Nが3の場合の魔方陣の一つを図1に示す。　応用情報技術者試験（平成28年度秋期午後問03 図01）

　Nが奇数の場合、魔方陣の一つを次の手順で作ることができる。N=3のときに、この手順によって1～6の数が配置される様子を図2に示す。　〔魔方陣の作り方〕　魔方陣の作り方は、次のとおりである。ここで(A)～(E)は図2中の該当箇所を示す。　(1) N×Nの全てのマスは何も入っていない空白の状態とする。　(2) 最下行の中央のマスを現在位置とし、現在位置に数1を配置する(A)。　(3) 現在位置の右下のマスが空白かどうか確認する。このとき、最下行の下は最上行(B)、最右列の右は最左列(C)とする。右下隅の右下は、左上隅(D)である。　(4) (3)で確認したマスが空白の場合は、そこを新しい現在位置とする。(3)で確認したマスが空白でない場合は、現在位置の上のマスを新しい現在位置とする(E)。この際、新しい現在位置が最上行よりも上になることはない。　(5) 数を一つ増やし、現在位置にその数を配置する。　(6) 全てのマスが埋まるまで、(3)～(5)を繰り返す。

〔魔方陣のプログラム〕　魔方陣の数の配置を記憶する、整数型の2次元配列 houjin を用意する。配列の添字は1から始まる。行 y 列 x のマスは、houjinyx で表現する。例えば、図1中の1が配置されているマスは、houjin[3][2] である。　数の配置に関する判定をするために、配列 houjin の領域を(N＋1)×(N＋1)の大きさで用意し、適切な初期値を設定する。N が3の場合の例を図3に示す。数が既に配置されているかどうかを判定するために、図3の太枠内の各マスの初期値は0とする。また、現在位置の右下のマスが太枠の外であることを判定するために、4行目のマスに SOTO_SHITA、4列目のマスに SOTO_MIGI、行4列4のマスに SOTO_KADO の三つの異なる定数（0からN²までの整数以外の整数）を初期値として設定する。

　配列houjinの初期化をする関数shokika、及び数を配置する関数mahoujinのプログラムを図4に示す。引数Nは、正の奇数（N≧3）である。

〔プログラムの判定部分の改変〕　図4のプログラムによるメモリ使用量の削減のために、配列houjinの領域をNxNに縮小し、定数SOTO_SHITA, SOTO_MIGI及びSOTO_KADOを使わないようにするプログラムの改変を考えた。図4の（F）の部分を改変したプログラムを図5に示す。

設問1：

本文中のアに入れる適切な式を答えよ。

模範解答

ア：

N^{3}

解説

解答の論理構成

【問題文】には
「縦・横・対角線のN個のマスの合計値は、いずれも(ア＋N)÷2となる。」
とあり、この値を“魔方陣の定和”と呼びます。
1 から $N^{2}$ までの整数を全て用いるので、方陣全体（ $N \times N$ 個）の総和は
$1 + 2 + \dots + N^{2} = \frac{N ^{2} \ 、 ( N ^{2} + 1 )}{2}$
です（等差数列の和）。
行は $N$ 本あります。各行の和が同じ定和 $S$ であるため
$N \times S = \frac{N ^{2} \ 、 ( N ^{2} + 1 )}{2} .$
両辺を $N$ で割ると
$S = \frac{N \ 、 ( N ^{2} + 1 )}{2} .$
この $S$ が【問題文】記載の
「(ア＋N)÷2」
に一致するはずなので
$\frac{[ \ 、ア \ 、 ] + N}{2} = \frac{N \ 、 ( N ^{2} + 1 )}{2} .$
分子を比較すると
$[\ 、ア \ 、] + N = N \ 、 (N^{2} + 1) = N^{3} + N .$
$N$ を両辺から引けば
$[\ 、ア \ 、] = N^{3} .$

以上より、アに入る式は $N^{3}$ です。

誤りやすいポイント

行数が $N$ 本あることを忘れ、総和を $S$ でそのまま割らずに計算してしまう。
等差数列の和 $\frac{n ( n + 1 )}{2}$ を $n^{2}$ と誤って覚える。
「(ア＋N)÷2」を $([ア] + N) / N$ と読み違え、分母を $2$ でなく $N$ にしてしまう。
$N^{3} + N$ と $N (N^{2} + 1)$ の展開・整理で符号ミスを起こす。

FAQ

Q: 定和

S

を列や対角線でも同じ式で求めてよいのですか？
A: はい。【問題文】に「縦・横・対角線のいずれにおいても、その並びの数の合計が同じ」とあるので、行・列・対角線すべてが同じ

S

になります。求め方は行を基準にしても列を基準にしても同じ値です。

Q: 偶数次（

N

が偶数）の魔方陣でも定和は同じ式になりますか？
A: 数字 1 〜

N^{2}

を使う点は同じなので定和の値そのものは

S = \frac{N ( N ^{2} + 1 )}{2}

になります。ただし偶数次は作り方が異なり、必ずしも本問のアルゴリズムでは生成できません。

N

が大きくなると

S

はどの程度のオーダーで増えますか？
A:

S = \frac{N ( N ^{2} + 1 )}{2} \approx \frac{N ^{3}}{2}

なので、

N

の三乗オーダーで増加します。

関連キーワード: 魔方陣、等差数列、総和計算、一次方程式

設問2：〔魔方陣のプログラム〕について(1)、(2)に答えよ。

（1）図中のイ〜キに入れる適切な字句を答えよ。

模範解答

イ：houjin[N+1] ウ：houjin[N+1]x エ：x ← (N+1)/2 オ：

N^{2}

未満カ：yb−1 キ：xb

解説

解答の論理構成

まず配列の初期化を確認します。問題文には
「配列 houjin の領域を(N＋1)×(N＋1)の大きさで用意し、…4列目のマスに SOTO_MIGI…」
とあり、各行の列 N＋1 に定数 SOTO_MIGI を入れる必要があります。よって
イ＝houjin[N+1]
となります。
次に下側境界の設定です。行 N＋1 の各列に SOTO_SHITA を入れるので
ウ＝houjin[N+1]x
です。
魔方陣の作り方では「最下行の中央のマスを現在位置」と明記されています。最下行は y＝N、中央列は (N＋1)/2 なので
エ＝x ← (N+1)/2
となります。
ループ条件は「全てのマスが埋まるまで」、すなわち最終値 N² が入る直前まで継続します。したがって while の条件は
オ＝N²未満
です。
右下へ移動した結果、そのマスが既に埋まっていた場合は「現在位置の上のマス」を新しい位置にする手順（E）をコードに落とし込みます。直前の位置は yb, xb に退避しているので
カ＝yb−1
キ＝xb
が正しい操作になります。

これで模範解答の各字句と一致します。

誤りやすいポイント

配列サイズを (N＋1)×(N＋1) に拡張している理由を忘れ、境界セルの添字を N で書いてしまう。
最下行中央を「(N/2)」と丸めてしまい偶数用の計算式にしてしまう。奇数限定であることに注意。
while 条件を「N² 以下」と書き、最後にダブって 1 行余分に処理してしまう。
yb−1 を yb+1 と書き間違え、現在位置が 2 行飛んでしまう。

FAQ

Q: 添字を 0 ではなく 1 から始める理由はありますか？
A: 問題文が「配列の添字は1から始まる」と規定しているためです。言語仕様ではなく出題条件に合わせています。

Q: while 条件を N² 以上にしないのはなぜですか？
A: 1 から N² が順に入るため、最後の値 N² を書き込んだ直後にループを抜ける必要があります。未満判定にしておけば余分な反復が起きません。

Q: houjin[N+1] だけで二次元配列を表せるのですか？
A: 多くの疑似言語では houjin[行] が行全体を示し、その後ろに [列] を付けてセルを参照します。行ループ内で使うことで houjiny[N+1] と同義に扱えます。

関連キーワード: 魔方陣、二次元配列、添字管理、番兵セル、ループ制御

設問2：〔魔方陣のプログラム〕について(1)、(2)に答えよ。

（2）図4の関数mahoujinを実行した場合、配列houjinの中で一度も参照も代入もされない要素が二つ存在する。該当する配列houjinの要素をそれぞれ答えよ。

模範解答

①：houjin[1][N+1] ②：houjin[N+1][1]

解説

解答の論理構成

まず、番兵セル（外側 1 行 1 列）を設定する処理を確認します。
・【問題文】図4‐shokika 内の
「houjiny[N＋1] ← SOTO_MIGI」
「houjin[N＋1]x ← SOTO_SHITA」
「houjin[N＋1][N＋1] ← SOTO_KADO」
という 3 行により、
- 右側番兵列：行 1～N, 列 N＋1
- 下側番兵行：行 N＋1, 列 1～N
- 右下隅：行 N＋1, 列 N＋1
  が番兵値で初期化されます。
次に、mahoujin で番兵セルが参照される流れを捉えます。
・同図 mahoujin の「y ← y + 1」「x ← x + 1」で、いまいるセルの右下（対角）に一歩進んでから houjinyx を参照します。
・もし参照した値が
「SOTO_SHITA」なら y ← 1、「SOTO_MIGI」なら x ← 1、「SOTO_KADO」なら y ← 1, x ← 1
というように、番兵が検出されたときのみ座標が書き換えられます。
ここで重要なのは「右下へ 1 マス動いてから判定する」という点です。
- 現在位置 (y,x) が「列 N」にあれば、右下へ動いた時に列 N＋1 (番兵列) に着きますが、行は y＋1 なので 1≤y＋1≤N です。したがって参照される番兵セルは「houjin[2～N][N＋1]」だけになります。
- 同様に、現在位置が「行 N」にあれば、右下へ動くと行 N＋1 (番兵行) になりますが、列は x＋1 なので 1≤x＋1≤N です。参照される番兵セルは「houjin[N＋1][2～N]」だけです。
- 「houjin[1][N＋1]」と「houjin[N＋1][1]」は、それぞれ
  ・右下へ 1 マス動く直前の位置が存在しない（行 0、列 0 になるため）
  ・また、番兵判定後の書き換えで参照されることもない
  ため、読み取りも書き込みも行われません。
したがって、一度も「参照も代入もされない」番兵セルは
①「houjin[1][N＋1]」
②「houjin[N＋1][1]」
の 2 要素となります。これは【模範解答】とも一致します。

誤りやすいポイント

番兵セル全体が「使われない」と思い込み、右側・下側の全セルを答えてしまう。実際にはほとんどの番兵セルはラップ判定で参照されます。
y ← 1 や x ← 1 の書き換え後に「列 N＋1 や行 N＋1 が再度参照される」と勘違いする。書き換え後は必ず内部セル（1～N）が対象です。
右下隅「houjin[N＋1][N＋1]」は一見不要に見えるが、(N,N) から右下へ動いたときに確実に参照されることを見落とす。

FAQ

Q: もし y ← y + 1 と x ← x + 1 の順番を逆にしても未使用セルは同じですか？
A: はい。同じタイミングで右下へ 1 マス移動するため、行・列どちらを先に増やしても到達できる番兵セルの集合は変わりません。

Q: houjin[0][] や houjin[][0] を使う実装例もありますが、今回使わない理由は？
A: 配列添字を 1 から始める方がアルゴリズム（人間の行列番号）に合わせやすいためです。番兵が必要な境界は「下」と「右」だけと割り切ることで余計な配列外判定を減らしています。

Q: 配列サイズを NxN に縮小した図5 の改変でも、この 2 要素が未使用になる事実は活用できますか？
A: いいえ。図5 では番兵セルそのものを削除しているため「未使用セル」という概念がなくなります。番兵判定は添字の範囲チェックへ置き換えられています。

関連キーワード: 番兵、2次元配列、添字操作、範囲チェック、wrap-around

設問3：

図5中のク、ケに入れる適切な字句を答えよ。

模範解答

ク：N ケ：1

解説

解答の論理構成

配列の大きさ
改変後のプログラムは「配列houjinの領域をNxNに縮小し、定数SOTO_SHITA, SOTO_MIGI及びSOTO_KADOを使わない」と記述されています。したがって行・列の有効な添字は 1 ～ N だけです。
行番号 y の判定
図5では最初に

y ← y + 1

を行い、直後に

if( y がクよりも大きい ) y ← ケ endif

で範囲外を補正します。
• ここで「よりも大きい」と比較する上限は最大添字 N です。
• 範囲外（N+1）になったときに折り返す先は最上行、すなわち 1 行目です。
列番号 x の判定
同じく

x ← x + 1 if( x がクよりも大きい ) x ← ケ endif

でも上限は N、折り返しは 1 列目です。
結論
よって
ク＝「N」、ケ＝「1」
となります。

誤りやすいポイント

0 始まりと混同してケに「0」を入れてしまう。配列は 1 始まりです。
クを「N-1」としてしまう。添字 N も正当な内部セルなので誤りです。
「行」と「列」を別値にしてしまう。どちらも同じ比較・代入式を使うため同一値が入ります。

FAQ

Q: N が奇数である条件はク・ケの決定に影響しますか？
A: 影響しません。奇数であるのは魔方陣生成アルゴリズムの前提で、配列添字範囲 1～N は偶数でも同じです。

Q: 折り返し処理を if でなく modulo 演算に置き換えても良いですか？
A: 実装上は可能です。ただし設問は図5の if/endif 構造を前提としているため、空欄には比較対象と代入値をそのまま記入します。

Q: 「よりも大きい」ではなく「≧」を使う実装と混同しそうです。
A: 先に y ← y + 1 を実行してから比較するので「大きい（>）」で正しく範囲外を検出できます。「≧」にすると N から N への更新時に誤って折り返す危険があります。

関連キーワード: 配列境界、ラップアラウンド、魔方陣アルゴリズム、インデックス、二次元配列

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2016年 秋期 午後 問03

魔方陣に関する次の記述を読んで、設問1～3に答えよ。

.css-epvm6{white-space:nowrap;}設問1：

模範解答

解説

解答の論理構成

誤りやすいポイント

FAQ

設問2：.css-1hn4tij{display:inline;overflow-wrap:anywhere;word-break:break-word;min-width:0px;}〔魔方陣のプログラム〕について(1)、(2)に答えよ。

模範解答

解説

解答の論理構成

誤りやすいポイント

FAQ

設問2：〔魔方陣のプログラム〕について(1)、(2)に答えよ。

模範解答

解説

解答の論理構成

誤りやすいポイント

FAQ

設問3：

模範解答

解説

解答の論理構成

誤りやすいポイント

FAQ

応用情報技術者 2016年秋期午後問03

設問1：

設問2：〔魔方陣のプログラム〕について(1)、(2)に答えよ。