Gracias a los amables participantes de Habr por ser invitados a escribir publicaciones y recibir comentarios sobre ellas.
Hoy me gustaría destacar el tema de representar números usando la serie Fibonacci y, por supuesto, escribir una API REST simple usando el algoritmo Mongo DB usando el lenguaje Ruby , que devolvería su representación para un número dado N.
Parte 1: la representación de Zeckendorff
Como dice el artículo de Wikipedia:
El teorema de Zeckendorff establece que cualquier número natural se puede representar de forma única como la suma de uno o varios números de Fibonacci diferentes, de modo que esta representación no contiene dos números adyacentes de la secuencia de Fibonacci.
100 = 89 + 8 + 3.
Creo que, al comprender qué son los números de Fibonacci, no será difícil comprender de qué se trata este teorema.
Objetivos a alcanzar:
velocidad de trabajo
máxima simplicidad de código
Como lenguaje de programación usaré Ruby , ¿por qué? Porque Ruby es
El mejor amigo del programador.
Primero, teóricamente, necesitas encontrar un patrón mediante el cual se escribirá el algoritmo.
, (), , , .
:
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 puede ver, el tiempo de funcionamiento incluso en números hasta 10 ^ 9 es muy positivo.
Y la cantidad total de código en 17 líneas indica que ambas tareas se completaron con éxito.
Un artículo sobre el interés, siempre debes tener un par de problemas con los números de Fibonache bajo la manga, de lo contrario, ¿qué tipo de programador eres?