最初に

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;
    }
}

オンライン実行