Obrigado aos simpáticos participantes da Habr, por serem convidados a escrever posts e receber feedback sobre eles.
Hoje eu gostaria de destacar o tópico de representação de números usando a série Fibonacci e, é claro, escrever uma API REST simples usando o algoritmo Mongo DB usando a linguagem Ruby , que retornaria sua representação para um determinado número N.
Parte 1: a representação Zeckendorff
Como os Wikipédia artigo estados :
O teorema de Zeckendorff afirma que qualquer número natural pode ser representado de forma única como a soma de um ou vários números de Fibonacci diferentes, de modo que essa representação não contenha dois números adjacentes da sequência de Fibonacci.
100 = 89 + 8 + 3.
Eu acho que, entendendo o que são os números de Fibonacci, não será difícil entender do que se trata esse teorema.
Metas a serem alcançadas:
velocidade de trabalho
simplicidade máxima de código
Vou usar Ruby como linguagem de programação , por quê? Porque Ruby é
O melhor amigo do programador.
Primeiro, teoricamente, você precisa encontrar um padrão pelo qual o algoritmo será escrito.
, (), , , .
:
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
( )
Como você pode ver, o tempo de operação mesmo em números até 10 ^ 9 é muito positivo.
E a quantidade total de código em 17 linhas indica que ambas as tarefas foram concluídas com êxito.
Um artigo sobre interesse, você sempre precisa ter alguns problemas com os números do Fibonache na manga, caso contrário, que tipo de programador você é :-)