前回、循環節を求める簡単なプログラムを紹介しましたが、この方法では入力値nに対してn-1個のリストを作る必要がありました。
今回は、リストが不要な「ウサギとカメのアルゴリズム」（フロイドの循環検出法）を紹介します。
この方法は、2つの変数（ウサギとカメ）を使います。ウサギとカメは１をnで割った剰余1をスタート地点とし、同時にスタートします。ウサギは1つ飛ばしで移動します。カメは1ずつ移動します。速さの違うウサギとカメがトラック上を走るような感じで、いずれウサギはカメに追いつき、ある位置でならびます。
ここで、ウサギがうまくぶつからずにカメを追い抜いてしまうのではないかと思うかもしれませんが、その心配はありません。
もし、ウサギがカメを追い抜き、カメはi番目の位置、ウサギはi+1番目の位置にあるとすると、1つ前の状態ではウサギもカメもi-1番目の位置にいたことになります。
ウサギがカメに追いついた時点でウサギをスタート地点にワープさせ、今度はウサギも1ずつ移動させていきます。再びカメと並んだ位置がループの開始点となっています。次に、カメをループの開始点で待たせておき、ウサギを1個ずつ移動させます。再度、ウサギとカメが出会った時点がループの終了点となります。
なぜ、そうなっているかというと、、
ここで、出発点からループの開始点までの長さをK。ループの長さをLとします。
カメがスタート地点から出発して、ループの開始点に到達したとき、ウサギはカメの2倍、2K進んでいるはずです。
また、ウサギはループの開始点からはK進んでいます。
Kはループの長さLより大きいかもしれないので、ウサギのループ内の位置を剰余K’＝K mod Lと表します。
このとき、カメはウサギのK’ステップ後ろにいます。逆にみて、ウサギはカメのL-K’ステップ後ろにいます。
1回のステップで、ウサギとカメは1ずつ近づくので、ウサギはカメにL-K’ステップで追いつきます。
追いついた時点で、ウサギをスタート地点にワープさせます。
ここで、カメはループの開始点からL-K’だけ移動した位置にいます。
ウサギとカメを1ずつ移動させていくと、ウサギとカメはループの開始点で出会うことになります。
なぜなら、ウサギがループの開始点までKステップで動く間に、カメはループ内の位置L-K’の位置からKステップ移動します。ループ内ではKステップ移動するとK’だけ進むので、カメはループのL-K’+K'=L=0地点つまりループの開始点に戻っているはずです。
最後に、カメをループの開始点で待たせ、ウサギを1個ずつ進ませ再びカメと出合う位置がループの終了点となります。
このアルゴリズムをC言語プログラムで記述すると以下のようになります。
#include <stdio.h>
void junkan2(int n)
{
int m = 1; // カメ。剰余を保持する変数（初期値1）
int p = 1; // ウサギ。剰余を保持する変数（初期値1）
int s = 0; // 循環節の開始位置
int t = 0; // 循環節の終了位置
if (n > 0)
{
// ウサギとカメが出合う地点を探す
while (true)
{
m = (m * 10) % n;
p = (p * 10) % n;
p = (p * 10) % n;
if (m == p)break;
}
// pが非ゼロ。割り切れない場合
if (p != 0)
{
// ウサギをスタート地点に戻し、再びカメと出合うまでループを回す
p = 1;
s = 1;
while (m != p)
{
s++;
m = (m * 10) % n;
p = (p * 10) % n;
}
// カメを止めて、ウサギだけ1ずつ進める
p = (p * 10) % n;
t = s;
while (m != p)
{
t++;
p = (p * 10) % n;
}
}
}
printf("n = %d, s = %d, t = %d\n", n, s, t); // 結果を出力
}
int main()
{
junkan2(108);
return 0;
}
出力結果
n = 108, s = 3, t = 5
見事、前回のプログラムと比べてリストの確保が不必要になっています。
コメント