応用情報技術者 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のマスは、houjin[y][x] で表現する。例えば、図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）である。

↩設問2(1) ↩設問2(2)

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

↩設問3

設問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

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

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

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

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

問題文を見る

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

模範解答

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

N^{2}

未満カ：yb−1 キ：xb

解説

解答の論理構成

関数 shokika の右側の境界（イ）
本文に「配列 houjin の領域を(N＋1)×(N＋1)の大きさで用意し」「4 列目のマスに SOTO_MIGI…を初期値として設定する」とあります（N が 3 の場合）。一般には、各行の N+1 列目に SOTO_MIGI を入れます。図4では、行 y のループの中で、列 x のループ（太枠内を 0 にする処理）の後に [イ] ← SOTO_MIGI があるので、行 y の N+1 列目を指定します。
イ＝houjin[y][N+1]
下側の境界（ウ）
同じく「4 行目のマスに SOTO_SHITA」とあり、一般には N+1 行目の各列に SOTO_SHITA を入れます。図4では列 x のループの中に [ウ] ← SOTO_SHITA があるので、N+1 行目の列 x を指定します。
ウ＝houjin[N+1][x]
最後の「houjin[N+1][N+1] ← SOTO_KADO」で右下の角が埋まり、図3の初期値ができあがります。
最初の位置（エ）
本文の作り方は「最下行の中央のマスを現在位置」から始まります。関数 mahoujin の先頭で y ← N としているので、列は中央の (N+1)/2 です。N は奇数なので割り切れます。
エ＝x ← (N+1)/2
ループの条件（オ）
最初に 1 を置き、ループの中で suuji を 1 増やしてから置きます。N² を置いたら終わるので、ループを続ける条件は suuji が N² 未満であることです。
オ＝N²未満
移動先が埋まっていた場合（カ・キ）
右下へ移動した先のマスが 0 でない（既に数がある）ときは、本文の(E)のとおり「現在位置の上のマス」に移ります。移動前の位置は yb、xb に退避してあるので、その一つ上です。
カ＝yb−1
キ＝xb

誤りやすいポイント

イを houjin[N+1][y]、ウを houjin[x][N+1] と、行と列を逆にしてしまう。本文の「行 y 列 x のマスは、houjin[y][x] で表現する」のとおり、先の添字が行です。SOTO_MIGI は右側（列 N+1）、SOTO_SHITA は下側（行 N+1）です。
最下行中央を N/2 としてしまう。N は奇数なので (N+1)/2 が中央です。
オを「N²以下」にしてしまう。suuji が N² になった時点でループに入ると、N²+1 を置こうとしてしまいます。
カを yb+1 としてしまう。(E)は「上のマス」なので行番号は 1 減ります。

FAQ

Q: なぜ配列を (N+1)×(N+1) に広げるのですか？
A: 右下へ移動したときに太枠の外へ出たかどうかを、外側のマスの値（SOTO_SHITA、SOTO_MIGI、SOTO_KADO）で判定するためです。図4の(F)の部分は、この値を見て移動先を折り返しています。

Q: 添字を 0 ではなく 1 から始めるのはなぜですか？
A: 本文で「配列の添字は 1 から始まる」と定めているためです。

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

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

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

問題文を見る

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

模範解答

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

解説

解答の導き方

結論として、参照も代入も一度もされない要素は houjin[1][N+1] とhoujin[N+1][1] です。以下で順を追って示します。

前提（配列の初期化）
- 問題文の shokika の趣旨から、配列は $(N + 1) \times (N + 1)$ の領域を持ち、太枠内は 0、外周に境界用定数が置かれます。図4 の最後にある通り「houjin[N+1][N+1] ← SOTO_KADO」があることから、右列（列 $N + 1$ ）や下行（行 $N + 1$ ）にも値が設定されていることが分かります。したがって候補の参照先は内側の $1 \dots N$ 領域と、境界用セル（行または列が $N + 1$ のセル）です。
初期位置とループ内での増分
- 図4 に「y ← N」があり、本文の手順に「最下行の中央のマスを現在位置とし、現在位置に数1を配置する(A)」とあるので、mahoujin の開始時点で現在位置は行 $y = N$ 、列 $x$ は $1 \dots N$ の値（中央値）です。よって最初の代入は内側領域に行われます。
- ループの主要部分でまず行われるのは「y ← y + 1」「x ← x + 1」です。ループ前の $y, x$ は常に $1 \leq y, x \leq N$ なので、増分直後の値は $2 \leq y \leq N + 1, 2 \leq x \leq N + 1$ となります（ $y = 1$ や $x = 1$ にはならない点に注意してください）。
境界判定の読み取りが行われる時点の範囲
- 増分直後に行っている判定は図4の通りです：「if( houjin[y][x] がSOTO_SHITAと等しい )」「elseif( houjin[y][x] がSOTO_MIGIと等しい )」「elseif( houjin[y][x] がSOTO_KADOと等しい )」。
- ここで実際に読み取られるセルは増分直後の $(y, x)$ に対応しますから、読み取り候補は $y \in {2, \dots, N + 1}$ 、 $x \in {2, \dots, N + 1}$ の組に限られます。したがって読み取り時に $y = 1$ または $x = 1$ が起こらないため、houjin[1][N+1]（ $y = 1, x = N + 1$ ）やhoujin[N+1][1]（ $y = N + 1, x = 1$ ）をこの段階で読むことはありえません。
- 各分岐の意味を具体的に見ると、
  - SOTO_SHITAが成立するのは読み取った位置が $(N + 1, 1 \dots N)$ のときですが、読み取り時は $x \geq 2$ なので実際に読み取られるのはhoujin[N+1][2..N] でありhoujin[N+1][1] は読み取られません。
  - SOTO_MIGIが成立するのは読み取った位置が $(1 \dots N, N + 1)$ のときですが、読み取り時は $y \geq 2$ なので実際に読み取られるのはhoujin[2..N][N+1] でありhoujin[1][N+1] は読み取られません。
  - SOTO_KADOは $(N + 1, N + 1)$ のみを読みます。
