No Programming, No Life

プログラミング関連の話題や雑記

Re:分数を小数に展開, 水の移し替えパズル

分数を小数に展開

お題

整数a, bを受け取り,分数a/bを小数に展開した文字列を返す関数/メソッドを作成してください。結果が循環小数になる場合は,循環部を{}でくくってください。例:

a=3, b=8 → 0.375
a=3, b=14 → 0.2{142857}

与えられる整数a, bは次の条件を満たすものと仮定して構いません。 1 ≦ a < b ≦ 2147483647。なお2147483647は2^31-1です。

Server error
hissan.groovy
assert recurringDecimal(3, 8)     == '0.375'
assert recurringDecimal(3, 14)    == '0.2{142857}'
assert recurringDecimal(1, 3)     == '0.{3}'
assert recurringDecimal(1, 7)     == '0.{142857}'
assert recurringDecimal(3, 7)     == '0.{428571}'
assert recurringDecimal(269, 111) == '2.{423}'

/**
 * 循環小数に変換
 *     例) 3/14 → 0.2{142857}
 * @param numer 分子
 * @param denom 分母
 * @return 循環小数
 */
def recurringDecimal(int numer, int denom) {
    def rslt = '' << '' // バッファ
    def remainMap = [:] // 剰余:小数点第n位
    def frac = []       // 小数部

    // とりあえずqとrを求める
    int q = numer / denom // quotient(商)
    int r = numer % denom // remainder(剰余)

    // 整数部を投入
    rslt << q
    // 剰余が0なら終了
    if (r == 0) {
        return rslt.toString()
    }
    rslt << '.'
    // 剰余を保持しておく
    remainMap[r] = 0

    // 小数第100位まで繰り返し
    for(digit in 0..<100) {
        // numerをr * 10に置き換えて、q, rを求める
        numer = r * 10
        q = numer / denom
        r = numer % denom
        // 小数部分を追加
           frac << q
        // 剰余がremainMapに含まれている場合、循環部分を取り出して返却して終了
        if (remainMap.containsKey(r)) {
            def beforeRecurr = frac[0..<remainMap[r]]
            def recurr = frac[remainMap[r]..-1]
            rslt << beforeRecurr.join() << "{${recurr.join()}}"
            return rslt.toString()
        }
        // 剰余が0なら終了
        if (r == 0) {
            rslt << frac.join()
            return rslt.toString()
        }
        // 剰余を保持しておく
        remainMap[r] = digit + 1
    }

    // 既定の小数点桁数を超過
    rslt << frac.join() << '...'
    return rslt.toString()
}

水の移し替えパズル

お題

A, B, Cの容器があり,それぞれ水が4L, 2L, 10L入っている.ここで次の操作を繰り返す.

(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ,残りの容器に移す.」

たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる.くみ上げる前の容器には必ず水が入っているとする.

(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ.

可能ならA=827392L,B=65536L,C=122880Lのときも求めよ.

Server error
waterTranslocate.groovy
def complete = []                               // 完了リスト
def nonComplete = [ [step:0, list:[4, 2, 10]] ] // 未完了リスト
def processedSet = [] as HashSet                // 処理済みリスト

// 選択の組み合わせ
def selection = [0, 1, 2].with{
    [it, it].combinations()*.sort().unique().findAll{
        it.count(it[0]) != it.size()
    }
}

// メインタスク
while(nonComplete) {
//    println "未完了=[${nonComplete.size()}]件 処理済=[${processedSet.size()}]件"
    if (nonComplete) {
        def cont = nonComplete.head()
        nonComplete = nonComplete.tail()
        if(processedSet.add(cont.list)) {
            def trans = selection.collect{ translocate(cont, it) }.grep{ it }
            // 判定
            complete.addAll(trans.findAll{ it.list.count(0) == 2 })
            nonComplete.addAll(trans.findAll{
                return (complete && it.step >= complete*.step.min()) ? false : true
            })
        }
    }
}

// 結果出力
println complete*.step.min()

/** 差し替え */
def translocate(cont, select) {
    def result = cont.clone()
    result.list = cont.list.clone()
    // 移し替え可能な選択なら
    if (select.collect{ result.list[it] > 0 }.every{ it }) {
        for (i in 0..<result.list.size()) {
            if (select.contains(i))
                result.list[i]--
            else
                result.list[i] += 2
        }
        result.step++
        return result
    }
}

感想

なんだか、この二つ時間がかかった割りにソースが汚いという…。
水の移し替えパズルの方は、数式を使えば簡単にできるみたいですが、あえて組み合わせ走査をしてみました。*1

*1:疲れた。