アルゴリズムとデータ構造2(テスト返却)

私のテスト結果は100点満点中68点でした. 平均点は64.7, 最高点は92点だそうです.

手計算が多くて全然駄目だと思っていたのですが, 意外とそこそこ出来ていたそうです.

紙上でアルゴリズムの計算過程を書くよりも, プログラミング言語で書いて出すという形式の方が良かったと思いました. まあ自分が有利になるからそう思っているだけで, 全体で良い講義になるという確証があるわけではないのですが.

間違えた答えについては, 計算用紙を提出してしまったのでなんでこんな答えが出てきたのかわからなくなってしまいました.

木構造

挿入した後のB木の構造正解した人5人だけらしいですね. なんで私は正解していたんだ…? 完璧に正解しているじゃないですか.

文字列"aoba"を整数値として読み込み83でmodを取りハッシュ化したハッシュ値の計算.

私は手計算で71という値を出しましたが誤っていたようですね.

私は上から $c * 256^{index}$ で文字に数値をかけていくと思ったのですが, indexの向きが逆で, 降順だったようです.

しかしその方式で計算してみたとしても

Prelude Data.Char> (sum $ map (\(c, i) -> ord c * 256^i) $ zip "aoba" [0 ..]) `mod` 83
20

で71にはならないんですよね. 私はどういう手計算をしたのでしょう.

講義スライドを元に計算しました.

Prelude Data.Char> (sum $ map (\(c, i) -> ord c * 256^i) $ zip "aoba" [3, 2, 1, 0]) `mod` 83
68

68が正解ですね. 私はどういう計算をして71を出したのでしょうか.

インデックスが正しかったとしても, 暗算は学習障害持ちの私は完全に無理なので, どうやっても間違えていたことでしょう. 仕方ないです.

ポポプポプトピポテピプからポプテピを探索する時BF法とBM法での文字比較回数を求めよ.

BFの方は16で正解しました.

BMの比較回数を10として誤ってしまいました.

今適当に見て計算したら7という値が出てきました. しかしこれは引っかかりやすい値で, 正解は8だそうです. あれ7で良くないですか, なんで8なんです? 話を聞いてもよくわからない.

まあ私は10という完全に謎の値を書いたのですが. 部分点これについてて良いんでしょうか.

BM法は本格的になると複雑なアルゴリズムなので本当にこれで良いのかよくわからなくなる.

パターンの末尾を基準にインデックス動かすのではなくて, パターンの不一致部分からインデックスを動かすようですね. 納得しました. 勘違いしていたようです.

これはまあ書くだけだったので.

と思ったら東京から品川まで8分と書いてあるのを有向グラフと解釈して双方向に飛べないと考えた人も居たんですね. 確かにそちらの方が現実に即しては居ますね, 上りと下りが同じ時間ではないことのほうが多い. その後にダイクストラ法で計算することとか考えると無向グラフの方が問題としては自然なのですが…

まあどちらでも正答扱いなので良いですね.

終わった後に隣接行列が全然違うじゃんと間違いだなと思ったのですが, 正解扱いでした. 距離を行列に書いていって同じ駅は0, 繋がっていない駅は-1とする方法でも良いのでしょうか. これも隣接行列の1つとしてOKもらったのかな.

隣接リストと混同するのは流石にしませんでした. 隣接行列と書いてあるので最低限行列ということだけはわかったので.

ダイクストラ法のアルゴリズム書いていて良かった. 正解しました.

ダイクストラ法で距離求めていたので問題ありませんでした.

この辺で時間が完全になくなりました.

時間が足りなくて書けなかったのですが, ヒープソートは途中まで書いていたので部分点2点を貰いました.

略称を数値にするのは思いつきませんでした. 一意なのでそれで良かったですね.

略称がみんな違って答え合わせが大変なら, 完全にソートの項だけ分割して普通に数値を題材にしてソートする問題を出せば良かったのでないでしょうか…

ヒープソートの手順がムチャクチャで, 時間が足りててもダメでしたねこれは. ヒープに追加する要素を頭から行うのではなく, 何故か末尾から行ってしまっています. この方法でもソートは多分正常に終了しますが, 計算回数が多いのでヒープソートとは呼べないでしょう.

クイックソートはコードは実装できるけど何やってるのか紙面上に書くのは多分無理なので時間があってもおそらく間違えていたでしょう.