私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「フィボナッチ進数」（CodeIQ）を参照してください。
【概要】
二進数の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だけです。
フィボナッチ進数」は、この問題のために作られた造語です。
Rubyで解答しています。
#!/usr/bin/ruby
$Min = 0
def fib(n)
arr = [0,1]
begin
arr << arr[-2] + arr[-1]
end while arr.last < n
arr.pop if arr.last > n
return arr
end
def searchMax(f, n)
ret = []
(f.size-1).downto(1){|i|
if n-f[i] >= 0 then
ret << i
n -= f[i]
end
break if n == 0
}
return ret
end
def toMin(f, mx)
arr = mx.dup
ret = []
while !arr.empty?
v = arr.pop
if (v == 1) || (v == 0) then ret.unshift(v)
else
a = v-1
b = v-2
if ret.include?(a) || ret.include?(b) then ret.unshift(v)
else
arr.push(a)
arr.push(b)
end
end
end
return ret
end
def toNum(arr)
ret = 0
for a in arr
next if a == 0
ret |= (1 << (a-1))
end
return ret
end
def solve(n)
f = fib(n)
mx = searchMax(f, n)
mn = toMin(f, mx)
return toNum(mx), toNum(mn)
end
# main
while line = gets
line.strip!
next if line.empty?
mx, mn = solve(line.to_i)
printf("%b,%b\n", mx, mn)
end
それほど難しくないのですが、微妙に苦労しました。
最大のフィボナッチ数は簡単に求められます。問題は最小のフィボナッチ数です。
まず、使用できるフィボナッチ数は入力値以下の数に限られるので容易に列挙できます（入力値の最大がたかだか1,000,000なので数列の要素数は大した数ではありません）。
最大のフィボナッチ数は使用できる数列の要素に含まれる数のうち大きいものから順に選んで入力値から引き、残りの数にも同じことをすればできます。
例えば27の場合だと使用できるのは[1,1,2,3,5,8,13,21]なので、
・21≦27なので21を選択して、残りは6
・13>6、8と>6なので無視
・5≦6なので5を選択して、残りは1
・3>1、2>1なので無視
・1≦1なので選択して、残りは0
・1>1なので無視
無視した部分が0、選択した部分が1なので10010010というわけです。
最小のフィボナッチ進数の数は最大値から「an+2 = an+1 + an」という規則を利用して作ります。
まず、最大値の一番下の0ではない桁の数をその前の2つのフィボナッチ数に分けて新しいフィボナッチ数にします。この時、分割した数がすでに使われていたら分割できないのでその部分は飛ばして上の桁に進みます。新しい数ができたら同じように一番下の桁から繰り返して操作不能になるまでやると最小の数になります。
例えば27のフィボナッチ進数の数は10010010なので次のようになります。
これは[21, 5, 1]を使っているので次のようになります。
・一番下の1を[1,0]にし、10010001（0は使わないので）
・5を[3,2]にし、10001101（[21, 3, 2, 1]）
・2を[1,1]にしたら一番下の桁の1が重複なので無視
・3を[2,1]にしたら2が重複なので無視
・21を[13,8]にし、1101101（[13, 8, 3, 2, 1]）
・8を[5,3]にしたら3が重複なので無視
・13を[8,5]にしたら8が重複なので無視
・操作できなくなったので終了し1101101が最小値
という具合です。
入力値を数値にしてsolve()に渡し、結果を印字します。
問題を解きます。
fib()で使用できるフィボナッチ数の配列を求めます。
searchMax()で最大のフィボナッチ進数で使用するフィボナッチ数の要素番号（先頭の0を0番とする）の配列を求めます。
searchMax()の結果からtoMin()で最小のフィボナッチ進数で使用するフィボナッチ数の要素番号の配列を求めます。
それぞれのフィボナッチ進数で使用しているフィボナッチ数の要素番号から数値表現をtoNum()で求め、返却します。
n以下のフィボナッチ数列を返却します。
単純にループで処理しています。
先頭の0を含めているのはtoMin()がちょっと楽に実装できるため（と思った）です。
引数fは使用できるフィボナッチ数列、nは入力値です。
考え方に書いた通り、フィボナッチ数列の大きな方からn以下のものがあればnから引いて返却値にフィボナッチ数列の要素番号を追加し、nを減算する操作をnが0になるまで繰り返しています。
フィボナッチ数列の要素番号を利用するのはtoMin()を簡単に実装するためです。
引数fは使用できるフィボナッチ数列、mxは最大のフィボナッチ進数で使用するフィボナッチ数の要素番号の配列です。
考え方に書いた通りの実装ですが、要素番号を使用しているので分割処理が簡単で、単にv番目をv-1番目とv-2番目にすれば良いだけです。
35〜42行目のelseの処理が考え方に書いた処理で34行目は0番目の要素0と1番目の要素1のための処理です。この2つは初期値として定義されていて分割できないのでそのまま結果に移動させる必要があるので別扱いになります。
私の実装の操作は次のようになっています。
配列arrはmx（最大値）のコピーで、retは結果（最小値）になる予定のものです。
分割した場合はarrに戻し、分割できなかった時はretに移動することで常に一番下の桁を処理するようにしています。
入力値27、要素番号[2,5,8]の場合、次のようになります。
・2を取り出し要素番号[0,1]に分割します。分割したのでarr=[0,1,5,8]、ret=[]になります。
・0を取り出し、要素番号0なのでretに移動します。arr=[1,5,8]、ret=[0]になります。
・1を取り出し、要素番号1なのでretに移動します。arr=[5,8]、ret=[0,1]になります。
・5を取り出し、要素番号[3,4]に分割し、arrに戻します。arr=[3,4,8]、ret=[0,1]になります。
・3を取り出し、要素番号[1,2]に分割します。1がretにあるので分割不能ということになり、3をretに追加します。arr=[4,8]、ret=[0,1,3]になります。
・4を取り出し、要素番号[2,3]に分割します。3がretにあるので分割不能ということになり、4をretに追加します。arr=[8]、ret=[0,1,3,4]になります。
・8を取り出し、要素番号[6,7]に分割し、arrに戻します。。arr=[6,7]、ret=[0,1,3]になります。
・6を取り出し、要素番号[4,5]に分割します。4がretにあるので分割不能ということになり、6をretに追加します。arr=[7]、ret=[0,1,3,4,6]になります。
・7を取り出し、要素番号[5,6]に分割します。6がretにあるので分割不能ということになり、7をretに追加します。arr=[]、ret=[0,1,3,4,6,7]になります。
・arrが空になって操作できなくなったので終了します。
この様に要素番号を使うことで単純な処理にできます。
arrはフィボナッチ数列の要素番号の配列でこれを数値表現にします。
ビット演算でarrの要素番号-1のビットを1にすることで処理しています。
最初問題を見たとき、使えるフィボナッチ数列を用意して（これは回答と同じ）、再帰で簡単に列挙できるからメモ化でもすれば良いだろうと思ってやりました。そうしたらうまくメモ化できないわけです。小さい数を全部調べてから大きな数にならないので漏れが出るわけです。
まぁ、最大と最小だけだから見つかったところで打ち切れば良いわけです（最小はフィボナッチ数列を昇順に扱ってなるべく数を使う再帰を優先、最大は数列を降順に扱ってなるべく数を使う再帰を優先、でできる）が、ローカルで実行して見たら大きな数だと全然間に合わない。
この段にに至ってメモ化再帰とか動的計画法じゃダメということに気づきました。
それで回答の方法に至るわけです。
結局、回答を含めて3パターン（再帰で列挙、再帰で最大と最小だけを探す、解答）のコードを書くことになってしまいました。