GrahamScan
点群の凸包を求める 問題 与えられた2次元の点群を包み込む多角形を求める問題です。下の□が与えられた点群で、多角形がそれを覆う凸包です。 手法 ここでの手法 セジビック著 「アルゴリズムC++」 を参考にしました。図も著書を引用させていただきます。ここでは、概略しか説明しません。詳細は、本を参照してください。最初に以下の点が与えられたとします。まず、一番下でかつ右にある基礎となる点を求めます。ここでは、B点になります。 セジビック著 「アルゴリズムC++」より B点から各点への角度を求め、この角度で点を整列します。 B,M,J,L,N,P,K,... となります。 セジビック著 「アルゴリズムC++」より BとMは凸包の点です。次にJを加えます。この時点では、J も凸包の点とします。しかし、次にLを加えますとBJLは凸でなくなります。そこで、Jを凸包から除外しLを加えます。こ
Spaghetti Source - 凸包 (Andrew's Monotone Chain)
解説 Andrew's Monotone Chain は凸包を求めるアルゴリズムで，Graham Scan における角度計算を ccw に置き換えてロバストにしたものである． 点列を x 座標でソートした後，下側凸包と上側凸包を別々に求め，併合して凸包を構成する．下側凸包を求めるときは点集合を左から右に見ていき，進行方向が左側であるような最も右よりの点を取っていく．上側凸包の場合は右から左に見ていく以外は全く同一である．進行方向に対して同一直線上にある場合は，最も近いものを取ることで凸包上にある点を取りこぼすことなく凸包に入れることができる． 使い方 vector<point> convex_hull(vector<point> ps) 点集合 ps に対してその凸包を求める．ps は三点以上あることを仮定する． 計算量 O(n log n)． ソースコード vector<point> c
パスカルの三角形 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "パスカルの三角形" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2019年1月) パスカルの三角形の最初の6段 パスカルの三角形（パスカルのさんかくけい、英: Pascal's triangle）は、二項展開における係数を三角形状に並べたものである。ブレーズ・パスカル（1623年 - 1662年）の名前がついているが、実際にはパスカルより何世紀も前の数学者たちも研究していた。 この三角形の作り方は単純なルールに基づいている。まず最上段に 1 を配置する[1]。それより下の段は両端には 1 を、それ以外の位置には右上の数と左上の数の和
シーザー暗号 - Wikipedia
シーザー暗号では、決まった文字数分のアルファベットをシフトさせて暗号化を行う。図の例では3文字分左にシフトさせて平文「E」を暗号文「B」に置換する。 シーザー暗号（シーザーあんごう、英語: Caesar cipher）は、暗号理論上、もっともシンプルで、広く知られた暗号のひとつである[1]。カエサル式暗号[2]、シフト暗号[3]とも呼ばれる。 シーザー暗号は単一換字式暗号の一種であり、平文の各文字を辞書順で3文字分シフトして（ずらして）暗号文とする暗号である[4]。古代ローマの軍事的指導者ガイウス・ユリウス・カエサル（英語読みでシーザー）が使用したことから、この名称がついた[3]。 文字のシフト数は固定であるが、3に限る必要はない。たとえば左に3文字分シフトさせる場合、「D」は「A」に置き換わり、同様に「E」は「B」に置換される。 シーザー暗号はヴィジュネル暗号などの部品として使用されるこ
中国の剰余定理 - Wikipedia
ガウスは『整数論』（1801年）において中国の剰余定理を明確に記述して証明した[1]。 中国の剰余定理（ちゅうごくのじょうよていり、英: Chinese remainder theorem）は、中国の算術書『孫子算経』に由来する整数の剰余に関する定理である。あるいは、それを一般化した可換環論における定理でもある。中国人の剰余定理（ちゅうごくじんのじょうよていり）、孫子の定理（そんしのていり、英: Sunzi's theorem）とも呼ばれる。 『孫子算経』には、「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題とその解法が書かれている。中国の剰余定理は、この問題を他の整数についても適用できるように一般化したものである。 3 - 5世紀頃成立したといわれている中国の算術書『孫子算経』には、以下のような問題とその解答が書かれている[2]。 今有物、不知其数。三・三数之、
Bal4u : C/UVa
本人が得意としているのはC言語（C++でも，C#でもありません）．数値計算・数論・ソート・検索・計算幾何学・符号・文字列照合等数多くのC言語用ライブラリがここに置いてあります． また，2004年末頃から，スペインにあるオンライン・プログラミング・コンテスト・サイト に参戦していた．参戦記や解答プログラムの一部もここに公開しています． 効率的に約数の個数を求めるアルゴリズムを考えているが、まだ四苦八苦している状態。つまり、1～500万までの整数について、それぞれの約数の数を一気に求めたい。 個々の整数なら、素因数分解して、因数の指数の積で約数の数が分かるのだが、1個1個やっているのでは、遅すぎて話にならない。 それよりも多少高速なプログラムは以下の通り。それでも数秒かかってしまう。 #define MAX 5000000 int c[MAX+10]; /* 約数の数を記録する */ void
オイラー路 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Eulerian path|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があ
エラトステネスの篩 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "エラトステネスの篩" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2019年6月) エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がついている。
C - で私も素数を数えてみた : 404 Blog Not Found
2010年07月26日18:30 カテゴリMath C - で私も素数を数えてみた 世間は夏休みだそうだし、連日の猛暑で体調も底だし、というわけで私も素数を数えてみた。 10兆までの素数のリストを作ってみませんか？ - 記者の眼：ITpro もしあなたがプログラマだったら、プログラムを書いて10兆までの素数のリストを作ってみてほしい。情報システムの開発に携わる人であれば、10兆までの素数のリストを出力するシステムの見積もりを考えてみてほしい。費用はどれくらいかかるか、納期はどれくらいか、あなたはどんな答を出すだろうか。仕様書はうまく書けるだろうか。 プライムナンバーズ David Wells / 伊知地宏監訳 / さかいなおみ訳 [原著:Prime Numbers: The Most Mysterious Figures In Math] といっても原田記者と同じように書いても芸がないので
C - で素数を数え直したら、範囲10億で10秒切ったお : 404 Blog Not Found
2010年07月28日01:30 カテゴリMath C - で素数を数え直したら、範囲10億で10秒切ったお というわけで数え直したら… 404 Blog Not Found:C - で私も素数を数えてみた はてなブックマーク - mohnoのブックマーク「Core i7 な iMac で、10億の範囲を検索するのに1プロセス300秒前後」←遅いってこと？ エラトステネスのふるいで、原田氏の記事でも10億なら2分（Core i7 920）、私の手元では20秒（Core 2 Duo E6850）だったんだけど。 10秒を切ってしまったので。 次にアルゴリズムであるが、いろいろいじってみた結果こうした。 まず p < 256 な小さな素数でエラトステネスのふるいにかけ 次にMiller-Rabin素数判定法を適用する これは「個々の64bit整数が素数かどうか」を判定するのには(素数表を引くこ
素数を求めるプログラム
・課題の定番 100以下の素数を全て表示するプログラムをつくってください。 printf("2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97\n"); というとこれでいいやとか思う人がいそうなので課題変更です。 10000以下の素数を求めてください。 これでも上のようにやる人がいたら尊敬します。 ・完成までの流れ まずは大まかなプログラムの流れを考えてみましょう。 for(i=1;i<=10000;i++) { if(iが素数) printf("%d ",i); } iが素数であるかを調べるにはどうしたらいいでしょうか。 素数の定義を考えforの中身を次のように置き換えます。 iの約数の個数を求める処理 if(iの約数の個数==2) printf("%d ",i); iの約数の数は以下のようにすれば
グーグルが構築した大規模システムの現実、そしてデザインパターン（4）～デザインパターン編
グーグルが「Evolution and Future Directions of Large-Scale Storage and Computation Systems at Google」（グーグルにおける、大規模ストレージとコンピュテーションの進化と将来の方向性）という講演を、6月に行われたACM（米国計算機学会）主催のクラウドコンピューティングのシンポジウム「ACM Symposium on Cloud Computing 2010」で行っています。 講演の内容を4つの記事（MapReduce編、BigTable編、教訓編、デザインパターン編）で紹介しています。この記事は教訓編の続き、デザインパターン編です。 大規模システムデザインの指針 よりよく使ってもらうためのインフラのデザインと開発方法を考えてみよう。 インフラに対する機能の要望についてさまざまなグループと話すと、多くのリクエ
グーグルが構築した大規模システムの現実、そしてデザインパターン（3）～教訓編
グーグルが「Evolution and Future Directions of Large-Scale Storage and Computation Systems at Google」（グーグルにおける、大規模ストレージとコンピュテーションの進化と将来の方向性）という講演を、6月に行われたACM（米国計算機学会）主催のクラウドコンピューティングのシンポジウム「ACM Symposium on Cloud Computing 2010」で行っています。 講演の内容を4つの記事（MapReduce編、BigTable編、教訓編、デザインパターン編）で紹介しています。この記事はBigTable編の続き、教訓編です。 大規模分散処理システムの構築から学んだこと ここからは、グーグルがたくさんのシステムを経験して学んだことと、それらのデザインパターンなどを紹介していきたい。 まず、大きく複雑な
グーグルが構築した大規模システムの現実、そしてデザインパターン（2）～BigTable編
グーグルが「Evolution and Future Directions of Large-Scale Storage and Computation Systems at Google」（グーグルにおける、大規模ストレージとコンピュテーションの進化と将来の方向性）という講演を、6月に行われたACM（米国計算機学会）主催のクラウドコンピューティングのシンポジウム「ACM Symposium on Cloud Computing 2010」で行っています。 講演の内容を4つの記事（MapReduce編、BigTable編、教訓編、デザインパターン編）で紹介しています。この記事はMapReduce編の続き、BigTable編です。 分散処理に対応するBigTable 次はBigTableの説明に移ろう。BigTableは、大規模分散の半構造化データストアシステムだ。 グーグルでは多くの構造的
グーグルが構築した大規模システムの現実、そしてデザインパターン（1）～MapReduce編
グーグルが「Evolution and Future Directions of Large-Scale Storage and Computation Systems at Google」（グーグルにおける、大規模ストレージとコンピュテーションの進化と将来の方向性）という講演を、6月に行われたACM（米国計算機学会）主催のクラウドコンピューティングのシンポジウム「ACM Symposium on Cloud Computing 2010」で行っています。 グーグルはどのようにして大規模分散システムを構築してきたのか、そして、そこからどのようなことを学んだのかが語られていますし、後半では大規模分散システムのデザインパターンという、非常に興味深いノウハウも公開している、非常に情報量の多い講演です。 その講演の内容を、全部で4つの記事、MapReduce編、BigTable編、教訓編、デザイン
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ベイジアンアルゴリズムは効くのか? - アメリカでがんばりましょう
Creating a BSP Tree
微分積分
符号とその性質
サービス終了のお知らせ