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

fubonacci en 2 variables

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
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 438

fibonaxci 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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 466

Fibonacci en 2 varriables

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

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

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

Fibonaccci 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 : 1484

Fibonacci en 2 varriables

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

Fibonacci n 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
12-02-2010 Enigmes Mathématiques
03-01-2008 Enigmes Mathématiques
P2T
Particularité de 2017 par Franky1103
04-01-2017 Enigmes Mathématiques
P2T
26-09-2012 Enigmes Mathématiques
21-06-2010 Enigmes Mathématiques
P2T
Soupe de portables par titoufred
23-10-2014 Enigmes Mathématiques
P2T
La machine par PRINCELEROI
27-10-2014 Enigmes Mathématiques
P2T
Un point, c'est tout ? par SaintPierre
02-01-2011 Enigmes Mathématiques

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