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

Fibonacci en 2 vvariables

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

fibonacci en 2 varizbles

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

Fibonacci en 2 vairables

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

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

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

fubonacci 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 : 1566

Fibonacci en 2 variable

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

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

Si il y a 51 pommes et que vous en prenez 24, combien en avez-vous ?

Sujets similaires

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