平成26年春期、応用情報技術者試験の午後問3にて、フロイドの循環検出法のアルゴリズムに関する問題が出されました。
問題文に関してはあまりにも長いため、問題は 応用情報技術者試験.com で確認お願いします。
問題の中で、循環を追う手順をウサギとカメの歩みに例えています。
Python で実装してみたので、ここにメモしておきます。時間に余裕ができたら解説を追記したいです。
Python による実装
Python のテストフレームワークには標準にある unittest を使いました。
問題では (s, t) の**タプル (Pair)**を返すように誘導していますが、一つの関数で循環節の長さを計算したかったのでこちらでは若干変えています。
import unittest
def cycle_finding(n):
m, p = 1, 1 # m.. カメの計算の余り p.. ウサギの計算の余り
s, t = 0, 0 # s.. 循環節の先頭小数桁位置 t.. 循環節の末尾小数桁位置
# 余りが一致するまで
while True:
m = (m * 10) % n # カメが1歩進む
p = (((p * 10) % n) * 10) % n # ウサギが2歩進む
if m == p:
break
if p != 0:
# 循環節の先頭の検知
p = 1
s = 1
while m != p:
s += 1
m = (m * 10) % n
p = (p * 10) % n
# 循環節の末尾の検知
p = (p * 10) % n
t = s
while m != p:
t += 1
p = (p * 10) % n
if s == 0 and t == 0:
return 0
else:
return t - s + 1
class TestCycleFinding(unittest.TestCase):
def test_1st_decimal_place(self):
# n = 3 1 / 3 = 0.33333... -> 0.(3)
self.assertEqual(cycle_finding(3), 1)
def test_2nd_decimal_place(self):
# n = 6 1 / 6 = 0.16666... -> 0.1(6)
self.assertEqual(cycle_finding(6), 1)
def test_max_digits(self):
# n = 7 1 / 7 = 0.14285714285714... -> 0.(142857)
self.assertEqual(cycle_finding(7), 6)
def test_two_digit_number(self):
# n = 56 1 / 56 = 0.01785714285714285... -> 0.017(857142)
self.assertEqual(cycle_finding(56), 6)
if __name__ == '__main__':
unittest.main()
解答の続き
与えられた n に基づき，O記法で表した場合，関数 junkan のプログラムが必要とする記憶域の大きさは
オとなり，計算量はカとなる。
上で書いた Python のコードでは junkan ではなく cycle_finding という関数名に変更しています。
サイト元に解説がついていなかったので驚きつつも自分の解答として、
記憶域の大きさは m, p, s, t の4つの変数しか扱っていないのでΟ(1)
時間計算量は
このように，循環小数となる全ての n において，ウサギは循環部分の何巡目かで周回遅れのカメに必ず追い付き，両者の余りは一致する。
...
両者の余りが一致したら，図4に示すように，カメは引き続き，ウサギは最初に戻って今度は両者とも1歩ずつ進む。最初に両者の余りが一致したところ(〈9〉と《9》)の次の割り算の商が，循環節の先頭である。
...
循環節の先頭を検出した後，図5に示すように，ウサギだけが再びカメと余りが一致するところ(〈9〉と《15》)まで1歩ずつ進むことによって，循環節の末尾を検出する。
上記 3 ループが高々 Ο(n) であることから Ο(n) とわかります。
解説があっているか責任は持てません。今度過去問題集買ってきます。
さいごに
最初、C++ で書いていたのですが、今後 Python で書いたほうがよさそうと考えたので Python で書き直しました。