創造情報H22年アルゴリズム

去年の創造情報の過去問を一問だけ解いたのでせっかくだからうp

 

情報理工学系研究科創造情報学専攻、専門の第一問、アルゴリズムの問題

シャーペンで書いたのそのままなのでかなり見にくいですが…

 

h22algorithm_1

h22algorithm_2(クリックででかい画像)

 

この問題は、実際にアルゴリズムを知らなくても、読めばとけるので例年に比べて簡単だったと思います。

 

(1),(2)はただ手動で計算するだけ。(2)で計算ミスしないように。

これ検算せずにUPしてるので間違ってたらコメントとかでお願いします汗

 

(3)の比較考察せよってのはたぶん計算量のオーダーとか言えばいいのかなと。

edgeの数をmとすると、n>mならAlgorithm1-ALL有利。

n<mならAlgorithm2が有利です。

空間計算量は一応Algorithm1-ALLのほうが有利な気がします。

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">