最初に
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;
}
}
オンライン実行
関連