解答例・解説

情報処理 II レポート課題 (2012 年 12 月 25 日) の解答例・解説
(2013 年 1 月 25 日改訂)
問 1: (省略)
問 2: 空行を除き 6 行で構成され，最初の行は，解の通し番号である．その次から 5 行
は，5 行 7 列で構成されるマス目において，左上をスタート，右下をゴールとして，
それぞれのマスをちょうど 1 回ずつ通るルートを表している．それぞれのマスには
「U」
「D」
「L」
「R」
「*」のいずれかが書かれ，それぞれ，
「上に進む」
「下に進む」
「左
に進む」「右に進む」「ゴールに着いた」を意味する．
問 3: 左上をスタート，右下をゴールとして，それぞれのマスをちょうど 1 回ずつ通る
ルートをすべて求める．
問 4: 以下のとおり．
74 行目 移動先候補の X 座標（列の位置）を求める．
75 行目 移動先候補の Y 座標（行の位置）を求める．
85 行目 x_new および y_new を移動先とし，rp の指し示す構造体に格納する．
90 行目 rp の値に基づいて，解を出力する．
93 行目 上下左右に移動を試みる．
96 行目 85 行目の呼び出しで格納した値を取り除く．
問 5: 何も出力しない．
問 6: 以下のとおり．
• コメントが皆無である．ファイルの先頭にファイル内容や作成者の情報，構造
体や変数の定義ではその意味，関数にはその機能をそれぞれ記述すればよい．
• 関数名が短すぎて，何を行う関数なのかが分かりにくい．例えば display は
print_route とするとよい．
• 自作関数の new は C++ の予約語であり，C/C++ 対応のコンパイラではエ
ラーとなる．関数名を new_position にするとよい．
• 81 行目の「|| rp->length > rp->length_goal」について，値の格納のさ
れ方を考慮すると，ここで真の値に評価されることはない．したがって，取り
除いてよい．
問 7: 問題文：左上をスタート，右下をゴールとした最短路をすべて求めるには，プログ
ラムのどこをどのように変更すればよいか．
答え：57 行目を「r.length_goal = width + height - 2;」とする．
1
補足
• 着想を得たのは，http://www.youtube.com/watch?v=Q4gTV4r0zRs．この動画
の「5 × 5」の解（同じところを 2 度通らない道順の数）を，今回のプログラムで
求めるには，88 行目の「&& rp->length == rp->length_goal」をコメントにし
てコンパイルし，./route 6 6 を実行すればよい．
• 複数の解条件および出力文字セットから選べる Ruby スクリプトを https://
gist.github.com/4567205 で公開し，http://d.hatena.ne.jp/takehikom/
20130119/1358535393 にて解説した．
• 問 1–4 はいずれも，このプログラムを読み解くのに欠かせない箇所を，出題にして
いる（とはいえ，問 1 はコピー答案抑止の意味合いもある）．試験で「説明／論述
しなさい」とあったら，「何を書いてもいい」ではなく，その対象について問われ
ている主要なことは何なのか，よく考えてから，答案を書くようにしてほしい．
• 問 4 について，関数 search は，上下左右に移動しながら探索を行っている．無限
ループに至らない処理が必要で，それは 80 行目の式が担っている．同種のプログ
ラムは，昨年度の情報処理 II の授業（第 9 回および試験）で取り上げているので，
手続きが分かりにくければ読むとよい．
• 問 5 について，このプログラムでは行数と列数がともに偶数のとき，解なしとな
る．以下，その理由を述べる．簡単のため 4 行 4 列を考え（任意の偶数でも同様）
，
次のようにＡとＢを配置する．
ＡＢＡＢ
ＢＡＢＡ
ＡＢＡＢ
ＢＡＢＡ
左上を 1 番目として上下左右に移動するとき，奇数番目はＡ，偶数番目はＢのいず
れかに位置する．
解がないことを示すには，背理法を用いる．解があると仮定すると，ゴールはス
タートと同じＡなので，そこへは奇数番目に着くことになる．一方，それぞれのマ
スをちょうど 1 回ずつ通ってゴールに着くようにするためには，ゴールには 4 ×
4 ＝ 16 番目すなわち偶数番目に着かなければならない．したがって矛盾．
「行数と列数がともに奇数のとき」と「行数と列数の一方が偶数，もう一方が奇数
のとき」には，自明な解が存在する．配置からも，ともに偶数のときとは状況が異
2
なるのが確認できる．
3 行 3 列（ＡはＢより 1 つ多い）:
ＡＢＡ
ＢＡＢ
ＡＢＡ
3 行 4 列（ゴールはＢ）:
ＡＢＡＢ
ＢＡＢＡ
ＡＢＡＢ
「走らせ終了を待つまでに，結果がどうなるかを考える」ことを習慣とし，今後の
プログラミングに役立ててほしい．
3
誤答例 (「//」以降は村川のコメント)
• (問 2) 1 行目は試行番号 // もし，「試行番号」と表現するなら，成功した番号・失
敗した番号があるべきである．今回のプログラムでは，解が見つかれば，通し番号
を振って No.1 から順に出力している．
• (問 2) 1 行目は問題番号 // 「問題」ではなく「解」の番号である．
• (問 2) 1 行目は出席番号 // プログラムの出力として見たときは，「出席番号」でも
「学生番号」でもない．
• (問 3) 左上から右下に移動するプログラム // それでは斜め移動になってしまう．
• (問 3) 左上をスタート，右下をゴールとして，ルートをすべて求める // それは，
補足のところで URL を記した動画と同じになる (通らないマスがあっても良いた
め，解の数は増える)．
• (問 3) 左上をスタート，右下をゴールとして，それぞれのマスをちょうど 1 回ずつ
通るルートを求める // 「すべて」のルートを求めるプログラムである．
• (問 4) NEW 関数 // 関数名はいずれも小文字である．C 言語では，大文字と小文
字は区別される．
• (問 5) ともに偶数にするとエラーが発生する // エラーは起こらない．何も出力し
ないだけである．
• (問 5) 動かなかった // 正しく打ち込んだプログラムなら，
「動いた」けれども「何
も出力しなかった」となる．
• (問 6) 創作関数 // 「自作関数」と書こう．
• (問 6) if 分 // 「if 文」である．推敲しよう．
• (問 6) 大文字が多い // 定数は大文字を使って表記するのは，C 言語の慣例であり，
間違いではない．慣れてほしい．
• (問 6) 行ごとに適切にコメントアウトする // 「コメントをつける」と書きたかっ
たものと思われる．「コメントアウト」は，プログラムコードを一時的にコメント
にし，コンパイルや実行の対象外とすることをいう．またコメントは行単位ではな
く (変数などの宣言では逐一するほうがよいが)，処理のまとまりごとにつけるべき
である．
4
誤答にはしなかったが要注意 (「//」以降は村川のコメント)
• (体裁) 右上を綴じている // 2 穴バインダに答案を入れると，あとで見るのが困難
になる．左上を綴じること．
• (体裁) 針なしホッチキス (ステープラ) で綴じている // 減点にはしないが，レポー
ト全体の中で，違和感があった．
• (体裁) 教科書体のフォントを使用している // 明朝体・ゴシック体を基本としよう．
• (体裁) 2 段組で書く // レポートで 2 段組は推奨しない．
• (体裁) 問 1、 // 読点はつけない．空白を入れる．「問 1。」
「問 1.」も良くない．箇
条書きの「1.」は，差し支えない．
• (体裁) 問一 // 数字は原則として算用数字を用いる．
• (問 1) 以下のように，2 行目以降の出力が不揃いになった．
No.2
RRRRRRD
DLLLLLL
RRRRDRD
DLLLLUD
RRRRRU*
// 等幅フォントを使えば，きれいに書ける．Word で書くのなら，「ＭＳ 明朝」が
該当する．それに対し「ＭＳ Ｐ明朝」はプロポーショナルフォントと呼ばれる．
(ちなみに「等幅」は「とうはば」という．)
• (問 2) 1 行目は初項 1，公差 1 の等差数列 // 「通し番号」という言葉を知ってお
こう．
• (問 3) 一筆書きする // 説明としては，それでよいが，パズルなどで出題されたり，
情報科学 (グラフ理論) で検討されたりしてきた「一筆書き」とはかなり異なる．
今回のプログラムは，グラフの形状が制限され，始点と終点が固定された状況での
「ハミルトン路」を求めるものである．
• (問 5) 結果は表示されない // 計算機内部で「結果」を持っているが，それは標準
出力に書き出されない，と読める．実態は，そうではない．
• (問 6) 僕なら // レポートや外向けの文書で「僕」は使わないように．しかし，単
純に「私なら」に置き換えればいいというものでもない．この種の一人称は，使用
しないことで，客観的な文章を作ることができる．
5