The Aggregate Magic Algorithms
There are lots of people and places that create and collect algorithms of all types (here are a few WWW sites). Unfortunately, in building systems hardware and software, we in The Aggregate often have found it necessary to do relatively obscure low-level things very efficiently. Many of the tricks we've devised or collected either require assembly language coding or are not entirely portable when
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
Suffix Arrayの簡単な説明
最終更新日: 2000-11-14 (公開日: 2000-11-14) Suffix Arrayは巨大なテキストを高速に検索するためのデータ構造 です。テキストのサフィックスを辞書順 (ABC順) に並べ、それに 対するポインタを配列として格納したものが Suffix Array です。 サフィックスとはテキスト中のある位置からテキスト末尾までの文 字列のことをいいます。テキストへの検索は Suffix Array を用い て 2分探索の要領で行います。 では、 Suffix Arrayの構築に移りましょう。ここでは ``abracadabra''というテキストに対して Suffix Array を作成す ることにします。 まず最初に、テキストに対してインデックスポイントを割り当てる 必要があります。インデックスポイントは、検索が行える位置を指 定したものです。この例では、どの位置からでも
イントロソート - Wikipedia
イントロソート（英: introsort）は、David Musser（英語版） が1997年に設計した、クイックソートとヒープソートを組み合わせたソートアルゴリズムである。 最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。時間計算量は最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。 イントロソートは、クイックソートやヒープソートと同様、比較ソートである。 クイックソートは、性能がピボット（データ列を分割する境界値）の選択に強く依存するという欠点があった。 例えばデータ列の先頭や最後尾をピボットに選ぶと、ほぼソートされた入力について最悪の性能を示す。 ニクラウス・ヴィルトはこれを避けるため、データ列の中央の要素をピボットに選ぶようにしたが、工夫をこらした並びに対しては
Visual C++の勉強部屋
理工系、特に電気系、の学生と技術者を対象としたVisual C++の解説を行います。Visual C++を始めたいが、よく分からないという人は、これを参考にしてください。ただし、初めてプログラムを学ぶ全くの初心者向けではありません。 本資料の一部のJava版が（株）翔泳社のウエブサイトＣｏｄｅＺｉｎｅにありますので、こちらもご利用ください（Java版とある場所をクリックして下さい）。Visual C++ 6.0版（現在は全部削除）が最初に公開され、そのJava版がCodeZineに寄稿され、その後に現在のVisual C++ 2005 Express Edition版が作成されています。 Java版は、すべてアプレットになっていますので、ブラウザから試してみることができます（Javaランタイム必要）。 Visual C++ 2008 Express Editionが無償でダウンロード
￣torito＿ パズル遊びへの招待・オンライン版
●パズル遊びへの招待・オンライン版● このコーナーでは、高木茂男氏の著書「パズル遊びへの招待」（発行：ＰＨＰ研究所・1994年）の内容に著者自身が加筆・修正を加えたものを、著者本人及び出版元の許諾により掲載しています。 一部情報が古くなったり、また現代では不適切と思われる表現もございますが、資料的価値を尊重し執筆当時のままとしております。 他サイトへの無断転載はご遠慮ください。
Mersenne Twister: A random number generator (since 1997/10)
English Version News: MTToolBox をGitHubで公開しました。(2013/10/04) TinyMTをリリースしました。 (2011/06/20) MTGPをリリースしました。(2009/11/17) SIMD-oriented Fast Mersenne Twister (SFMT) をリリースしました。 SFMTはオリジナルのMersenne Twisterより約二倍速く、 よりよい均等分布特性を持ち、零超過初期状態からの回復も高速です。 SFMTのページを見てください。 (2007/1/31) お願い：使う時にemailを一通下されば、 今後の改良のはげみになります。 どんなささいな問題点でも、見つけ次第御連絡下さい。 m-mat ＠ math.sci.hiroshima-u.ac.jp (このメールアドレスは スペースを抜いて手で打ち直してください)
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 こんなことやって意味あるのかどうか正直言って迷いました。プログラマはたいてい知っているような内容だし見る人もいないんじゃないかと思いましたが、これからプログラミングを始めてみようという方にとっては参考になるかもしれないし、何よりも自分にとって頭の中を整理できたりするので、これから定期的にやっていこうかと考えてます。 ところで、紹介する内容はほとんど過去に出版された書物関係から抜粋しています。一応下の方に参考文献として挙げておきますので興味を持たれた方は書店などで探してみてはいかがでしょうか？ ということで、まずはライン・ルーチン(画面に直線を描画する)についての紹介です。
Sphere Online Judge (SPOJ)
Become a true programming master Learn how to code and build efficient algorithms Are you passionate about coding? Try your luck in a brain challenge and join ADB Brain Wars contest! ADB Brain Wars is a contest organized for Polish programmers. Check the details at: adb-brain-wars.com Win great prizes and have a lot of fun! The elimination round begins on the 25th of March Register today! Seven da
『数学者の密室』
３種類以下の数字からなる２乗数 [F24] ('97/04/28, '00/10/03, '03/07/13, '04/05/17, '08/10/31 更新)
最短経路問題
(1) 区間ＡＢを通り抜ける経路は何通りあるか｡ (2) 区間ＡＢを通り抜けずに区間ＣＤを通り抜ける経路は何通りあるか。 (3) すべての経路から任意に1つ選んだとき、S地点からG地点に到達するのにかかる時間 の期待値を求めよ。 （解） （１） （２！/１！１！）×（５！/２！３！）＝２×１０＝２０（通り） （２） １×１×１＋２×１×１＋１×（４！/２！２！）×１＝１＋２＋６＝９（通り） （３） 区間ＡＢ、区間ＣＤをともに通り抜ける場合（所要時間 １６－１＋６＝２１分） ２×３＝６（通り） 区間ＡＢを通り抜けるが、区間ＣＤは通り抜けない場合（所要時間 １６－１＝１５分） ２×（１×３＋２×２）＝１４（通り） 区間ＣＤを通り抜けるが、区間ＡＢは通り抜けない場合（所要時間 １６＋６＝２２分） 上記の（１）の場合で、９通り 区間ＡＢ、区間ＣＤをともに通り抜けない場合（所要時間 １６分） ８！/
多倍長演算クラス - sodex @ ウィキ
bigint.h #ifndef _BIGINT_INCLUDE_CHECK #define _BIGINT_INCLUDE_CHECK #include <algorithm> #include <vector> #include <list> #include <iterator> #include <iostream> #include <iomanip> using namespace std; typedef unsigned long int LINT; template <typename L> class BIGINT { list<L> lint; int degree; // The num of this list bool sign; // if this BIGINT is greater than 0, sign is true. public: BIGINT<
アルゴリズムとデータ構造演習
本演習の目的は、プログラミング言語C及びSchemeの基礎を習得し、 それらの言語を通じて、講義「アルゴリズムとデータ構造」の理解を深めることにあります。 重要なお知らせ 特に重要な連絡事項はここに掲載されます。 課題について 課題には、A課題とB課題があります。（課題番号の末尾が種類を表します。） B課題が基礎的な課題で、A課題が発展的な課題となっています。 B課題を全問解くことが、単位取得の目安です。 C入門第1回（10月10日） C入門第2回（10月17日） C入門第3回（10月24日） C入門第4回（10月31日） C第1回（11月7日） C第2回（11月14日） C第3回（11月21日） C第4回（11月28日） C第5回（12月5日） Scheme第1回（12月12日） Scheme第2回（12月19日） Scheme第3回（1月9日） Scheme第4回（1月16日） C補講
いろいろな曲線
グラフ描画についての指針 グラフを調べる場合、次のことを念頭において計算を進めればよい。 （１） 曲線の存在範囲（Existence)や座標軸に対する対称性(Symmetry) （２） 座標軸との交点(Intersection)や曲線上の特殊な点の座標(Special point) （３） 関数の増減と極値(One) （４） 関数の凹凸と変曲点(Two) （５） 漸近線(Straight line) 私の高校時代、上記手順を覚えるために頭文字をつなぎ合わせて、 ＳＥＳＩＯＴＳ（セシオッツ） などという語呂合わせを考案したものだ。 例 曲線 Ｙ２＝Ｘ２(１－Ｘ２) のグラフを描いてみよう。 式の特徴から、曲線は、Ｘ軸に関して対称、Ｙ軸に関して対称、原点に関して対称である ので、計算する範囲を、Ｘ≧０、Ｙ≧０ としてよい。さらに、Ｙ２≧０ であるので、 ０≦Ｘ≦１ としてよい。このとき、与えら
SAT ソルバで数独を解く方法 - まめめも
数独は非常に SAT に変換しやすい問題です。全部参考文献 *1 に載っている内容ですが、なるべくわかりやすく説明してみます。ちょっと長いです。 SAT とは まず SAT をごく簡単に説明します。すでに SAT を知っている人はここは読み飛ばしてください。 命題論理式の形の一つに乗法標準形のというのがあります。変数か変数の否定 (リテラルと言います) を or だけでつないだ式 (節と言います) を and だけでつないだ論理式のことを言います。つまり以下みたいな形です。 ( a1 or !a2 or ... or an) and ( b1 or !b2 or ... or !bn) and ... and (!z1 or z2 or ... or !zn)SAT は「a1 や zn などの変数にうまく true か false を代入して、上の式全体を true にできるか」という問題
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Puzzle De Programming
white page
atso-net.jp
http://www.pref.fukushima.jp/pc-concours/2009/03/03_reidai.html
サービス終了のお知らせ