アルゴリズム
久しぶりにこのシリーズ書きました。シリーズ一覧はこちらから。 A*アルゴリズムとは? 「今までにかかったコスト + これから先の推定されるコスト」が最小になるノードを選びながら探索していくアルゴリズムです。 最短経路探索を考えると分かりやすいです…
Uniform binary search - Wikipediaというページを発見しました。二分探索の改良版とのことです。
タイトルのとおりです。いろは順に並べ替える関数をつくりました。
第二回とありますが続かない可能性が高いです。
(本記事はリライト記事です。元の記事は削除しました) 第一回とありますが続かない可能性が高いです。
(本記事はリライト記事です。元の記事は削除しました) 今回は中置記法の数式を逆ポーランド記法にする、操車場アルゴリズムについて解説します。 (逆ポーランド記法は「後置記法」とも呼びます。本記事では以降「後置記法」と呼びます。)
構文解析はプログラマなら誰しも一度はやったことがあると思います。しかし、構文解析には独自の用語がたくさんあります。 そこで、初心者に向けて用語の解説をしたいと思います。「非終端記号って何?」「トップダウンとボトムアップはどう違うの?」と疑問に…
これも結構間違えた実装してました…
まあひねりの何もないコードですが、なぜか間違えたまま半年放置してしまっていたという笑えない事態になっていました…
約1ヶ月ぶりの更新です。いやー夏休み終わって部活再開してからめちゃくちゃ忙しくて大変です… 今回は、n本の線分の集合が与えられたとき、それらの交点をO(n log n)で求めるアルゴリズム、bentley-ottmannアルゴリズムを紹介します。実装はダラダラ進めてい…
離散フーリエ変換とは (以下では離散フーリエ変換をDFTと記述します) DFTとは、「ある関数f(x)から、関数F(t)を求める変換」です。 ただし、f(x)もF(t)も連続した関数ではありません。離散した関数なので、どちらかというと数列に近いです。 F(t)は以下の式…
アリ本の解説、私のように頭が弱い人には足りないことがあります。そこで、私がうんうん唸りつつ考察した、小学生でもわかりそうな解説を記そうと思います。 …少なくとも東大未満でも学生なら理解できるレベルではあります。たぶん 今回は2-2の「区間スケジ…
結局C++でも実装しました。 ブログネタないからハフマン符号記事で3つも書いたなんてことはありません
二分ヒープを用いることでハフマン符号を効率よく計算できるようにしました
え?C++を体得したんじゃなかったって? 知りませんね、そんなこと。私はC++なんて使わないでJavaScriptでコードを書きます。
配列をシャッフルし、それぞれのインデックスの要素が、元の配列の該当インデックス要素と異なるようにするアルゴリズムです。 A, B, Cを A, C, Bではなく、 C, A, Bのようにシャッフルします。 あ、前回の記事が400番目の記事でした。また記念イベントを忘…
作りました。七対子、国士以外の判定です(二つは簡単すぎますよね)。また、流し満貫ものぞきます。
世の中には辞書順という便利なものがあります。しかし、意外とオリジナルの順序を作りソートするプログラムは見かけません。 例えば麻雀では「東」「南」「西」「北」という4つの牌があります。これら4種類のみからなる配列を「東南西北」という順にソートす…
新型のテトリスを考えていた時に自然数の分割が必要となり考えてたら結構すんなり綺麗に解けたので紹介します。
http://www.cplusplus.com/reference/algorithm/lower_bound/ ここの仕様を満たすように実装していきます。 lower_bound()とupper_bound()をJavaScriptで実装してみたのリベンジ記事です。
追記: さすがに雑だったので書き直しました。 www.pandanoir.info lower_bound()とupper_bound()のJavaScriptによる実装がなかったので、ネットでlower bound関連の記事漁りつつ適当にテストしたプログラム載せておきます。
前回のプログラムを C++ で書きなおして任意精度演算を行ってみました。
自力で考え出した方法です。だいたい10回の施行で3.141592まで当てました どうでもいいですが7月22日は22/7が円周率に近似するため円周率の日というらしいです。
大きい数を扱うとき、必ずといっていいほど四捨五入されたりして値がずれてしまい、計算ができなくてこまったこと、ありますよね?
昔から実装されてる古典的なフィボナッチ数列を求める関数の意味をじっくり考えてみました。
ルートを求めるプログラムを組んでみました。
AtCoderという競技プログラミングの大会を月1で開いているサイトがあります。そこには過去の大会の問題もあるのでやってみました。言語は当然のようにJavaScriptです。
関数を関数の中から呼ぶと、どこからよばれたのかという記録がコールスタックというところにスタックされていきます。その限界についてしらべてみました。
第一回とありますが続かない可能性が高いです。
調べ物をしていたら、Fisher–Yatesアルゴリズムを見つけました。考え方がとてもシンプルでよかったので紹介します。