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 :

x² et puissance de x par récurrence


Sujet :

Algorithmes et structures de données

  1. #1
    Inactif  
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    123
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2002
    Messages : 123
    Points : 130
    Points
    130
    Par défaut x² et puissance de x par récurrence
    Bonjour,
    j'aimerais connaitre et retrouver la formule de x² par récurrence;
    du style u(n+1)=f(un)

    Et à terme, une formule pour toutes les puissances de x.
    merci
    under construction...

  2. #2
    Membre régulier
    Inscrit en
    Août 2002
    Messages
    132
    Détails du profil
    Informations forums :
    Inscription : Août 2002
    Messages : 132
    Points : 102
    Points
    102
    Par défaut
    J'ai pas très bien compris... Tu veux une formule par récurrence qui donne : , c'est ça???

    Tu ne veux alors retrouver x² que pour les entiers, j'imagine...

    Dans ta formule de récurrence, tu ne veux pas écrire n du tout ou alors
    on peux avoir du n linéaire? Parce que si on peut alors voilà ta
    formule :
    on sait que : Donc :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    u(n+1) = u(n) + 2*n + 1
    A mon avis c'est pas ça que tu veux, mais qui sait???

    Bon courage!

  3. #3
    Inactif  
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    123
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2002
    Messages : 123
    Points : 130
    Points
    130
    Par défaut si si
    Citation Envoyé par poppels
    A mon avis c'est pas ça que tu veux, mais qui sait???
    si si c'est ce que je veux
    à une exception près, sans le '2n + 1'

    je crois me souvenir qu'il faut soustraire les u(n+1) pour enlever le n.
    under construction...

  4. #4
    Membre régulier
    Inscrit en
    Août 2002
    Messages
    132
    Détails du profil
    Informations forums :
    Inscription : Août 2002
    Messages : 132
    Points : 102
    Points
    102
    Par défaut
    Ok...

    Alors :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    (n+1)² + (n-1)² = n²+2n+1  +  n²-2n+1
    Ou encore :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    u(n+1)+u(n-1) = 2*u(n)+2
    Pour conclure (mais c'est une récurrence forte, c'est-à-dire on remonte de 2 crans) :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    u(n+1) = 2* u(n) + 2 - u(n-1)
    Je fais quand même un petit test sous excel avant de poster...............
    ......................................................................................................
    .......................................................................................................
    ........................................................................................................
    ................

    OK Ca marche... (mais j'en étais sur, hein!!!)

    Salut!

  5. #5
    Inactif  
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    123
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2002
    Messages : 123
    Points : 130
    Points
    130
    Par défaut
    Citation Envoyé par poppels
    u(n+1) = 2* u(n) + 2 - u(n-1)
    Super !
    et comment faire pour exprimer les relations de récurrences pour les puissances de 3,4,5,.... ?
    under construction...

  6. #6
    Membre régulier
    Inscrit en
    Août 2002
    Messages
    132
    Détails du profil
    Informations forums :
    Inscription : Août 2002
    Messages : 132
    Points : 102
    Points
    102
    Par défaut
    Houla!
    C'est sans doute un peu plus compliqué

    Il faudrait faire des calculs... je ne m'en sens pas tellement ce soir...

    Mais si j'y pense, peut-être c w-e...

    A bientôt

    Ceci dit, maintenant que tu as pour les puissances de 2, ça te donne déjà une bonne idée...

    Bon courage

  7. #7
    Membre régulier
    Inscrit en
    Août 2002
    Messages
    132
    Détails du profil
    Informations forums :
    Inscription : Août 2002
    Messages : 132
    Points : 102
    Points
    102
    Par défaut
    Je peux juste te donner une piste supplémentaire :

    (Voir binôme de Newton) :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
    (n+1)^0 = 1
     
    (n+1)^1 = n+1
     
    (n+1)² = n²+2n+1
     
    (n+1)³ = n³ + 3n² + 3n +1
     
    (n+1)^4 = n^4 + 4n³ + 6n² + 4n + 1
     
    ...
    Les coefficients des binomes sont les suivants :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    1
    1  1
    1  2  1
    1  3  3  1
    1  4  6  4  1
    1  5  10 10 5 1
    ...
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    Pour les trouver, c'est très facile : la somme des deux du dessus donne celui d'en-dessous
    Ce sont les coefficients binomiaux :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    Cmp  =   m!  / [  p!  * ( m-p )! ]
    (m est en indice et p en exposant)
    le symbole ! représente la factorielle :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
      n! = 1 * 2 * 3 * 4 * ... * (n-1) * n
    Bon courage...

  8. #8
    Inactif  
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    123
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2002
    Messages : 123
    Points : 130
    Points
    130
    Par défaut mes recherches
    Voici mes résultats de recherche:

    f(x) = x --------------------- f(x+1) = x+1
    f(x) = x² -------------------- f(x+1) = x²+2x+1
    f(x) = x^3 ------------------ f(x+1) = x^3 + 3x²+3x+1
    f(x) = x^4 ------------------ f(x+1) = x^4 + 4x^3 + 6x² + 4x + 1

    En remplacant les puissances de x par UN(x) et x par n j'obtiens:

    U1(n+1) = U1(n) + 1
    U2(n+1) = U2(n) + 2U1(n) + 1
    U3(n+1) = U3(n) + 3U2(nà + 3U(n) + 1
    U4(n+1) = U4(n) + 4U3(n) + 6U2(n) + 4U(n) + 1

    ce qui donne pour U2(n+2)
    U2(n+2) = U2(n+1) + 2U1(n+1) + 1 = 2U2(n+1) - U2(n) + 2

    pour U3(n+3)
    U3(n+3) = 3U3(n+2) - 3U3(n+1) + U3(n) + 6

    pour U4(n+7)
    U4(n+7) = U4(n+6) + ...

    donc il faut 6 points pour calculer x^4, c'est à dire le double que pour calculer x^3...soit avec x^20, 2^20 points...aie aie

    cependant, en calculant tout ça j'ai remarqué que:

    pour la puissance de 1: U(n+1) - U(n) + C soit les coefficients [ 1 -1 ]
    pour la puissance 2: U(n+2) - 2U(n+1) + U(n) + C [ 1 -2 1 ]
    pour la puissance 3: [ 1 -3 3 1 ]
    et pour la puissance 4: [ 1 4 -5 -2 5 -4 1 ]

    donc aux signes près la moitié des coefficients est suffisant. donc la moitié des points également.

    cette propriété permet-elle de calculer x^20 seulement avec 20 points ?
    under construction...

Discussions similaires

  1. Puissance 4 - IA par récursivité
    Par SeaoI dans le forum C++/CLI
    Réponses: 1
    Dernier message: 03/12/2013, 11h22
  2. Soucis raisonnement par récurrence
    Par NiamorH dans le forum Mathématiques
    Réponses: 2
    Dernier message: 31/07/2009, 17h44
  3. Raisonnement par récurrence
    Par Bovino dans le forum Enigmes
    Réponses: 3
    Dernier message: 09/02/2009, 14h33
  4. Destruction par récurrence
    Par koushkov dans le forum C++
    Réponses: 4
    Dernier message: 20/04/2007, 18h26
  5. [MySQL] Lister un nombre de résultats par récurrence
    Par Anduriel dans le forum PHP & Base de données
    Réponses: 3
    Dernier message: 04/02/2007, 21h53

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