うさぎでもわかるアルゴリズム 動的計画法
こんにちは、ももやまです。 動的計画法は、アルゴリズムでもかなり重要な内容です。AtCoderやらプログラミングコンテストとかでもよく出てきます。 ですが、動的計画法は「アルゴリズムを学ぶ上での壁・登竜門」とも呼ばれるとおり、かなり難易度の高いアルゴリズムとなっています。どの参考書を見てもなかなかわかりやすくは書かれていません。 そんな動的計画法を今回はうさぎでもわかるようにわかりやすくかみ砕いて説明したいと思います。 １．動的計画法とは 動的計画法とは、 問題をいくつかの簡単で小さな問題に分割 それぞれの問題の計算結果を表に記録 同じ問題に対しては表から計算結果を参照する の3つの特徴を持ったアルゴリズムです。 といきなり言われてもわけがわからないと思うので、動的計画法のイメージを説明しましょう。 動的計画法のイメージ 例えば、\[ 28 \times 37 \]の計算を解きなさい。 と
弾幕ゲームと数学
くいなちゃん @b2 sinh、cosh、tanh などの双曲線関数って、どんな分野で使うんです…？ あまり使う分野を見たことがないので、標準ライブラリから外そうと思いますが、使う人います？ 2012-08-04 12:30:41
デザインパターン習得編
ホーム < ゲームつくろー！ デザインパターン習得編 コンセプト デザインパターン事始め 生成に関するパターン Abstract Factory 一塊のオブジェクト群を沢山の種類用意する Builder 同じ生成過程で完成する色々なオブジェクト Factrory Method 子オブジェクトを親クラスの関数で作る Prototype 原型を用意して、後はコピーコピーコピー Singleton 存在するオブジェクトは1つだけ 構造に関するパターン Adapter 変換コネクタパターンです Bridge インターフェイスと実装の分離入れ替え自由自在 Composite 入れ子の入れ子の入れ子の入れ子の･･･ Decorator 知らずに着飾るオブジェクト Facade ユーザに優しいシステム操作人 Flyweight ゲーム製作でおなじみのオブジェクト使い回し法 Proxy オブジェクトへのア
その６ 楕円と点の衝突
ホーム < ゲームつくろー！< 衝突判定編 2D衝突編 その６ 楕円と点の衝突 実に1年4ヶ月ぶりの2D衝突編の更新となりました。円に点が衝突している（含まれている）かどうかは2D衝突編その３で紹介しておりますが、ここで考えるのは「楕円と点」の衝突です。 楕円というのは円を何らかの方向に伸ばした（縮めた）図形です。英語ではエリプス(ellipse)と言います。オーバル(oval)というのも楕円形の意味がありますが、これはどちらかというと卵型の意味が強いようです。「楕円って円みたいなもんでしょ？」と思われるのは大きな間違いです。例えば、ただ円を伸ばしただけなのに、楕円の円周の長さやその面積は解析的に解く事ができなくなります。点との衝突も同じでして、円の中心点と云々というほど簡単な話ではなくなります。 ただ、楕円には1つうれしい性質があります。それは、長径（長い方の径）方向をしゅしゅしゅと縮め
平面幾何におけるベクトル演算 » 直線と線分
で求まります（ここで |x×y| は実数に対する絶対値， |x| はベクトルに対する絶対値と「絶対値」の意味が異なっている点に注意してください）。 コーディングは以下の通りです*1： // 点a,bを通る直線と点cとの距離 double distance_l_p(P a, P b, P c) { return abs(cross(b-a, c-a)) / abs(b-a); } 線分と点の距離 今度は線分と点の距離を考えてみましょう。 距離としてどのような値が欲しいのか，というのは問題依存なのですが， ここでは一般的な距離の定義に従って，点から「線分のどこか」への最短距離としてみます。 そうすると，線分 ab に垂直な直線で点 a を通る直線と点 b を通る直線に囲まれた領域（下図の左の赤色領域に相当）にある点であれば， 点から直線 ab への垂線が最短距離になります。 また，点 c がこ
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な : 404 Blog Not Found
2012年01月13日08:00 カテゴリアルゴリズム百選Lightweight Languages algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な The C Programmming Lanugage K&R 言い出しっぺの法則。 404 Blog Not Found:algorithm - bucket sort - 比較しなければソートは相当速い これほど素晴らしいアルゴリズムなのに、なぜlibcやLL言語の組み込みとして用意されていないのでしょう? https://plus.google.com/103748274114027132441/posts/VmpVES1hFds - Shiro Kawai さんのコメント他のソートアルゴリズムのような汎用のライブラリになってないのは、目的によってチューニングポイントが違って、それらに
![algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な : 404 Blog Not Found](https://cdn-ak-scissors.b.st-hatena.com/image/square/da78a05937633f7a2b4b2219826151c370cd607b/height=288;version=1;width=512/https%3A%2F%2Fparts.blog.livedoor.jp%2Fimg%2Fusr%2Fcmn%2Fogp_image%2Flivedoor.png)
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
衝突判定編