IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

probleme autour un algo.


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre du Club
    Inscrit en
    Octobre 2007
    Messages
    6
    Détails du profil
    Informations forums :
    Inscription : Octobre 2007
    Messages : 6
    Par défaut probleme autour un algo.
    bonjour ,
    j'ai probleme avec cette suite U1=0 , U2=1 et Un= 3*Un-1 + 2*Un-2 (n>=3)
    je veux écrire un algo qui demande à l'utilisateur de saisir un nombre n et calcule le néme terme de la suite de Fibonacci définie par la suite précéfente
    malheureusement je n'est pas trouvé une maniére pour écrire cet algo .

  2. #2
    Membre éclairé
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Par défaut
    Citation Envoyé par le marocain Voir le message
    bonjour ,
    j'ai probleme avec cette suite U1=0 , U2=1 et Un= 3*Un-1 + 2*Un-2 (n>=3)
    je veux écrire un algo qui demande à l'utilisateur de saisir un nombre n et calcule le néme terme de la suite de Fibonacci définie par la suite précéfente
    malheureusement je n'est pas trouvé une maniére pour écrire cet algo .
    Bonsoir,

    tu as pensé à la récursivité?

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    suite_fibo(n)
     
    Begin
     
      si (n = 0) ou (n = 1) alors 
    résultat =1
     
    sinon
     
    résultat= suite_fibo(n-1) + suite_fibo(n-2)
     
    end
    mais dès que n devient grand, cette solution devient très couteuse en temps.

  3. #3
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    Citation Envoyé par acacia Voir le message
    Bonsoir,

    tu as pensé à la récursivité?

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    suite_fibo(n)
     
    Begin
     
      si (n = 0) ou (n = 1) alors 
    résultat =1
     
    sinon
     
    résultat= suite_fibo(n-1) + suite_fibo(n-2)
     
    end
    mais dès que n devient grand, cette solution devient très couteuse en temps.
    Je dirais même que cette solution n'est utilisable que pour les n extrèmement petit, la complexité étant exponentielle alors que le problème est en O(log n) en réalité.
    Mais il est déjà extrêmement simple d'en revenir à une complexité linéaire, que ce soit en récursif ou en impératif.
    Par exemple avec une récursion terminale :
    Code Haskell : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    fib_auxiliaire 1 u u' = u'
    fib_auxiliaire n u u' = fib_auxiliaire (n-1) (3*u+2*u') u
     
    fib n = fib_auxiliaire n 1 0

    --
    Jedaï

  4. #4
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par le marocain Voir le message
    bonjour ,
    j'ai probleme avec cette suite U1=0 , U2=1 et Un= 3*Un-1 + 2*Un-2 (n>=3)
    je veux écrire un algo qui demande à l'utilisateur de saisir un nombre n et calcule le néme terme de la suite de Fibonacci définie par la suite précéfente
    malheureusement je n'est pas trouvé une maniére pour écrire cet algo .
    Regarde les méthode de calcul de la suite de fibonnacci sur wikipedia et inspire-t-en. En gros il y a trois méthode.

    La mauvaise : la récurcivité qui a pour complexité la suite de Fibo justement (soit une complexité exponentielle).

    Il y a ensuite la méthode linéaire, qui a deux sous méthodes.
    Celle que plein de gens pratiquent qui consiste à remplir un tableau.
    Celle un peu plus maline (car constante en utilisation mémoire) qui consiste à passer du couple (u_n, u_n+1) au couple (u_n+1, u_n+2).

    Et enfin la méthode logarithmique qui consiste à remarquer que dans la méthode précédante, le passage d'un couple au suivant est une multiplication matricielle, et que l'on peut faire une exponentiation rapide.

    Have fun

Discussions similaires

  1. [PUBLICATION] Problème autour animation Flash !
    Par delavega dans le forum Intégration
    Réponses: 6
    Dernier message: 24/04/2006, 13h20
  2. Réponses: 24
    Dernier message: 27/09/2005, 21h16
  3. [Conception][Algo] Pb resolution d'un probleme au nivo algo
    Par cmoa59 dans le forum Général Java
    Réponses: 3
    Dernier message: 07/07/2005, 12h05
  4. [algo]probleme de variables hotes ds un insert
    Par omega dans le forum Langage SQL
    Réponses: 2
    Dernier message: 16/03/2004, 09h03

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo