番兵を使った線形探索の実装。 線形探索は床に並べたトランプと端から確認していき、目的の数を探すような 直感的なアルゴリズム。 当然、計算量はデータ量Nに対してO(N)となる。しかし、番兵を使うと定数倍の計算量の違いがでる。番兵を使わないと for (int…

以下の論文でシュミレータの元となる数式があるらしい。 手が開いたところでやってみよう。■論文 Craig Reynolds: Flocks, Herds, and Schools: A Distributed Behavioral Model ■参考書籍エンジニアとしての生き方 IT技術者たちよ、世界へ出よう！ (インプ…

基本的なデータ構造の学習。 ここでは、逆ポーランド記法で与えた数式をスタックで計算させる。 スタックを用いた計算方法は、東北大学の外山先生の授業がわかりやすかったが、 講義資料はHPに無いようだ。ちなみに、ここでは演算子を"+"や"-"にしているが、…

今までのようにループ回数から計算量を直感的に求められないアルゴリズム。 挿入ソートは、整列されていれば高速に動作し、そうでない場合にはN(N-1)/2よりO(N^2)のアルゴリズムに なるのだった。この特徴を生かし、あらかじめざくっと(３個ずつとか４個ずつ…

ソートが安定的か判定する。と言っても、バブルソートを安定的として、選択ソートの結果と先頭から 単純に比較していく。先頭から比較していくだけなので、計算量はデータNに対してN回になる。これだけではつまらないので、N^4となるアルゴリズムでも実装し…

あらかじめ床に並べられたトランプを見ていき(j)、 一番小さい数を先頭の数と交換する。 そうすると、比較した回数分、先頭からはソート済みになるので、 次の比較は先頭から比較した回数ぶん後ろ(i)から見ればよい。選択ソートでは、離れた要素を交換するの…

挿入ソートと違い、あらかじめ床に並べてあるトランプを整列させる。 (結局全部並べた暁には、メモリの使用量は同じだけれど・・・。)考え方は簡単で、一番後ろの要素から一つずつ比較していく。 全要素比較したあとでは、要素がソートされている。 ここでは…

練習の記録を残すために、GitHubでのコード保存をすることにした。参考にしたのは、以下のページ。手順どおりに実施したところすぐにできた。参考URL[GitHubの使い方：画像付き] GitHubデビューが意外と簡単だった！！tontotakumi.com

ソートは計算量の見積もり練習として良い題材となる。 (for文から直感的に見積もることができるから。) for文はプログラム中でも頻繁に使うため、実践的である。初等とは、効率が悪い事もあるが、実装が簡単という意味である。以下にアルゴリズムを紹介する…