応用情報技術者 2014年 春期 午後 問03

　与えられた自然数 n について、1/n の小数表現を考える。1/n は、割り切れない場合、必ず循環小数となる。本問において、循環小数は、図1に示すように、繰り返し現れる数の並びである循環節の先頭から末尾までを括弧でくくる表記法で表す。 　1 を n で割る割り算で現れる余りは、1 から n−1 までの値に限られる。循環小数となる場合は、割り算を小数第1 位から行っていくと、どこかでそれまでに現れた余りと同じ値の余りが現れる。以降の割り算で得られる小数は、同じ数の並びが繰り返されることとなり、その数の並びが循環節となる。循環節の桁数は最大 n−1 である。

　1/56 の計算で商を1 桁ずつ求めていくと、余りの遷移は図2のようになる。ここでは、前のマスの中の値を10 倍して56 で割った余りが次のマスの中の値となる。余りとして48 が再度現れることから、1/56 では小数第4 位から第9 位までが循環節となることが分かる。

〔循環節を検出するアルゴリズム〕 　単純に余りを配列に記録して、既出の余りであるかどうか比較することによって循環節を検出する方法では、割り算の各桁で現れる余りの種類の最大である n−1 種類の余りを記録する必要がある。その配列の大きさは n に比例するととらえ、処理できる n の値は使用可能な記憶域の大きさによって制約される。そこで記憶域の制約を受けないで、“ウサギとカメ” に例えられるフロイドの循環検出法のアルゴリズムを用いる。この検出法は、循環するデータの先頭と末尾の位置を効率良く検出できることが証明されている。 　図2の余りを格納したマスから次のマスへ割り算を 1 桁進めることを、“ウサギとカメ” の歩みに例えて 1 歩進むという。 　このアルゴリズムでは、まず、図3に示すように、カメは〈1〉、〈2〉、…と一度に 1 歩ずつ、ウサギは《1》、《2》、…と一度に 2 歩ずつ進む。両者は同時に出発し、進んだマス（〈1〉と《1》、〈2〉と《2》、…）の余りを比較しながら、余りが一致するところ（〈6〉と《6》）まで進む。 　このように、循環小数となる全ての n について、ウサギは循環部分の何巡目かで周回遅れのカメに必ず追い付き、両者の余りは一致する。

　両者の余りが一致したら、図4に示すように、カメは引き続き、ウサギは最初に戻って今度は両者とも 1 歩ずつ進む。最初に両者の余りが一致したところ〈〈9〉と〈9〉〉の次の割り算の商が、循環節の先頭である。

　循環節の先頭を検出した後、図5に示すように、ウサギだけが再びカメと余りが一致するところ（〈9〉と〈15〉）まで1歩ずつ進むことによって、循環節の末尾を検出する。

　このアルゴリズムを使って循環節の先頭と末尾の位置を求める関数 junkan を図6に示す。図6で使用する変数と関数は、表1のとおりである。

　与えられた n に基づき、0 記法で表した場合、関数 junkan のプログラムが必要とする記憶域の大きさは オ とあり、計算量は カ となる。