Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

アルゴリズム

アルゴリズム勉強会 第三回 A*探索

久しぶりにこのシリーズ書きました。シリーズ一覧はこちらから。 A*アルゴリズムとは? 「今までにかかったコスト + これから先の推定されるコスト」が最小になるノードを選びながら探索していくアルゴリズムです。 最短経路探索を考えると分かりやすいです…

Uniform Binary Search(一定二分探索)解説

Uniform binary search - Wikipediaというページを発見しました。二分探索の改良版とのことです。

配列をいろは順にソートするプログラム

タイトルのとおりです。いろは順に並べ替える関数をつくりました。

アルゴリズム勉強会 第二回 幅優先探索

第二回とありますが続かない可能性が高いです。

アルゴリズム勉強会 第一回 深さ優先探索

(本記事はリライト記事です。元の記事は削除しました) 第一回とありますが続かない可能性が高いです。

操車場アルゴリズム解説

(本記事はリライト記事です。元の記事は削除しました) 今回は中置記法の数式を逆ポーランド記法にする、操車場アルゴリズムについて解説します。 (逆ポーランド記法は「後置記法」とも呼びます。本記事では以降「後置記法」と呼びます。)

構文解析に出てくる用語たち

構文解析はプログラマなら誰しも一度はやったことがあると思います。しかし、構文解析には独自の用語がたくさんあります。 そこで、初心者に向けて用語の解説をしたいと思います。「非終端記号って何?」「トップダウンとボトムアップはどう違うの?」と疑問に…

直線と直線の交点を求めるプログラム

これも結構間違えた実装してました…

線分の上に点が載っているか判定する

まあひねりの何もないコードですが、なぜか間違えたまま半年放置してしまっていたという笑えない事態になっていました…

bentley-ottmannアルゴリズム

約1ヶ月ぶりの更新です。いやー夏休み終わって部活再開してからめちゃくちゃ忙しくて大変です… 今回は、n本の線分の集合が与えられたとき、それらの交点をO(n log n)で求めるアルゴリズム、bentley-ottmannアルゴリズムを紹介します。実装はダラダラ進めてい…

離散フーリエ変換の解説

離散フーリエ変換とは (以下では離散フーリエ変換をDFTと記述します) DFTとは、「ある関数f(x)から、関数F(t)を求める変換」です。 ただし、f(x)もF(t)も連続した関数ではありません。離散した関数なので、どちらかというと数列に近いです。 F(t)は以下の式…

アリ本の詳解 その1

アリ本の解説、私のように頭が弱い人には足りないことがあります。そこで、私がうんうん唸りつつ考察した、小学生でもわかりそうな解説を記そうと思います。 …少なくとも東大未満でも学生なら理解できるレベルではあります。たぶん 今回は2-2の「区間スケジ…

C++でハフマン符号を求めるプログラム

結局C++でも実装しました。 ブログネタないからハフマン符号記事で3つも書いたなんてことはありません

二分ヒープによるハフマン符号の効率化

二分ヒープを用いることでハフマン符号を効率よく計算できるようにしました

ハフマン符号をJavaScriptで実装した

え?C++を体得したんじゃなかったって? 知りませんね、そんなこと。私はC++なんて使わないでJavaScriptでコードを書きます。

配列をバラバラに入れ替えて元の配列と重複しないようにする

配列をシャッフルし、それぞれのインデックスの要素が、元の配列の該当インデックス要素と異なるようにするアルゴリズムです。 A, B, Cを A, C, Bではなく、 C, A, Bのようにシャッフルします。 あ、前回の記事が400番目の記事でした。また記念イベントを忘…

麻雀の役判定アルゴリズム

作りました。七対子、国士以外の判定です(二つは簡単すぎますよね)。また、流し満貫ものぞきます。

好きな順番で配列をソートする

世の中には辞書順という便利なものがあります。しかし、意外とオリジナルの順序を作りソートするプログラムは見かけません。 例えば麻雀では「東」「南」「西」「北」という4つの牌があります。これら4種類のみからなる配列を「東南西北」という順にソートす…

自然数の分割について考えてみた

新型のテトリスを考えていた時に自然数の分割が必要となり考えてたら結構すんなり綺麗に解けたので紹介します。

lower_boundとupper_boundをJavaScriptで実装してみた

http://www.cplusplus.com/reference/algorithm/lower_bound/ ここの仕様を満たすように実装していきます。 lower_bound()とupper_bound()をJavaScriptで実装してみたのリベンジ記事です。

lower_bound()とupper_bound()をJavaScriptで実装してみた

追記: さすがに雑だったので書き直しました。 www.pandanoir.info lower_bound()とupper_bound()のJavaScriptによる実装がなかったので、ネットでlower bound関連の記事漁りつつ適当にテストしたプログラム載せておきます。

( 続 ) 円周率を求める方法

前回のプログラムを C++ で書きなおして任意精度演算を行ってみました。

円周率を求める方法

自力で考え出した方法です。だいたい10回の施行で3.141592まで当てました どうでもいいですが7月22日は22/7が円周率に近似するため円周率の日というらしいです。

任意精度演算とは?

大きい数を扱うとき、必ずといっていいほど四捨五入されたりして値がずれてしまい、計算ができなくてこまったこと、ありますよね?

フィボナッチ数列を関数で求める

昔から実装されてる古典的なフィボナッチ数列を求める関数の意味をじっくり考えてみました。

ネイティブJavaScriptより高速に平方根を求めたかった

ルートを求めるプログラムを組んでみました。

AtCoderの過去問をやってみました。

AtCoderという競技プログラミングの大会を月1で開いているサイトがあります。そこには過去の大会の問題もあるのでやってみました。言語は当然のようにJavaScriptです。

JavaScriptにおける関数のスタックの限界を調べた

関数を関数の中から呼ぶと、どこからよばれたのかという記録がコールスタックというところにスタックされていきます。その限界についてしらべてみました。

アルゴリズムの勉強をしよう 第一回 深さ優先探索

第一回とありますが続かない可能性が高いです。

世界最速の配列シャッフルアルゴリズム、Fisher-Yatesアルゴリズム

調べ物をしていたら、Fisher–Yatesアルゴリズムを見つけました。考え方がとてもシンプルでよかったので紹介します。