良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
「カルドセプトサーガ」にダイス目が偶数と奇数を繰り返すバグ | スラド
株式会社バンダイナムコゲームス発売のXbox360向けゲームソフト「カルドセプトサーガ」に「次のダイス目が偶数か奇数か推測できる」という致命的バグが見つかりました。ちなみに「カルドセプト」はモノポリーに侵略要素を加えたようなボードゲームで、このようなバグはゲームの根幹に関わるものです。 カルドセプトサーガ不具合情報によりますと、「最大ダイス目が偶数のマップでの非AI戦において、ダイスによって導かれる数値は奇数と偶数を交互に繰り返す」とのこと。Youtubeに検証動画があります。 また最大ダイス目が奇数のマップでのダイス目に関しても法則性らしきものが見つかっています。 双六やモノポリーでダイス目が偏っていれば、ゲームとして成立しなくなります。 どういう事情があればボードゲームのダイス目に偏りがあるまま発売されたりするのでしょうか。 ボードゲームとしての価値を自分で全否定しているようなものです
qsort - enbug diary (2007-02-10)
_ qsort ちょっと古いスレッドだが、 Slow glibc qsort, two versions that are much faster という話題があった。 要するに、glibcのqsortは遅くて、 qsortG やNetBSDのqsortは速いとか。 ほんまかなーと思って、ちょっと試してみた。 intの配列一千万個で、 ランダム、ソート済み、大体ソート済み、逆順を対象に、 glibcのqsort、qsortG、 STLのsort でまず実験。 glibcのqsortはメモリを確保できそうな大きさなら mergesortで、 そうでないと quicksort である。 qsortGはひらすらquicksort、 STLはSGI STL由来だから、 多分 introsort で、 quicksort + heapsort + insertion sort のはず。 ところが、q
Bal4u : C/UVa
本人が得意としているのはC言語（C++でも，C#でもありません）．数値計算・数論・ソート・検索・計算幾何学・符号・文字列照合等数多くのC言語用ライブラリがここに置いてあります． また，2004年末頃から，スペインにあるオンライン・プログラミング・コンテスト・サイト に参戦していた．参戦記や解答プログラムの一部もここに公開しています． 効率的に約数の個数を求めるアルゴリズムを考えているが、まだ四苦八苦している状態。つまり、1～500万までの整数について、それぞれの約数の数を一気に求めたい。 個々の整数なら、素因数分解して、因数の指数の積で約数の数が分かるのだが、1個1個やっているのでは、遅すぎて話にならない。 それよりも多少高速なプログラムは以下の通り。それでも数秒かかってしまう。 #define MAX 5000000 int c[MAX+10]; /* 約数の数を記録する */ void
Karetta|Cパズルプログラミング-再帰編
はじめに基本的過ぎること階乗fact1.c (2)fact2.c (1)fact3.c組合せcomb1.ccomb2.ccomb3.c四則演算１行入力の動作確認expr1.cトークン処理の準備expr2.cトークンがやっと動き出すexpr3.c (1)数式もどきexpr4.c優先順位を考えた式の処理 (1)expr5.c整理expr6.c８クイーンボードの準備queen1.cqueen2.cクイーンを左端に置いてみようqueen3.cqueen4.cクイーンを８個置いてみようqueen5.cqueen6.cqueen7.c効き筋のチェックqueen8.cqueen9.cqueen10.cデバッグをする羽目にqueen11.cqueen11.txtqueen12.cqueen12.txtqueen13.c動くようになったので整理整頓queen14.cqueen15.c対称移動の研究対象移動の
サルにもわかるＲＳＡ暗号: はじめに
So what kind of ciphers are actually used? Ciphers for authentication purposes include the password mentioned earlier. On the other hand, ciphers for the purpose of hiding information include the famous Caesar cipher and the cryptogram mentioned earlier. The details will be discussed later. This Cryptogram, can you see that the unit to be encrypted […]
ACM/ICPC国内予選突破の手引き
ACM/ICPCの2008年度の大会日程が公開されています。 国内予選は2008年7月4日，アジア地区予選会津大会は2008年10月25日～27日でホスト校は会津大学です。 参加登録締め切りは2008年6月20日です。 ここではACM/ICPC（ACM国際大学対抗プログラミングコンテスト: ACM International Collegiate Programming Contest）で 国内予選を突破するために必要な情報を載せています。 ACM/ICPC自体については2006年度の横浜大会のWebサイトなどを読んでください。 結局のところ，ACM/ICPCで良い成績を残すにはひたすら問題を解く練習をするしかありません。 ですが，出題される問題の多くはいくつかのカテゴリ，例えば探索問題やグラフ問題，あるいは幾何問題などに分類することができます。 つまり，「傾向と対策」が存在します。 本サ
CGファイル概説 目次
最終更新日：2001年5月1日 第1章へ webmaster@snap-tck.com Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)
データ圧縮法概説 目次
最終更新日：2001年7月2日 第1章へ webmaster@snap-tck.com Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)
私の備忘録
私の備忘録 何かと情報過多の時代、情報の取捨選択が難しいですね。本屋さんにいっても、新刊本 のあまりの多さに、閉口。探すのも大変だし、とても付き合いきれません。そこで、便利なの が図書館。新刊も確実に入ってくるし、しかも、丁寧に分類されていて、目的の本がすぐ見 つかります。しかも、ない本はリクエストすれば、公費で購入してもらえるので、ありがたい です。図書館は、まさしく我が家の大切な書庫。このコーナーは、そんな気分で作ってみま した。 何でもないことだけど、あれば便利というものを整理していきたいと思います。お手持ちの もので公開してもいいよ、というものがあれば、どしどし投稿してください。お待ちしています。 □数学・・・代数学分野（式と計算に関する話題です） □数学・・・幾何学分野（図形に関する話題です） □数学・・・解析学分野（計量に関する話題です） □数学・・・統計学分野（情報の整理に関
XOR交換アルゴリズム - Wikipedia
XOR交換(エックスオアこうかん、XOR swap)は、コンピュータ・プログラミングのアルゴリズムの一種であり、排他的論理和(XOR)を使用して一時変数を使わずに同じデータ型のふたつの変数の(異なる)値を交換する操作である。 このアルゴリズムはXORの対称差という性質を利用したものである。すなわち、任意のA, Bについて、(A XOR B) XOR B = A が成立することである。 標準的な交換アルゴリズムでは一時的な格納場所が必要となる。x と y の値を交換する場合、以下のようになる。 y の値を一時格納域にコピーする：temp ← y y に x の値を代入する：y ← x x に一時格納域の値を代入する：x ← temp あるいは、x と y が整数ならば、以下のようなアルゴリズムで交換することができる。 x := x + y y := x - y x := x - y ただし、
teaching
最終修正 2008/5/7 トップページへ 学科講義資料 講義資料(草苅担当分) 以下から、講義資料のファイルを入手できます。 各ファイルは、 ポストスクリプト(ps) PDF(pdf) パワーポイント(ppt) ワード(doc) エクセル(xls) テキスト(txt) 等の形式が混在しています。 科目別 線形代数学(1セメスタ) 基礎セミナー(1セメスタ) プログラミング演習(3セメスタ) 情報理論(4セメスタ) ソフトウェア工学(5セメスタ) 情報数理学(大学院) 各種勉強会 旧担当科目 年度別 平成20年度 前期 線形代数(1セメスタ) 基礎セミナー(1セメスタ) プログラミング演習(3セメスタ) ソフトウェア工学(5セメスタ) 情報数理学(M1セメスタ) 平成19年度 後期 情報理論(4セメスタ) 前期 線形代数(1セメスタ) 基礎セミ
数値解析入門I(広島工業大学)
Next: 目次 目次 索引 数値解析入門I 横田 壽 解答付きテキストは開成出版から1,680円で出ています 目次 数値解析の基礎 誤差 アルゴリズムと収束 １変数方程式の解 ２分法(bisection method) 定点法(fixed-point method) Newton法 漸化法のエラー解析 収束速度の改良 多項式の解とMuller法 補間法と多項式近似 Lagrangeの多項式と補間法 差分商(divided difference) Hermite補間 ３次スプライン補間法 パラメトリック曲線 数値微分と数値積分 数値微分(numerical differentiation) Richardsonの補外法 数値積分 合成数値積分 Romberg積分 適応型求積法(Adaptive Quadrature Method
ALGORITHM NOTE
X×Y個のセルから成るグリッド上のスタート地点から出発し、全５種類のパチクリ（生物）を捕まえた状態でゴール地点まで行く最短コストを求める問題です。各パチクリはそれぞれ、火、氷、木、土、水の属性を持ち、火のパチクリは氷のパチクリを捕まえることができ、氷のパチクリは木のパチクリを捕まえることができ、といったように火→氷→木→土→水→火というような属性の関連があります。スタート地点で最初に持つパチクリを１つ選ぶことができます。グリッドのサイズx, y はそれぞれ2以上1000以下で、各属性のパチクリの数はそれぞれ0以上1000以下です（全体の数は5000以下）。 最初に１つのパチクリを選んだ後のパチクリを捕まえる順番は、上記属性の関連の順番になります。例えば最初に火の属性をもつパチクリを持っていれば、氷、木、土、水の属性をもつパチクリを順番に捕まえてゴールに行けばよいので、下図に示すDAG（Di
JavaScriptで配列をシャッフル
配列をシャッフル、つまりランダムに要素の位置を入れ替えるというのを、sortメソッドを使ってやってみたのだけど、明らかにダメダメなものになってしまった。その後、あーでもないこーでもないと考えたのだけど、算数が得意すぎて頭が痛くなった。ということを某所でぼやいたらはてのくんがコードを見つけてくれた。どうやらFisher-Yatesという有名なアルゴリズムでやると良いらしい。 最初に書いたコードは、 var a = new Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); a.sort( function (a, b) { return Math.ceil(Math.random() * 3) - 2; } ); というもの。sortメソッドは、パラメータに与えられた関数が負の値・0・正の値を返すことによって要素の順序を決定するので、その関数がランダムに値を返せばランダ
趣味的にっき - 石取りゲーム
先日のRuby勉強会のお題だったのですが、時間がなくて演習中にできなかったので、今日改めてやってみました。というかid:nshttskさんの成果(id:nshttsk:20070428:1177787956)をリファクタリングしてみました(賢いコンピュータの実装はサボりました)。リファクタリングのポイントは以下です。 テストし易そうなインターフェースにする(Mockオブジェクトを使ってでテストできる部分を増やす)。 (上にもからめて)入出力部分をまとめる。MVCモデルぽくする。 うーむ、やっぱりかえって複雑になってしまったような気がします。それにしてもメソッド名のセンスが悪いなぁ。我ながら。 コメントありましたらお願いします。どしどしお願いします。 #!/usr/bin/env ruby module StoneTakingGame class Player def initialize(
最小完全ハッシュ関数の作り方
■順列型の最小完全ハッシュ関数 ０から４までの５個の数字が下のように並んでいる場合を例にして説明します。 ５個の数字の並べ方は５！通りありますので５！(=120)通りの並べ方の総てに対して0から119までの数値を一意に割り付けることが目的となります。 ３４１０２ ここでは左側から順に数字を見ていくことにします。最初の数字は３で残りの数字の個数は４個ですね。 この残れさた数字の個数分の総順列数は４！ですが、この数量を基数と言います。 つまり左端の数字が何であるかを完全に識別する為に最低限必要な基本となる重みのことです。 従って先ず最初の数字３に基数である４！を掛け算してはじき出します。 [３]４１０２ → ３＊４！ 次に左から２番目の数字ですが、ここから先はとても注意が必要です。 ２番目の数字は４で残りの数字の個数は３個です。残りの数字の個数が３個なので基数は３！になります。つまり基数が変化
地球にやさしいアルゴリズム---目次 - 地球にやさしいアルゴリズム：ITpro
アルゴリズムを構成している楽しい仕組みを紹介しながら，あなたに「おおっ」と言わせることが，本連載の最初の目的です。興味を持てたなら，アルゴリズムに関する文献や情報を抵抗なく読めるようになるはずです。アルゴリズムを使いこなしたり，作ることも無理なくできるようになるでしょう。 まずはいろいろなアルゴリズムの面白いところを見て，楽しんでみましょう 第1回 ナンプレを解いてみよう 第2回 パズルみたいに楽しいデータ圧縮 第3回 「場面」の移り変わりに注目する 第4回 できるだけ短いルートでゴールに到達する 第5回 隣の区画と異なる色で地図を四色に塗り分ける 第6回 上手なアルゴリズムの見つけ方 第7回 多対多の関係を賢く扱う 第8回 倉庫番を解くアルゴリズム 第9回 プロトコルを実現するアルゴリズム 第10回 麻雀の役を判定する 第11回 プログラム同士の対戦ゲーム 第12回 対戦ゲームの戦略を考
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Yamamoto's Laboratory 講義ノート(5E 計算機応用 2005年度)
M.Hiroi's Home Page / Lightweight Language