- プログラミングのお題スレ Part8©2ch.net
657 ：651[sage]：2016/08/24(水) 20:06:38.41 ID:emWUYHC0 - >>654の言うように展開できるぎりぎりの数を順に選んでます。
とりあえず、f(0)+f(1)+...+f(n)=sum(n) とした場合、
1〜sum(n)の整数はf(0)〜f(n)の部分和で表すことができる
例）フィボナッチ数列の最初の6つ[0,1,1,2,3,5]を使えば1〜12までの数を表せる
というのを前提に、与えられた数がsum(n)より大きくsum(n+1)以内なら
必ずf(n+1)が含まれるということを、残りの数が0になるまで再帰的に計算しています。
最初の前提は、数列を一辺とした正方形をつなげていくというあの形から
直感的になんとなく。1〜sum(n)がf(0)〜f(n)の数列の組み合わせで表せるなら
sum(n)>=f(n+1)（n>=1の場合）
なので1〜sum(n+1)もf(0)〜f(n+1)の数列の組み合わせで表せるということに
なるんじゃないのかなぁと。正直全く自信ないです。
自分が書いたコードは、求めたフィボナッチ数列を配列に保存していたけど
その必要全くなかったですね。 http://ideone.com/oUIvN8
|