Merci aux aimables participants de Habr d'avoir été invités à écrire des articles et à recevoir des commentaires à leur sujet.
Aujourd'hui, je voudrais souligner le sujet de la représentation des nombres à l'aide de la série Fibonacci et, bien sûr, écrire une API REST simple en utilisant l' algorithme Mongo DB en utilisant le langage Ruby , qui retournerait sa représentation pour un nombre donné N.
Partie 1: la représentation de Zeckendorff
Comme l'indique l' article de Wikipédia:
Le théorème de Zeckendorff stipule que tout nombre naturel peut être uniquement représenté comme la somme d' un ou plusieurs nombres de Fibonacci différents de sorte que cette représentation ne contienne pas deux nombres adjacents de la séquence de Fibonacci.
100 = 89 + 8 + 3.
Je pense que, comprenant ce que sont les nombres de Fibonacci, il ne sera pas difficile de comprendre de quoi il s'agit.
Objectifs à atteindre:
vitesse de travail
simplicité maximale du code
En tant que langage de programmation, j'utiliserai Ruby , pourquoi? Parce que Ruby est
Le meilleur ami du programmeur.
Tout d'abord, théoriquement, vous devez trouver un modèle par lequel l'algorithme sera écrit.
, (), , , .
:
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
( )
Comme vous pouvez le voir, le temps de fonctionnement même sur des nombres allant jusqu'à 10 ^ 9 est très positif.
Et la quantité totale de code en 17 lignes indique que les deux tâches ont été exécutées avec succès.
Un article sur l'intérêt, vous devez toujours avoir quelques problèmes avec les numéros de Fibonache dans votre manche, sinon quel genre de programmeur êtes-vous :-)