その後の占有判定と代入
- 増分→境界判定の後に行う「if( houjin[y][x] が0と等しくない )」の読み取りは、境界判定で $y, x$ を必要に応じて $1$ に戻すため、この判定時の $y, x$ はいずれも $1 \leq y, x \leq N$ になります。したがってこの判定でも列 $N + 1$ や行 $N + 1$ のセルは読まれません。
- 実際の数の代入は「houjin[y][x] ← suuji」のみであり、この代入は常に $1 \leq y, x \leq N$ の位置に対して行われます。よって mahoujin による代入で境界セル（列 $N + 1$ や行 $N + 1$ ）が上書きされることもありません。
まとめ（結論）
- 増分直後の読み取りは $y, x \geq 2$ を満たす組のみを見ており、その後の占有判定と代入は $1 \leq y, x \leq N$ の範囲で行われるため、houjin[1][N+1]（ $y = 1, x = N + 1$ ）とhoujin[N+1][1]（ $y = N + 1, x = 1$ ）はmahoujinの実行中に一度も参照されず、また代入もされません。

最終解答（設問の求め方に合わせて） ①：houjin[1][N+1]
②：houjin[N+1][1]

誤りやすいポイント

増分直後の $y$ や $x$ の取り得る範囲を誤ること。増分後は $2 \leq y, x \leq N + 1$ であり、誤って $1 \leq y + 1 \leq N$ のように書くと結論が崩れます。
「右下へ1マス動かす直前の位置が存在しない（行0、列0になる）」のように表現すると混乱します。添字は1始まりなので $y = 0$ や $x = 0$ はあり得ない、という算術的理由で説明する必要があります。
shokikaとmahoujinの役割（shokikaが境界用の定数を設定し、mahoujinはそれを参照してラップ処理をする）を混同すると、どの段階でどのセルが読まれるかを誤認します。
if の順序や分岐後の代入（y←1, x←1 等）を考慮せずに、途中で (1,N+1) のような組が発生し得ると誤判断することがあります。実際の判定順と値域を順に追って検証してください。

FAQ

Q: 境界判定で使われるSOTO_MIGI/SOTO_SHITA/SOTO_KADOはmahoujinでどのように参照されますか？
A: 増分直後に「if( houjin[y][x] がSOTO_SHITAと等しい )」「elseif( houjin[y][x] がSOTO_MIGIと等しい )」「elseif( houjin[y][x] がSOTO_KADOと等しい )」という順で読み取られます。読み取り時の

(y, x)

は

2 \leq y, x \leq N + 1

に限定されるため、読み取られるSOTOセルはhoujin[N+1][2..N], houjin[2..N][N+1], houjin[N+1][N+1] のいずれかだけです。

Q: mahoujinによって境界セルが上書きされることはありますか？
A: いいえ。実際の数を代入する命令は「houjin[y][x] ← suuji」ですが、この代入は境界判定後で

1 \leq y, x \leq N

が成り立つ場合にのみ行われます。したがって mahoujin による境界セルの上書きは起きません。

Q: もし配列の添字が0始まりなら今回の結論は変わりますか？
A: はい。今回の議論は「配列の添字は1から始まる」という前提を利用しています。添字が0始まりに変わると増分直後の値域やSOTOの配置が変わり、未参照セルの組は変わる可能性があります。

関連キーワード: 2次元配列、境界チェック、添字の範囲、場合分け、初期化

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問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 への更新時に誤って折り返す危険があります。

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

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 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)に答えよ。