Panda Noir

JavaScript の限界を究めるブログです。

アルゴリズム

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

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

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

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

操車場アルゴリズム解説

(本記事はリライト記事です。元の記事は削除しました) 逆ポーランド記法は数式からカッコが消せるという魔法のような記法です。今回は中置記法の数式を逆ポーランド記法にする、操車場アルゴリズムについて解説します。 (逆ポーランド記法は「後置記法」とも…

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

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

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

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

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

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

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関連の記事漁りつつ適当にテストしたプログラム載せておきます。

任意精度演算とは?

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

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

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

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

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

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

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

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

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

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

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

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

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