...

解答例・解説

by user

on
Category: Documents
1

views

Report

Comments

Transcript

解答例・解説
情報処理 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 列を考え(任意の偶数でも同様)
,
次のようにAとBを配置する.
ABAB
BABA
ABAB
BABA
左上を 1 番目として上下左右に移動するとき,奇数番目はA,偶数番目はBのいず
れかに位置する.
解がないことを示すには,背理法を用いる.解があると仮定すると,ゴールはス
タートと同じAなので,そこへは奇数番目に着くことになる.一方,それぞれのマ
スをちょうど 1 回ずつ通ってゴールに着くようにするためには,ゴールには 4 ×
4 = 16 番目すなわち偶数番目に着かなければならない.したがって矛盾.
「行数と列数がともに奇数のとき」と「行数と列数の一方が偶数,もう一方が奇数
のとき」には,自明な解が存在する.配置からも,ともに偶数のときとは状況が異
2
なるのが確認できる.
3 行 3 列(AはBより 1 つ多い):
ABA
BAB
ABA
3 行 4 列(ゴールはB):
ABAB
BABA
ABAB
「走らせ終了を待つまでに,結果がどうなるかを考える」ことを習慣とし,今後の
プログラミングに役立ててほしい.
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 で書くのなら,「MS 明朝」が
該当する.それに対し「MS P明朝」はプロポーショナルフォントと呼ばれる.
(ちなみに「等幅」は「とうはば」という.)
• (問 2) 1 行目は初項 1,公差 1 の等差数列 // 「通し番号」という言葉を知ってお
こう.
• (問 3) 一筆書きする // 説明としては,それでよいが,パズルなどで出題されたり,
情報科学 (グラフ理論) で検討されたりしてきた「一筆書き」とはかなり異なる.
今回のプログラムは,グラフの形状が制限され,始点と終点が固定された状況での
「ハミルトン路」を求めるものである.
• (問 5) 結果は表示されない // 計算機内部で「結果」を持っているが,それは標準
出力に書き出されない,と読める.実態は,そうではない.
• (問 6) 僕なら // レポートや外向けの文書で「僕」は使わないように.しかし,単
純に「私なら」に置き換えればいいというものでもない.この種の一人称は,使用
しないことで,客観的な文章を作ることができる.
5
Fly UP