投稿を書いてフィードバックを受け取るよう招待されたHabrの親切な参加者に感謝します。
今日は、Fibonacciシリーズを使用して数値を表現するトピックに焦点を当て、もちろん、Ruby言語を使用してMongoDBアルゴリズムを使用して単純なRESTAPIを記述します。これにより、指定された数値Nの表現が返されます。
パート1：ゼッケンドルフ表現
ウィキペディアの記事が述べているように：
Zeckendorffの定理は、任意の自然数は1つまたは複数の 異なるフィボナッチ数の合計として一意に表すことができる ため、この表現にはフィボナッチシーケンスからの2つの隣接する数が含まれないと述べています。
100 = 89 + 8 +3。
フィボナッチの数が何であるかを理解すれば、この定理が何であるかを理解することは難しくないと思います。
達成すべき目標：
作業速度
コードを最大限に簡素化
プログラミング言語としてRubyを使用しますが、なぜですか？ので、Rubyがあります
プログラマーの親友。
まず、理論的には、アルゴリズムを作成するためのパターンを見つける必要があります。
, (), , , .
:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
34, (21) , N, , :-).
, : .
- : .
: N , , <= 0.
:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
ans = [34]
N = 51 - 34 = 17
F = 1 , 1 , 2 , 3 , 5 , 8 , 13.
ans = [34 , 13]
N = 17 - 13 = 4
F = 1 , 1 , 2 , 3.
ans = [34 , 13 , 3]
N = 4 - 3 = 1
F = 1
ans = [34 , 13 , 3, 1]
:
def le_fib(limit, fib)
theoretical = fib[fib.count - 1] + fib[fib.count - 2]
return fib.last if theoretical > limit
fib << theoretical
le_fib(limit, fib)
end
def main(target,result)
temporary = le_fib(target, [1,1])
result << temporary
return result if target - temporary <= 0
main(target - temporary, result)
end
pp main(gets.to_i,[])
le_fib - , , target. , , .
main - c, , .
, , , , , .
20 1000
( )
ご覧のとおり、10 ^ 9までの数値でも動作時間は非常にプラスです。
また、17行のコードの合計量は、両方のタスクが正常に完了したことを示しています。
興味についての記事、あなたはいつもあなたの袖の上のフィボナッシュ番号に関していくつかの問題を抱えている必要があります、さもなければあなたはどんな種類のプログラマーですか:-)