Animated Sorting Algorithms
Discussion These pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to: Show how each algorithm operates. Show that there is no best sorting algorithm. Show the advantages and disadvantages of each algorithm. Show that worse-case asymptotic behavior is not the deciding factor in choosing an algorithm. Show that the initial condition (inp
ALGORITHM NOTE
X×Y個のセルから成るグリッド上のスタート地点から出発し、全５種類のパチクリ（生物）を捕まえた状態でゴール地点まで行く最短コストを求める問題です。各パチクリはそれぞれ、火、氷、木、土、水の属性を持ち、火のパチクリは氷のパチクリを捕まえることができ、氷のパチクリは木のパチクリを捕まえることができ、といったように火→氷→木→土→水→火というような属性の関連があります。スタート地点で最初に持つパチクリを１つ選ぶことができます。グリッドのサイズx, y はそれぞれ2以上1000以下で、各属性のパチクリの数はそれぞれ0以上1000以下です（全体の数は5000以下）。 最初に１つのパチクリを選んだ後のパチクリを捕まえる順番は、上記属性の関連の順番になります。例えば最初に火の属性をもつパチクリを持っていれば、氷、木、土、水の属性をもつパチクリを順番に捕まえてゴールに行けばよいので、下図に示すDAG（Di
数独インデックス - SUDOKU Index
実行ボタンを押すと，それぞれのプログラムが実行され，約１５秒ほどで答えが戻ります 数独インデックスから解盤面へ 数独のIndexを入力 (0〜6670903752021072936959) 解盤面から数独インデックスへ 数独の盤面を入力（９×９の数字列；半角数＆改行） 概要 数独の解盤面は，大ざっぱにいうと， 約 60 垓個（6 の後ろに 0 が 21 個並ぶ）通りあることが知られています． 我々は， その解盤面一つ一つに番号付け（数独インデックス）を与えました． このページでは， 解盤面→数独インデックス，数独インデックス→解盤面の両方が， 約 10 秒程度で計算できます． 右のフォームから実行できるので， 試してみてください． 注釈： 「数独」はニコリの登録商標．一般名は Number Place です． 対象とするのは１〜９までの数を埋める通常の数独です． B. Felgenh
共立出版「アルゴリズム・サイエンスシリーズ」: ホットコーナー
ブログ(iiyu.asablo.jpの検索) ホットコーナー内の検索 でもASAHIネット(asahi-net.or.jp)全体の検索です。 検索したい言葉のあとに、空白で区切ってki4s-nkmrを入れるといいかも。 例 中村(show) ki4s-nkmr ウェブ全体の検索 ASAHIネット(http://www.asahi-net.or.jp)のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。 --- ゴールデンウィークの少し前に渋谷の大型書店ブックファーストに行く機会 があったので、コンピュータ関係の棚をぼっーと眺めていた。 この、「棚をみるでもなくぼーっとみる」のが、オンライン書店だとまだで きないリアル書店の楽しみ。 そのとき、見つけたのが、休刊したbit誌など我々コンピュータ業界では
Tinkertoys and tic-tac-toe, p. 120
indirectly kicks an "output duck," a bird-shaped construction. The output duck swings down from its perch so that its beak points at a number- which identifies the computer's next move in a game of tic~tac-toe. What precisely does the read head scan as it feels its way down the monolith? Nothing less than 48 rows of Tinkertoy "memory spindles" encoding all the critical combinations of X's and O's
Topcoder
Topcoder is a crowdsourcing marketplace that connects businesses with hard-to-find expertise. The Topcoder Community includes more than one million of the world’s top designers, developers, data scientists, and algorithmists. Global enterprises and startups alike use Topcoder to accelerate innovation, solve challenging problems, and tap into specialized skills on demand.
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
きまぐれ日記: ソートの平均要素移動距離
配列をソートする際に各要素の平均移動距離はどれくらいになるか問題が同僚の間で話題になった. 結論から言ってしまえば，サイズ n の配列の場合平均移動距離は n/3 になるらしい． サイズ n の場合, 最右の要素は [0 .. n-1] に等確率で移動するので，直感的に考えると n/2 のような気がする．しかし，真ん中の要素は両側に移動するので，その距離は小さくなる．平均移動距離は n/2 より小さい値になるはずだ. 頭で考えるより手を動かしたほうが楽なので，モンテカルロサンプリングしてみた. 配列をランダムにシャッフルし，ソート済みの配列と比較して各要素の平均移動距離を求める．これを 1000 回繰り返し平均値を計算する. #include <iostream> #include <vector> #include <cmath> #include <algorithm> static
OSはアルゴリズムではない | Okumura's Blog
……んだろうかという話が土曜日の研究会であって，ぼーっとして聞いていたが，Slashdotの Forget Math to Become a Great Computer Scientist? で紹介されているITWireの記事 Want to be a computer scientist? Forget maths に “An operating system is not supposed to terminate, nor does it yield a singular solution.” だからOSはアルゴリズムではない，コンピュータサイエンスの基本は数学やアルゴリズムではない，と主張する本 Computer Science Reconsidered: The Invocation Model of Process Expression（Amazon.comへのリンク）が紹介
David Baraff's Home Page
I have moved from Carnegie Mellon University to Pixar Animation Studios. My contact information is: David Baraff Pixar Animation Studios 1001 West Cutting Blvd. Richmond, CA 94804 deb@pixar.com Research Items List of my available online-papers. Pictures associated with my papers. Siggraph Course Notes Lectures notes and slides from the SIGGRAPH '97 course, Physically Based Modeling: Principles and
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)
第2回 形式言語とオートマトン---「文」のルールを知り，機械に解釈させる
前回はアルゴリズムを評価するための計算量理論について解説した。今回は，「形式言語」と「オートマトン」を通して，機械が「文」をどのように解釈しているのかについて考えてみたい。 人間の営みの中で自然に発生した日本語や英語などの言語を「自然言語」と呼ぶ。それに対して，特定の目的のために意図的に作られたプログラミング言語のような言語を「形式言語」と呼ぶ。 この形式言語で記述された文を受理する（解釈する）架空の機械を「オートマトン」と呼ぶ。形式言語やオートマトンは，現代のコンピュータ技術の基礎原理の1つであり，様々な場面で応用されている。今回は，このコンピュータにおける「言語」について考えていこう。 「置き換えルール」で定義 形式言語の文法は，どのように定義すればよいだろう。1950年代に米国の言語学者であるノーム・チョムスキーは，「○○とは△△である」という“置き換えルール”の羅列で形式言語の文法
Fonts - Apple Developer
APPLE INC. LICENSE AGREEMENT FOR THE APPLE SAN FRANCISCO FONT For iOS, OS X and tvOS application uses only PLEASE READ THIS SOFTWARE LICENSE AGREEMENT ("LICENSE") CAREFULLY BEFORE USING THE APPLE SAN FRANCISCO FONT (DEFINED BELOW). BY USING THE APPLE FONT, YOU ARE AGREEING TO BE BOUND BY THE TERMS OF THIS LICENSE. IF YOU ARE ACCESSING THE APPLE FONT ELECTRONICALLY, SIGNIFY YOUR AGREEMENT TO BE BOU
ベジェ曲線
新年のご挨拶 みなさま、明けましておめでとうございます。 今年もよろしくお願いいたします。 ベジェ曲線とは さて、当教室のコースに「Photoshop CS」、「Photoshop CS2」コースがあります。 この中で、なめらかな曲線を引くため、いわゆる「パス機能」を使う際に用いられているのが、今回の主題の「ベジェ曲線」です。 ベジェ曲線とは、フランスの工学者である「Pierre Bezier」氏の創案になるもので、2点間を結ぶ曲線の表示方法の一種です。 n次のベジェ曲線の定義は、フリー百科事典である「ウィキペディア」によれば、2点をr（0）とr（n）として、制御点をr（1）〜r（n-1）とすれば、 r＝ΣnＣi ti （1−t）n-i r（i） 、ここでi＝0〜nであり、パラメータ tは、0〜1を動きます。 なお、nＣiは、n！／（（n−i）！i！）を表し、rは、位置ベクトル
404 Blog Not Found:グラフィックに役立つ数学的事実
2007年06月20日10:30 カテゴリ翻訳/紹介Math グラフィックに役立つ数学的事実 del.icio.us経由。 Handy Mathematics Facts for Graphics 単なる翻訳ではなく、もう少し使いやすくしてみた。 定数 実際にJavaScriptに計算させています。 √2 = sqrt(2) = Φ = (sqrt(5) + 1)/2 = 黄金比の長い方。短い方は小文字のφをあてることが多い。φ = 1/Φ = Φ - 1 = √3 = sqrt(3) = e = exp(1) = π = 4 * atan2(1,1) = ファイゲンバウム定数 詳しくは Feigenbaum Constant -- from Wolfram MathWorld Feigenbaum constants - Wikipedia, the free encyclopedia
日曜プログラマー劇場～ブログ編～: ３次のベジェから２次のベジェ（B-Spline）に変換
FlashのSWF書き出しの覚書２ FlashのSWFでは３次のベジェが使えないため、表題のごとく ３次のベジェから２次のベジェ（B-Spline）に変換 する必要があります。 で、WEBを探したのですが正しい方法が見つからず、ひとまず適当な変換を大急ぎ（約１時間）で実装し、やれやれと思ってたところ。。。ふとSWFの仕様書をよく読んだら、変換の仕方について書いてありました （Ｔ＿Ｔ） 詳しくはこちらをご覧下さい（英語です） http://steve.hollasch.net/cgindex/curves/cbez-quadspline.html 大まかに説明すると、 １．3次のベジェC1の2本のコントロールの交点を2次のベジェのコントロールとして曲線C2を作る。 ２．C2が、元の曲線C1を十分に近似できているか評価する ３．近似できていない場合は、元のＣ１をさらに二つに分割して、
マイコンのテクニック アルゴリズム
マイコン系 プログラムのテクニック アルゴリズム 2000/1月再着工 現在工事中 チャタリング取り 割算を使わない整数の平方根の算出 その他関数近似 10進 １００進 割算 DDA ステップモータの回し方 MOD n の平均 プログラムの流れ Win95で斜め楕円の描画 楕円をベジェスプラインで近似する 楕円の周長 直線,円系 の アルゴリズム 今までニフテイとかに投稿した内容をまとめています。推考していないので ボロボロとミスがあるようです。 論理演算の利用 AND OR 演算を利用すると分岐無しに色々な計算が出来ます 分岐無しにすると処理時間が固定になり便利な事が多いですね 最近のCPUは分岐が少ない方が速い事も多いようです /************************************************************ 符号無し同士の加算をし、結果がオーバ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Amazon.co.jp: 思考する機械コンピュータ (サイエンス・マスターズ 15): ダニエルヒリス (著), Hillis,W.Daniel (原名), 彰,倉骨 (翻訳): 本
CG Notes: Converting Bezier Curves to Quadratic Splines