キンサクプログラマー

お金儲けと技術のメモ

アルゴリズム

毎日アルゴリズム(第5日目)ボゴソート

効率の悪いソートアルゴリズム クイックソートやバブルソートなどが有名なソートアルゴリズムだが、中でも効率の悪いボゴソートをご存知だろうか。効率悪いアルゴリズムという響が新鮮だが、いってしまえばただ単にランダムでソートするだけのアルゴリズムだ…

毎日アルゴリズム(第4日目)ダイクストラ法 その2

pikurusux.hatenablog.com 時間が開いたが実装してみた。 アルゴリズム自体はその1に乗っているので、詳細はそちらへ。 まともに動いているのか至極怪しいが、一応動く。 github.com なんとなくポイント。 最短距離から計算しよう 常に最短のノードから計算…

pythonの演算比較してみたらシフト演算が遅い事に気づいた

ダイクストラ法の実行時間を計測しようとtime関数をいれて見てたら気づいた。 import time a = 6 print(str(time.time()) + "sec") a = a >> 2 print(str(time.time()) + "sec") a = a/2 print(str(time.time()) + "sec") a = a+2 print(str(time.time()) + …

毎日アルゴリズム(第3日目)ダイクストラ法 その1

毎日どころか毎週もやっていないアルゴリズムだけど、この名前で続けようと思う。 3日目は最短経路問題でよく出るダイクストラ法。 いろんなサイトで解説されているが、下記のサイトが個人的には理解しやすかったので、 参考にされたし。 ちなみにソースは…

毎日アルゴリズム(第2日目)ユークリッドの互除法

ユークリッドの互除法 他のアルゴリズムをやろうとしたが間に合わず急遽変更。 高校生レベルのユークリッドの互除法で満足しとく。 概要 二つの数字の最大公約数を高速に求めるアルゴリズム。 通常であれば素因数分解などで求めるが、こちらの方が早いらしい…

毎日アルゴリズム(第1日目)エラトステネスの篩

暇なので毎日アルゴリズムを勉強することにした。1日で終了しないことを目標に頑張ろうと思う。 いつか、ホットエントリーにのるその日まで・・・ エラトステネスの篩 エラトステネスの篩とは素数を見つけるアルゴリズム。N以下の素数を全部みつけることが…