Répondre à la discussion
Affichage des résultats 1 à 23 sur 23

Algorithme de calcul de la puissance d'un nombre

  1. #1
    Sam*

    Algorithme de calcul de la puissance d'un nombre

    Bonjour, j'ai écris un algorithme qui permet de calculer la puissance d'un entier naturel pn :

    Var i , exp , p , n : entiers

    Debut


    lire(p)
    lire(n)
    Si n=0 alors exp := 1
    Sinon
    exp:= 1
    pour i de 1 à n faire
    exp := exp * p
    Fin pour
    Fin si
    Fin

    PS : " := " signifie "reçoit".
    Merci de corriger cet algorithme.

    -----


  2. Publicité
  3. #2
    Astérion

    Re : Algorithme de calcul de la puissance d'un nombre

    Re,

    Citation Envoyé par Sam* Voir le message
    Bonjour, j'ai écris un algorithme qui permet de calculer la puissance d'un entier naturel pn :

    Var i , exp , p , n : entiers

    Debut


    lire(p)
    lire(n)
    Si n=0 alors exp := 1
    Sinon
    exp:= 1
    pour i de 1 à n faire
    exp := exp * p
    Fin pour
    Fin si
    Fin

    PS : " := " signifie "reçoit".
    Merci de corriger cet algorithme.
    Je me demande... pourquoi ne pas le faire de manière récusive... plutôt que de faire une boucle...?

    M'enfin...

    A plus.
    "The more is different" P.W Anderson.

  4. #3
    Astérion

    Re : Algorithme de calcul de la puissance d'un nombre

    Re,

    exemple:

    var exp, n,p:entier
    [...]
    fonction(n,p) donne entier
    si n=0 alors exp:=0
    sinon exp:=fonction(n-1,p)*p
    fin si
    [...]

    Voilà, comment je ferai,...mais bon, je n'ai pas vraiment fait de cours d'algo de ma vie!

    A plus;
    "The more is different" P.W Anderson.

  5. #4
    Sam*

    Re : Algorithme de calcul de la puissance d'un nombre

    Peut-etre mais moi on me demande d'utiliser une boucle , je ne sais pas ce que c'est que la récursivité .

  6. #5
    Coincoin

    Re : Algorithme de calcul de la puissance d'un nombre

    Salut,
    Citation Envoyé par Sam* Voir le message
    Merci de corriger cet algorithme.
    Ça me paraît bon, si n est un entier positif.

    Citation Envoyé par Astérion Voir le message
    Voilà, comment je ferai,...mais bon, je n'ai pas vraiment fait de cours d'algo de ma vie!
    Ce qui explique que tu ne connaisses pas l'exponentiation rapide...
    Encore une victoire de Canard !

  7. #6
    whoami

    Re : Algorithme de calcul de la puissance d'un nombre

    Bonjour,
    Citation Envoyé par Astérion Voir le message
    Je me demande... pourquoi ne pas le faire de manière récusive... plutôt que de faire une boucle...?
    Parce que utiliser la récursivité quand elle n'apparaît pas naturellement dans l'algorithme est une absurdité (et je pèse mes mots) : consommation mémoire, puissance processeur, risque de débordement de la pile du programme si on ne prend pas de précautions ...

    La récursivité, c'est beau en théorie, mais l'informatique ne se fait pas qu'avec de la beauté, il faut de l'efficacité.
    À part la mort et les impôts, tout n'est qu'incertitude.

  8. #7
    whoami

    Re : Algorithme de calcul de la puissance d'un nombre

    Bonjour,
    Citation Envoyé par Astérion Voir le message
    Re,

    exemple:

    var exp, n,p:entier
    [...]
    fonction(n,p) donne entier
    si n=0 alors exp:=0
    sinon exp:=fonction(n-1,p)*p
    fin si
    [...]

    Voilà, comment je ferai,...mais bon, je n'ai pas vraiment fait de cours d'algo de ma vie!

    A plus;
    Ce qui est faux, bien entendu.

    Sans parler de la fonction récursive (voir ci-dessus).
    À part la mort et les impôts, tout n'est qu'incertitude.

  9. #8
    Astérion

    Re : Algorithme de calcul de la puissance d'un nombre

    Re,

    Citation Envoyé par whoami Voir le message
    Bonjour,

    Parce que utiliser la récursivité quand elle n'apparaît pas naturellement dans l'algorithme est une absurdité (et je pèse mes mots) : consommation mémoire, puissance processeur, risque de débordement de la pile du programme si on ne prend pas de précautions ...

    La récursivité, c'est beau en théorie, mais l'informatique ne se fait pas qu'avec de la beauté, il faut de l'efficacité.
    Pourtant pour des réaliser des tris... je trouve la méthode récursive très sympa.
    D'ailleurs, sans être malhonnête, elle apparait naturellement là.
    puis des gardes-fous, ça se met en place....
    d'ailleurs, ici, on parle d'algo... mais le message est bien reçu, c'est une absurdité

    Citation Envoyé par Coincoin
    Ce qui explique que tu ne connaisses pas l'exponentiation rapide...
    et bah non, je ne connais pas tout ... mais j'apprends beaucoup

    A plus.
    "The more is different" P.W Anderson.

  10. #9
    Astérion

    Re : Algorithme de calcul de la puissance d'un nombre

    Re,

    Citation Envoyé par whoami Voir le message
    Bonjour,

    Ce qui est faux, bien entendu.

    Sans parler de la fonction récursive (voir ci-dessus).
    erreur de frappe de ma part, bien entendu (mais bon, tu as envie de te montrer non indulgeant ...)
    Pour la récursivité... j'ai répondu.

    A plus.

    Rq: Heureusement que j'ai dit que je n'y connaissais rien (hé oui j'ai mis un garde fou! ) sinon, la vache! Autant aller se guillotiner avec toi!

    A plus.
    "The more is different" P.W Anderson.

  11. #10
    Astérion

    Re : Algorithme de calcul de la puissance d'un nombre

    Re,

    J'ai ça pour ceux que ça intéresse ( notamment moi...).

    http://www.developpez.net/forums/d20...s-recursivite/

    A plus.
    "The more is different" P.W Anderson.

  12. #11
    Jack

    Re : Algorithme de calcul de la puissance d'un nombre

    Si n=0 alors exp := 1
    Sinon
    exp:= 1
    Donc dans tous les cas exp:=1

    On peut donc réduire à:
    Code:
    lire(p)
    Debut
        lire(n)
        exp:= 1
        Si n!=0 alors 
            pour i de 1 à n faire
               exp := exp * p
            Fin pour
        Fin si 
    Fin
    Note comme la balise code permet d'améliorer la lisibilité

    A+

  13. #12
    Sam*

    Re : Algorithme de calcul de la puissance d'un nombre

    Citation Envoyé par Jack Voir le message
    Donc dans tous les cas exp:=1

    On peut donc réduire à:
    Code:
    lire(p)
    Debut
        lire(n)
        exp:= 1
        Si n!=0 alors 
            pour i de 1 à n faire
               exp := exp * p
            Fin pour
        Fin si 
    Fin
    Note comme la balise code permet d'améliorer la lisibilité

    A+
    Non la condition "si n:=0 alors exp:=1" est importante , j'ai testé l'algorithme sous maple et effectivement s'il n'y pas cette condition le programme n'arrive pas à calculer p0.

  14. #13
    Jack

    Re : Algorithme de calcul de la puissance d'un nombre

    Non la condition "si n:=0 alors exp:=1" est importante
    Oui, mais avec l'algo que j'ai donné, si n est égal à 0, exp sera bien égal à 1 puisque la première chose que je fais est de mettre exp à 1 quelle que soit la valeur de n.

    Donc mon algo est bon.

    A+

  15. #14
    whoami

    Re : Algorithme de calcul de la puissance d'un nombre

    Bonjour,
    Citation Envoyé par Jack Voir le message
    Oui, mais avec l'algo que j'ai donné, si n est égal à 0, exp sera bien égal à 1 puisque la première chose que je fais est de mettre exp à 1 quelle que soit la valeur de n.

    Donc mon algo est bon.

    A+
    Oui, mais on peut encore simplifier :

    Puisque exp est initialisé à 1, et qu'un boucle de 1 à n ne bouclera pas si n = 0.
    Code:
    Debut
        lire(p)
        lire(n)
        exp:= 1
        pour i de 1 à n faire
            exp := exp * p
        Fin pour
    Fin
    À part la mort et les impôts, tout n'est qu'incertitude.

  16. #15
    Jack

    Re : Algorithme de calcul de la puissance d'un nombre

    Oui, mais on peut encore simplifier :

    Puisque exp est initialisé à 1, et qu'un boucle de 1 à n ne bouclera pas si n = 0.
    Je n'ai pas osé le proposer car si ça marche en C par exemple, ça n'est pas garanti en ALGO.

    A+

  17. #16
    whoami

    Re : Algorithme de calcul de la puissance d'un nombre

    Bonjour,
    Citation Envoyé par Jack Voir le message
    Je n'ai pas osé le proposer car si ça marche en C par exemple, ça n'est pas garanti en ALGO.

    A+
    Que fait ALGO dans ce cas ?

    S'il passe une fois dans une boucle de 1 à 0 avec pas positif, c'est grave !
    À part la mort et les impôts, tout n'est qu'incertitude.

  18. #17
    Jack

    Re : Algorithme de calcul de la puissance d'un nombre

    Que fait ALGO dans ce cas ?
    Justement on n'en sait rien. Tu connais une norme qui définit le langage algorithmique?

    S'il passe une fois dans une boucle de 1 à 0 avec pas positif, c'est grave !
    Pourquoi pas. Qu'est ce qui dit que le test est effectué en début ou en fin d'itération, après l'incrémentation du compteur. Bref, en analogie avec le C, est-ce plutôt du do ... while ou du while ... ?

    A+

  19. #18
    whoami

    Re : Algorithme de calcul de la puissance d'un nombre

    Bonjour,

    On fait une boucle POUR. Tout est dit.
    À part la mort et les impôts, tout n'est qu'incertitude.

  20. #19
    Jack

    Re : Algorithme de calcul de la puissance d'un nombre

    Quel organisme a défini le fonctionnement d'une boucle POUR?

    A+

  21. #20
    Jack

    Re : Algorithme de calcul de la puissance d'un nombre

    Afin d'éviter d'éterniser cette discussion, je suis évidemment d'accord avec toi pour dire qu'une boucle POUR conviendra. Je voulais juste éviter d'affirmer un truc qui n'est finalement défini par personne. On se tiendra donc au conventions.

    De toutes manières, il va falloir le coder dans un langage ou un autre qui sera lui parfaitement défini.

    A+

  22. #21
    whoami

    Re : Algorithme de calcul de la puissance d'un nombre

    Bonjour,
    Citation Envoyé par Jack Voir le message
    Je voulais juste éviter d'affirmer un truc qui n'est finalement défini par personne
    Peut-être, mais je n'ai JAMAIS vu d'interprétations autre que l'usuelle :

    On parcourt de valeur_début à valeur_fin par pas à définir, avec par défaut pas = +1.

    Citation Envoyé par Jack Voir le message
    De toutes manières, il va falloir le coder dans un langage ou un autre qui sera lui parfaitement défini.
    Oui, mais on parle d'algorithme, qui DOIT être indépendant du langage qui sera utilisé pour l'implémentation.
    À part la mort et les impôts, tout n'est qu'incertitude.

  23. #22
    Jack

    Re : Algorithme de calcul de la puissance d'un nombre

    On parcourt de valeur_début à valeur_fin par pas à définir, avec par défaut pas = +1.
    Ok si je complète ta définition

    Code:
    SI valeur_début ≤  valeur_fin
        On parcourt de valeur_début à valeur_fin par pas à définir, avec par  défaut pas = +1.

  24. #23
    34destrier

    Re : Algorithme de calcul de la puissance d'un nombre

    La complexité calculatoire vous en faites quoi ?
    Votre définition, la définition mathématique qui mène naturellement à une fonction récursive plus qu'à une boucle, est
    x0=1,
    xn=x*xn-1 si n>0.

    et mènerai à (en langage Oz)
    Code:
    fun{Pow X N}
    if N==0 then 1 else X*{Pow X N-1} end
    end
    Ce qui est trop couteux en terme d'espace et de temps...

    Il faut plutôt utiliser la définition alternative suivante :
    x0=1,
    x2n+1=x*x2n,
    x2n=y2 où y=xn (x>0)

    Et utiliser la récursion terminale

    Code:
    fun {Pow X N}
    if N==0 then 1
    elseif N mod 2 == 1 then X*{Pow X (N-1)}
    else Y in Y={Pow X (N div 2)} Y*Y end
    end
    Enfin après on peut s'improviser et coder ça salement (essayez votre code avec 5^30) !

    Bon courage...
    Dernière modification par 34destrier ; 04/10/2013 à 13h32.

Discussions similaires

  1. Calcul de la puissance d'un échangeur
    Par spoltibrun dans le forum Environnement, développement durable et écologie
    Réponses: 11
    Dernier message: 16/03/2012, 08h59
  2. puissance réel d'un nombre complexe
    Par Morghot dans le forum Mathématiques du supérieur
    Réponses: 8
    Dernier message: 28/08/2009, 19h40
  3. Puissance réelle d'un nombre complexe.
    Par invite43219988 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 03/04/2009, 19h22
  4. Puissance d'un nombre
    Par Seirios dans le forum Mathématiques du supérieur
    Réponses: 26
    Dernier message: 11/01/2009, 18h17
  5. Algorithme de calcul d'un déterminant de matrice
    Par Liv dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 12/11/2006, 18h45