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 : 1577

Fibonacci en 2 varialbes

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 : 501

Fbionacci 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 : 734

Fibonacci en 2 vriables

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

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

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

finonacci 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 : 1577

Fibonacci en 2 variabless

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 : 241

Fibnacci 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 à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
23-06-2009 Enigmes Mathématiques
P2T
Pyramide codée ! par gilles355
07-09-2012 Enigmes Mathématiques
16-12-2011 Enigmes Mathématiques
P2T
6 fois le chiffre 6 par LASYLVE12
24-09-2011 Enigmes Mathématiques
P2T
27-08-2007 Enigmes Mathématiques
P2T
14-09-2010 Enigmes Mathématiques
P2T
Volume max parallelepipede par salehseghiri
25-08-2009 Enigmes Mathématiques
P2T
Le binaire par missreglisse
09-10-2012 Enigmes Mathématiques
P2T
Gâteau 67 par Vasimolo
17-01-2014 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