アルゴリズム

フィボナッチ数列の第k項をO(log n)で計算しようとしたけど難しかった話

目次 フィボナッチ数列 ビネの公式 計算誤差について 計算の工夫 最終的な計算時間 サンプルコード 1. フィボナッチ数列 フィボナッチ数列は、イタリアの数学者レオナルド・フィボナッチの名前をとって名付けられた数列です。 数列の決まりは、「ある項は、1…

フィボナッチ数列は再帰で実装するな

目次 この記事の目的 フィボナッチ数列 再帰で実装 ループで実装 計算時間の違い まとめ 1. この記事の目的 プログラミング経験者って、なんだかんだでフィボナッチ数列を実装したことがありますよね。 みなさんはどのように実装しましたか?覚えてらっしゃ…

【Java】2つの線分の交点を求める

目次 この記事の目的 x, y-平面上の線分を表すクラス 2つの線分の交点をもとめる方法 まとめ 1. この記事の目的 この記事では2つの線分の交点を求める方法を紹介します。 そのために必要になる、線分を表すクラスのコードも紹介します。 サンプルコードを上…

【Java】2つのベクトルがなす角度を求める

目次 この記事の目的 三点がなす角度の求め方 x,y-平面上の座標を表すクラス ベクトルの差、長さ、内積、外積 三点がなす外角を求める まとめ 1. この記事の目的 この記事では、xy-平面上の点の情報から角度を求める方法について紹介します。 特に、三点を…

【WebAssembly】JSとwasmでソートの速度を比較する

目次 この記事の目的 C++でソートを実装 JSでソートを実装 実行用のHTMLを準備する 実際に速度を比較する まとめ

C言語でクイックソート

クイックソートとは クイックソートとは、O(n*log(n)) ソートの一つ。比較ソートの中では最も高速なアルゴリズムの一つ。再帰を用いるアルゴリズムなので、停止条件(ベースケース)の実装を忘れずに。詳しくは クイックソート - Wikipedia を参照してくださ…