フィボナッチ進数

フィボナッチ進数

締め切りが 2017/08/11 10:00 AM なので，その 1 分後に投稿されるように予約

【概要】
二進数の1010111を十進数で表現する場合、各桁に 1, 2, 4, 8, 16, 32, 64, ... を掛けたものの総和で求められます。
つまり、
1×64+0×32+1×16+0×8+1×4+1×2+1×1
なので、
1010111(二進数) = 87(十進数)
になります。

で。
この問題は「フィボナッチ進数」という表現に関するものです。

フィボナッチ進数の場合は、各桁にフィボナッチ数1, 1, 2, 3, 5, 8, 13, 21, ...を掛けたものの総和と定義します(最初の0は使いません)。

たとえば 1010111 は
1×13+0×8+1×5+0×3+1×2+1×1+1×1
なので、
1010111(フィボナッチ進数) = 22(十進数)
となります。

1010111の他に、10000001, 1100010, 1100001なども 22 のフィボナッチ進数表現になります。


で。
数値(十進数)を与えます。
その値のフィボナッチ進数表現のうち、
それを二進数だと思ったときに最も大きな値になるものと最も小さな値になるものを計算して下さい。



【入出力】
入力は
22
のようになっています。普通に十進数です。


出力は、
10000010,1010111
のような感じです。

入力値のフィボナッチ進数表現のうち、
それを二進数だと思ったときに最も大きな値になるものと最も小さな値になるものを、
コンマ区切りでならべて下さい。

【例】
入力
出力
22
10000010,1010111
27
10010010,1101101
34
100000000,10101011

【補足】
    •    不正な入力に対処する必要はありません。
    •    入力値は、1以上 百万以下です。
    •    出力の左端の桁は必ず 1 にしてください。
    •    使う数字は0と1だけです。
    •    「フィボナッチ進数」は、この問題のために作られた造語です。

========================================================

f = function(n) {
    makeString = function(bit) { # 最下位桁から並んでいる bit を逆順にして，1 つの文字列に繋ぎ，先頭の 0 を取り除く
        sub("^0+", "", paste(rev(bit), collapse="")) # ベクトル [0, 1, 0, 0, 0, 0, 0, 1] は "10000010" になる
    }
    mx = 30 # n = 1000000 までなので，30 桁で十分（fib[30] = 832040, fib[31] = 1346269)
    bit = integer(mx) # 1 ... 30 桁
    fib = integer(mx) # フィボナッチ数列 fib[1] ... fib[30] = 1, 1, 2, 3, 5, 8, 13, 21, ..., 832040
    fib[1] = fib[2] = 1
    for (i in 3:mx) fib[i] = fib[i - 2] + fib[i - 1]
    for (i in mx:1) { # 上位桁から順に決めてゆく
        if (n >= fib[i]) {
            bit[i] = 1
            n = n - fib[i]
        }
    } # n = 22 ならば，21+0+0+0+0+0+1+0, 最も左が 1 の位として 0, 1, 0, 0, 0, 0, 0, 1
    max = bit # これが，二進数として読んだときの最大値を表すビット列
    # 最小値は，左から順に見ていって，"0, 0, 1" というシークエンスがあれば，それを "1, 1, 0" に置き換える
    # ただし，最も左の 2 桁については，"0,1" なら "1, 0" に置き換える
    # これを繰り返して，置き換えが起こらなかったら完了
    # 0, 1, 0, 0, 0, 0, 0, 1
    # 1, 0, 0, 0, 0, 1, 1, 0
    # 1, 0, 0, 1, 1, 0, 1, 0
    # 1, 1, 1, 0, 1, 0, 1, 0 完了
    repeat {
        complete = TRUE
        for (i in 2:mx) {
            if (bit[i] == 1) { # …+0+0+21+… は …+8+13+0+… と同じ
                if (i == 2 && bit[1] == 0) {
                    bit[2] = 0
                    bit[1] = 1
                } else if (i >= 3 && all(bit[i-1:2] == 0)) {
                    bit[i] = 0
                    bit[i-1:2] = 1
                }
                if (bit[i] == 0) { # 1 回でも置き換えが起きたらまだ未完成（の可能性あり）
                    complete = FALSE
                }
            }
        }
        if (complete) { # 1 回も置き換えが起きなければ完成
            break
        }
    }
    min = bit
    cat(sprintf("%s,%s\n", makeString(max),makeString(min)))
}
# f(scan(file("stdin", "r")))

> f(1000000)
100010100000000000101000000000,10111110101010101111101010101
> f(999999)
100010100000000000100101010100,10111110101010101111011111111
> f(1)
10,1
> f(2)
100,11
> f(3)
1000,101
> f(832040)
100000000000000000000000000000,10101010101010101010101010101
> f(832039)
10101010101010101010101010100,1111111111111111111111111111
> f(129177)
10000010001000000010101000,1010111011101010111111101
> f(636488)
10010000000000101000010000100,1101010101011011101101011011
> f(325039)
1000000010000010001010100100,101010111010111011111111011
> f(77037)
1000000010010000100001010,101010111101011010110111
> f(825561)
10101010100000001000101010010,1111111110101011101111111101