複数の要素を大きさの順に並び替えるアルゴリズムの一つにバブルソートがあります。 ソートの手順は次のようなものです。 例えば、2,4、3、1という数字の並びを小さい順に並べるとき、 操作① 第1の数字2と第2の数字4とを比較して小さい順なので[…]

前回、循環節を求める簡単なプログラムを紹介しましたが、この方法では入力値nに対してn-1個のリストを作る必要がありました。 今回は、リストが不要な「ウサギとカメのアルゴリズム」(フロイドの循環検出法)を紹介します。 この方法は、2つの変数([…]

応用情報技術者の午後の試験で、循環小数の循環節を求めるのに「ウサギとカメのアルゴリズム」を使ったプログラミングの問題が出題された。 これが、ちょっと面白かったので分数と循環節についてまとめてみました。 まず、有理数は以下のように、ちょうど割[…]