概要
分数の形で表された有理数から循環小数を算出するプログラムを書きます。
小数の循環部分を検出するに当たり、以下の2つのアルゴリズムをそれぞれ試します。
- リストを使って循環を検出する方法
- フロイドの循環検出法
実装にはScalaを用います。
説明
有理数とは？
実数のうち、整数、もしくは分数の形で表す事ができる数です。
循環小数とは？
小数のある位以下に同じ数字の列が無限に繰り返される無限小数の事です。
プログラムで循環小数を求めるには？
◆ リストを用いた方法 ◆
まずはごく簡単に、筆算で行う割り算をシミュレートして求めます。
小数以下の割り算を繰り返していき、同じ余りが2回現れたら、そこで循環したことになります。
■ アルゴリズムの理解
筆算での計算手続きを確認してみます。
例題：15/17の循環小数を求めよ。
この問題を解くために計算していくと、以下の経過を辿ります。
| 求める位 | 計算 | 得られた答え（途中） |
|---|---|---|
| 1の位 | 15 ÷ 17 = 0 余り...15 | 0 |
| 小数第一位 | 150 ÷ 17 = 8 余り...14 | 0.8 |
| 小数第二位 | 140 ÷ 17 = 8 余り...4 | 0.88 |
| 小数第三位 | 40 ÷ 17 = 2 余り...6 | 0.882 |
| ・・・ | ・・・ | ・・・ |
直前の計算で得られた余りの数を10倍し、これをもう一度除数で割るという計算手順が繰り返されている事が分かります。
この例では、割り算が続いていますが、もし余りが出なかったらそこで計算は終わりで、循環小数ではなかった事になります。
■ プログラムにしてみる
では、ソースコードに落としてみます。
・リストで循環を検出する
package cycleFindingAlgorithm
import scala.annotation.tailrec
/**
* リストを用いて、循環節の開始位置と循環節の長さを求める。
* Created by nakam on 2017/06/10.
*/
class ListAlgorithm extends CycleFindingAlgorithm {
override def algorithmName: String = "リストを用いた循環検出法"
/**
* 循環節の開始位置と循環節の長さを算出する
* @param dividend 割られる数
* @param divisor 割る数
* @return 循環節の開始位置と循環節の長さ
*/
override def execute(dividend: Int, divisor: Int): CycleFindingResult = {
getCycleFindingResult(Seq.empty[Int] :+ dividend % divisor,divisor)
}
/**
* 循環節の開始位置と循環節の長さを算出する
* @param remainderList 余りのリスト
* @param divisor 割る数
* @return 循環節の開始位置と循環節の長さ
*/
@tailrec
private def getCycleFindingResult(remainderList:Seq[Int], divisor:Int): CycleFindingResult ={
val nextRemainder = getNextRemainder(remainderList.last,divisor)
if(remainderList.contains(nextRemainder)){
val startIndex = remainderList.indexOf(nextRemainder)
new CycleFindingResult(startIndex,remainderList.size - startIndex)
} else {
getCycleFindingResult(remainderList :+ nextRemainder,divisor)
}
}
/**
* 次の余りの数を得る
* @param remainder 前の割り算の余り
* @param divisor 割る数
* @return 今回の割り算の余り
*/
private def getNextRemainder(remainder:Int, divisor: Int): Int ={
remainder * 10 % divisor
}
}
package cycleFindingAlgorithm
/**
* 循環検出法の結果
* @param startPointIndex 循環の開始位置
* @param length 循環節の長さ
*/
class CycleFindingResult(val startPointIndex:Int, val length:Int)
ListAlgorithmクラスのexecuteメソッドがこのプログラムのエントリポイントです。
executeメソッドは、有理数を分数の形で引数に取り、以下の結果を返します。
- 循環節の開始位置
- 循環節の長さ
循環節とは、循環小数のうち、数字が循環している部分の数列の事です。
executeメソッドが呼び出されると、プログラムは有理数を小数の形に直すために、有理数を表す分数の分子を分母で割ります。
余りが出ると、プログラムはその数をリストに保存した後、得られた余りの数を10倍し、再度有理数の分子で割ります。
この操作を、同じ余りの数が現れるまで繰り返します。
同じ余りが現れたかどうかは、リストに余りの数が保存されているので、比較する事で分かります。
同じ余りが現れたら、プログラムは循環節の開始位置と循環節の長さを算出して返します。
開始位置と循環節の長さは、以下の計算で求められます。
- 循環節の開始位置
重複した数が初めて剰余のリストに現れた位置が循環節の開始位置になります。
- 循環節の長さ
剰余のリストのうち、重複した2つの値の間の長さです。
重複した余りが発見された時点での剰余のリストの長さ - 開始位置の添え字
【プログラムの停止性】
もし、同じ余りがいつまでも現れなかったらプログラムが停止しないのではないか、と思うかもしれませんが、途中計算で出てくる余りの値は、「0 <= 余り < 除数」の間に収まるので、最大でも「除数 - 1」桁になるまでには、循環節が見つかります。
・循環小数を求める
上記で書いたのは、飽くまでも循環の開始と長さを求めるプログラムで、循環小数そのものを求めるプログラムは別に書く必要があります。
既に循環の開始と長さは分かっているので、今度は循環する桁まで小数を求めます。
import scala.annotation.tailrec
/**
* 割り算
* Created by nakam on 2017/06/04.
*/
object Division {
/**
* 割り算で小数点以下の値を求める。
* @param dividend 割られる数
* @param divisor 割る数
* @param quotientList 算出済みの商
* @param time 割り算の回数
* @return 算出した商のリスト
*/
@tailrec
def divided(dividend:Int, divisor:Int, quotientList:Seq[Int], time:Int): Seq[Int] ={
val result = divided(dividend, divisor)
val currentAnswer = quotientList :+ result.quotient
if(time == 1){
currentAnswer
} else {
divided(result.remainder * 10, divisor,currentAnswer,time - 1)
}
}
/**
* 割り算を行う。
* @param dividend 割られる数
* @param divisor 割る数
* @return 商と余り
*/
private def divided(dividend:Int, divisor:Int): DivisionResult ={
new DivisionResult(dividend / divisor,dividend % divisor)
}
}
/**
* 割り算の結果
* @param quotient 商
* @param remainder 余り
*/
class DivisionResult(val quotient:Int, val remainder:Int)
time引数を持つ方のdividedメソッドを呼び出すと、指定された回数分、小数を求めるための割り算を繰り返し行います。
返り値は、割り算の商をリストにしたものです。
・結果を表示する
上記のクラスを使用して得られた計算結果を表示するプログラムも書いておきます。
import scala.annotation.tailrec
/**
* Created by nakam on 2017/06/10.
*/
object Ui {
/**
* 得られた答えをコンソール出力する
* @param algorithmName 使用したアルゴリズムの名前
* @param dividend 割られる数
* @param divisor 割る数
* @param quotientList 循環小数を求める操作で得られた商のリスト
* @param startPointIndex 循環小数の開始位置
* @param length 循環節の長さ
*/
def show(algorithmName: String, dividend:Int, divisor:Int, quotientList:Seq[Int], startPointIndex:Int, length: Int) : Unit = {
println(algorithmName + "\n")
println("有理数")
println(dividend.toString + "/" + divisor.toString + "\n")
println("循環小数")
println(getAnswerStr1(new StringBuilder(), quotientList.head.toString.length + 1 + startPointIndex, length, 0))
println(getAnswerStr2(new StringBuilder(), quotientList).toString() + "\n")
printf("循環節の開始位置：小数第%d位, 循環節の長さ：%d%n", startPointIndex + 1, length)
}
/**
* 循環小数を求める
* @param answerStr 循環小数を表す文字列を逆順にした文字列
* @param quotientList 循環小数を求める操作で得られた商のリスト
* @return 循環小数を表す文字列
*/
@tailrec
def getAnswerStr2(answerStr: StringBuilder, quotientList: Seq[Int]): StringBuilder = {
if (quotientList.size == 1) {
answerStr ++= "."
}
answerStr ++= quotientList.last.toString
if (quotientList.size == 1) {
answerStr.reverse
} else {
getAnswerStr2(answerStr, quotientList.init)
}
}
/**
* 循環節の最初の数字と最後の数字の上に点を打つ
* @param str 循環小数の上に表示する文字列
* @param startPointIndex 循環節の開始位置
* @param length 循環節の長さ
* @param index 現在の位置
* @return 循環節の最初の数字と最後の数字の上に打つ点を含む文字列
*/
@tailrec
def getAnswerStr1(str: StringBuilder, startPointIndex: Int, length: Int, index: Int): StringBuilder = {
val s = if (startPointIndex == index || startPointIndex + length - 1 == index) {
"."
} else {
" "
}
if (startPointIndex + length == index) {
str ++= s
} else {
getAnswerStr1(str ++= s, startPointIndex, length, index + 1)
}
}
}
・テストする
テストを実行するプログラムを書いて、テストを実施してみましょう。
import cycleFindingAlgorithm.ListAlgorithm
/**
* リストを用いて、循環の検出を試みる。
* Created by nakam on 2017/06/11.
*/
object ListAlgorithmTest {
def main(args: Array[String]): Unit = {
val dividend = 9 // 割られる数
val divisor = 74 // 割る数
// リストを用いて、循環の検出を試みる。
new Test[ListAlgorithm].cycleFindingTest(dividend,divisor,new ListAlgorithm)
}
}
import cycleFindingAlgorithm.CycleFindingAlgorithm
/**
* 循環小数を求めるテスト
* Created by nakam on 2017/05/29.
*/
class Test[T <: CycleFindingAlgorithm] {
def cycleFindingTest(dividend:Int, divisor:Int, cycleFindingAlgorithm: T): Unit = {
// 循環の開始位置と循環節の長さを求める
val result = cycleFindingAlgorithm.execute(dividend, divisor)
// 循環小数そのものを求める
val answer = Division.divided(dividend, divisor, Seq.empty[Int], result.startPointIndex + 1 + result.length)
// 結果をコンソール出力する
Ui.show(cycleFindingAlgorithm.algorithmName,dividend,divisor,answer,result.startPointIndex,result.length)
}
}
では実行してみます。
リストを用いた循環検出法
有理数
9/74
循環小数
. .
0.1216
循環節の開始位置：小数第2位, 循環節の長さ：3
循環小数が算出できました。
循環小数の上に打たれている点は、ここからここまでの数値が循環しているという意味です。
◆ フロイドの循環検出法 ◆
次にフロイドの循環検出法を試してみます。
■ アルゴリズムの理解
これは一言で説明するのが難しいのですが、大まかに分けると、以下の3ステップで、循環節の開始位置と循環節の長さを求めます。
1. 循環節の異なる位置にある同じ要素を見つける。
循環節の中では、何度も繰り返して同じ数が「余り」として出てきます。
この数を以下のアルゴリズムを用いて検出します。
まず、余りが数列として並んでいるとします。
この数列に対して2つポインタを用意し、数列の開始位置から、2つのポインタをそれぞれ異なる速度で移動させていきます。
1つ目のポインタAは1つづつ進み、2つ目のポインタBは2つづつ進みます。
しばらく進めるとポインタBが循環節に入り、やがてポインタAも循環節に入ります。
ここから1ステップごとにポインタは1つづつ、循環節上の位置が近づいていきます。
循環節を円環と見なした場合、ポインタBがポインタAの「後ろから」近づいてくるためです。
そして最終的に同じ「余り」の数を差す事になります。
この「余り」の数が循環節のどの要素かは分からないものの、循環節上にある値である事は確かです。
なぜなら、余りの数が同じであるという事は、そこから値が循環していくからです。
有理数 \Bigl(\frac{344}{224}\Bigr)の例を以下に示します。
2. 循環節の開始位置を見つける。
さて、循環節上にある同じ値を発見できましたが、ポインタAとBが差す値が循環節のどの位置にある値かは分かりません。また、2つのポインタが差す位置が、循環節の1周分だけ離れているのか、もっと何周分も離れているのかも分かりません。ですから、まだ、循環節の開始位置と循環節の長さは両方分からない訳です。
しかし、次の事は分かります。
① ポインタAとポインタBの距離をmとおいたとき、mは循環節の長さの整数倍になっている。
また、次の事も分かります。
- ポインタAの現在位置は、数列の開始位置からmだけ離れている。
- 数列のうち、循環節に含まれていない部分をλとおくと、ポインタAの位置をλの長さだけ進めたとき、循環節の開始位置とポインタAの距離はmとなる。mは循環節の整数倍であるから、このときポインタAの差す値と開始位置の値は一致する。
循環節の開始位置を求めるために、ポインタCを数列の開始位置におき、ポインタAと一緒に1つづつ位置を進めていきます。ポインタCがλの中にいる間は、循環節の中にある余りの値が出現する事はありません。なぜなら、循環節に含まれる余りの値がλの中で見つかれば、そこから循環節が始まる事になり、λの定義に反します。ポインタCが初めて循環節の中にある余りの値を発見するのは、循環節の開始位置です。先ほど述べた理由により、ポインタCが循環節の開始位置に到達した時、ポインタAはまさにその値と同じ値を指しています。そのため、ポインタC=ポインタAが成り立った時に、ポインタCが差している位置が、循環節の開始位置であることになります。
- ポインタCを追加
- 循環節の開始位置を探す
3. 循環節の長さを求める。
ここまでくれば、あとは簡単です。
ポインタCを循環節の開始位置においたまま、ポインタDを循環節の開始位置におき、ひとつづつ進めます。次に循環節の開始位置と同じ値が見つかった時、ポインタCとポインタDの距離が循環節の長さとなります。
この問題を解決するための手続きは、「1. 循環節の中にある要素を見つける。」を循環節の開始位置から実行するやり方でも構いません。
もうすでに循環節の中にいることが分かっているため、最初にポインタAとポインタBが一致した時の長さが、循環節の長さです。
■ プログラムにしてみる
フロイドの循環検出法を実装してみましょう。
・フロイドの循環検出法
package cycleFindingAlgorithm
import scala.annotation.tailrec
/**
* フロイドの循環検出法
* Created by nakam on 2017/06/04.
*/
class FloydsCycleFindingAlgorithm extends CycleFindingAlgorithm {
override def algorithmName: String = "フロイドの循環検出法"
override def execute(dividend:Int,divisor:Int) :CycleFindingResult = {
val firstRemainder = new Remainder(dividend % divisor,0)
val pointerA = findSameRemainders(firstRemainder, firstRemainder, divisor)
val pointerC = getStartPoint(firstRemainder,pointerA,divisor)
val length = getLength(pointerC,getNextRemainder(pointerC,divisor),divisor)
new CycleFindingResult(pointerC.index,length)
}
/**
* 循環節の長さを求める
* @param pointerC 循環節の開始位置を指すポインタC
* @param pointerD 循環節の終了位置を探すポインタD
* @param divisor 割る数
* @return 循環節の長さ
*/
@tailrec
private def getLength(pointerC:Remainder, pointerD:Remainder, divisor:Int): Int = {
if(pointerC.number == pointerD.number){
pointerD.index - pointerC.index
} else {
getLength(pointerC, getNextRemainder(pointerD,divisor), divisor)
}
}
/**
* 循環節の開始位置を見つける
* @param pointerC ポインタC
* @param pointerA ポインタA
* @param divisor 割る数
* @return 循環節の開始位置
*/
@tailrec
private def getStartPoint(pointerC:Remainder, pointerA:Remainder,divisor:Int): Remainder = {
if(pointerC.number == pointerA.number) {
pointerC
} else {
getStartPoint(getNextRemainder(pointerC,divisor),getNextRemainder(pointerA,divisor),divisor)
}
}
/**
* 同じ余りを見つける
* @param pointerA ポインタA
* @param pointerB ポインタB
* @param divisor 割る数
* @return 同じ余りが見つかったときのポインタA
*/
@tailrec
private def findSameRemainders(pointerA:Remainder, pointerB:Remainder, divisor:Int): Remainder ={
val resultA = getNextRemainder(pointerA, divisor)
val resultB = getNextRemainder(pointerB, divisor,2)
if(resultA.number == resultB.number){
resultA
} else {
findSameRemainders(resultA, resultB, divisor)
}
}
/**
* 指定したオフセット分先の余りを得る
* @param remainder 現在の余り
* @param divisor 割る数
* @param offset オフセット
* @return 先にある余り
*/
@tailrec
private def getNextRemainder(remainder: Remainder, divisor:Int, offset:Int):Remainder ={
val newRemainder:Remainder = getNextRemainder(remainder, divisor)
if(offset == 1) {
newRemainder
} else {
getNextRemainder(newRemainder, divisor, offset - 1)
}
}
/**
* 次の余りを得る。
* @param remainder 現在の余り
* @param divisor 割る数
* @return 次の余り
*/
private def getNextRemainder(remainder: Remainder, divisor:Int): Remainder ={
new Remainder(remainder.number * 10 % divisor, remainder.index + 1)
}
}
/**
* 余り
* @param number 余り
* @param index 添え字
*/
private class Remainder(val number:Int, val index:Int)
・テストする
さきほどリストを使った循環検出法をテストしたときに使ったテストクラスを使って、テストを実施してみましょう。
import cycleFindingAlgorithm.{FloydsCycleFindingAlgorithm, ListAlgorithm}
/**
* フロイドの循環検出法をテストする。
* Created by nakam on 2017/06/10.
*/
object FloydsCycleFindingAlgorithmTest {
def main(args: Array[String]): Unit = {
val dividend = 11 // 割られる数
val divisor = 93 // 割る数
// フロイドの循環検出法をテストする。
new Test[FloydsCycleFindingAlgorithm].cycleFindingTest(dividend,divisor,new FloydsCycleFindingAlgorithm)
}
}
実行してみます。
フロイドの循環検出法
有理数
11/93
循環小数
. .
0.118279569892473
循環節の開始位置：小数第1位, 循環節の長さ：15
結果が得られました。
フロイドの循環検出法では剰余のリストを使っていないため、剰余のリストが使用するメモリの空間量に制約される事はありません。
参考
したいことだけする フロイドの循環検出アルゴリズム
未知の破片 循環小数の循環節を求める「ウサギとカメのアルゴリズム」
Wikipedia フロイドの循環検出法
応用情報技術者過去問題 平成26年春期 午後問3
環境
Scala 2.12
Github
フロイドの循環検出法を用いて有理数から循環小数を算出する。
↑リストを用いた方法も、上記のリポジトリに入っています。