Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 07-09-2017 09:54:23

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1592

Fibonacci en 2 avriables

Hello
Voici une petite énigme facile et sans prétention, mais assez intéressante quand même.
Précision: c'est une énigme sur l'informatique, pas sur les mathématiques.

La suite de Fibonacci est définie par U(n+2) = U(n+1) + U(n), U0= U1 = 1
La plupart du temps, on peut le coder avec 3 variables:
* initialisation: a = 1, b = 1
* puis
*** c <-- a+b
*** a <-- b
*** b <-- c
Dans cette écriture, on a besoin de c pour stocker la somme (U(n+2) dans la formule) avant de transférer b (U(n+1) dans la formule) vers a (U(n) dans la formule)

Mais, dans la plupart des langages (bon, on va dire les langages C-like, type C, C++, Java, Javascript, C#, etc...; merci d'oublier le BrainF**k, APL et autres joyeusetés), on peut se limiter à 2 variables seulement pour faire ce calcul.

Comment ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 07-09-2017 10:34:35

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 544

gibonacci en 2 variables

Bonjour scarta,
En python :

Code:

a,b = b,a+b

Tu vas sans doute dire qu'il y a une 3ème variable implicite…

Ajouté :

Code:

b = a+b
a = b-a

 #3 - 07-09-2017 13:40:12

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 784

Fibonacci en 2 variales

*** b <-- a+b
*** a <-- b-a

 #4 - 07-09-2017 14:50:58

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 253

fibpnacci en 2 variables

Bonjour,
Boucle{
    b <-- a + b
    a <-- b - a
}

Mais on peut le faire avec seulement une variable!

Soit f la fonction de couplage de cantor
f(p,q) = (p+q)(p+q+1)/2 + q
Soit f-1(n) = (g1(n) , g2(n) )
avec
g1(n) =  X(n) - ( n - T(n) )
g2(n) = n - T(n)
X(n) = [ 1 + V(1+8n) ]/2 - 1
T(n) = [ (E(X(n) + 1)(E(X(n) + 2) ]/2

(voir message #10 de http://www.prise2tete.fr/forum/viewtopic.php?id=13314 pour le détail)

alors on peut écrire la fonction:
Init a = 5 = f(1,1)
Boucle{
    a <-- f( g2(a), g1(a)+g2(a) )
}   
retourner g2(a)



Si on se limite à  addition/soustraction, on a:

Un+3 = Un+2 + Un+1 + Un
Boucle{
    c <-- a + b
    b <-- c - a - b
   a <-- c - a - b
}

On peut généraliser pour une récurrence d'ordre n avec n affectations
(variables u1, ..., un)
un = Somme(ui) (i de 1 à n)
un-1 = un - Somme(ui) (i de 1 à n-1)
un-2 = un - Somme(ui) (i de 1 à n-1)
...
u1 = un - Somme(ui) (i de 1 à n-1)
ce qui est optimal en terme d'affectations

 #5 - 07-09-2017 17:18:58

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1592

fibonaccu en 2 variables

Bon tout le monde a l'air de l'avoir, j'enlève le timer.
Donc, oui on peut faire b = a+b et a = b-a

Autre option, moins lisible:
b=a+(a=b)

@caduk: si tu veux te le faire en une variable, y'a aussi:
http://www.prise2tete.fr/forum/viewtopic.php?id=1118
Et là, je suis sur que tu peux même généraliser (c'est plus long mais ça doit être bien marrant)

 #6 - 07-09-2017 23:31:07

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 253

fibonacxi en 2 variables

Effectivement, c'est une manière intéressante de le faire, par contre, c'est moins généralisable...
ma méthode se généralise facilement, si on a n variables, il suffit de trouver une fonction de couplage de N dans N^n, ce qui n'est pas compliqué, et ça se généralise pour des problèmes très différent des suites récurrentes.
Dans ton cas, c'est plus compliqué car il faut pouvoir deviner combien de chiffres comporte chaque nombre, ce qui, dans d'autres problèmes différent de Fibonacci, est parfois impossible...

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

Sujets similaires

Sujet Date Forum
23-06-2009 Enigmes Mathématiques
14-06-2011 Enigmes Mathématiques
P2T
Addition par gabrielduflot
30-05-2009 Enigmes Mathématiques
P2T
Résultat commun par mamouaz
07-05-2015 Enigmes Mathématiques
P2T
Suites pérodiques par nodgim
04-01-2018 Enigmes Mathématiques
P2T
Gâteau 78 par Vasimolo
28-05-2014 Enigmes Mathématiques
P2T
EDF le retour par Vasimolo
06-11-2010 Enigmes Mathématiques
P2T
Optimisation level 5 par golgot59
04-12-2014 Enigmes Mathématiques
10-07-2009 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete