最初に
C++で書かれた、ここでは、数列の周期をブレントのサイクルアルゴリズムを使って求めるコードです。サンプルは、数学の問題をプログラミングで解こう!「エース・ナンバー」問題解説の方法1:周期性を利用するから頂いている。
参照
ブレントの循環検出法 Wikipedia数学の問題をプログラミングで解こう!「エース・ナンバー」問題解説
C++コード
#include#include using namespace std; /** * ブレントのサイクルアルゴリズムを使用し、サイクル長と開始位置を探す。 * 繰り返し関係 X [n + 1] = f (x [n]) で f () に有限範囲がある場合、最終的に前に見た値が繰り返される * これが発生すると、後のすべての値は、最初の繰り返し値で始まるサイクルを形成し * そのサイクルの期間は、任意の長さの可能性がある * @param x0 [in] サイクルの最初の項目 * @param yielder [in] 反復実行によってサイクルを生成する関数デリゲート * @param lambda [out] サイクルの長さ * @param mu [out] 最初のサイクルを開始したアイテムの0から始まるインデックス * @see https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algorithm */ template void FindCycle(T x0, function yielder, T2 &lambda, T2 &mu) { T2 power; T tortoise, hare; power = lambda = 1; tortoise = x0; hare = yielder(x0); // サイクル長を求める while (tortoise != hare){ if (power == lambda) { tortoise = hare; power *= 2; lambda = 0; } hare = yielder(hare); lambda += 1; } // サイクル開始の0から始まるmuを求める mu = 0; tortoise = hare = x0; for (T2 times = 0; times < lambda; times++) hare = yielder(hare); while ( tortoise != hare) { tortoise = yielder(tortoise); hare = yielder(hare); mu += 1; } }