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

fibonzcci 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
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 550

Fibonacci en 2 variales

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

Fibonacci en 2 variaables

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

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

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

fibonacco 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 : 1612

Fibonaci 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 : 306

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

Dans une course, vous doublez le 19ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
23-06-2009 Enigmes Mathématiques
P2T
Les 3 cercles par legeneral
24-09-2008 Enigmes Mathématiques
P2T
Patron triangulaire par Bogriga
20-12-2016 Enigmes Mathématiques
P2T
18-05-2011 Enigmes Mathématiques
02-11-2011 Enigmes Mathématiques
11-04-2011 Enigmes Mathématiques
P2T
42 mais pas plus... par scrablor
23-03-2010 Enigmes Mathématiques
P2T
10-09-2009 Enigmes Mathématiques
P2T
Phrase nombres premiers. par gilles355
30-08-2012 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