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

Caml Discussion :

"diviser pour régner" itération - puissance n


Sujet :

Caml

  1. #1
    Candidat au Club
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    10
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 10
    Points : 2
    Points
    2
    Par défaut "diviser pour régner" itération - puissance n
    Bonjour,

    J'essaie de transformer ce programme récursif :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    let rec puiss x n = match n with
      | 0 -> 1.0
      | _ -> let y = puiss x (n/2) in
                 if n mod 2 = 0 then puiss y (n/2) else x *. puiss y (n/2)
    ;;
    en un programme itératif.

    Alors je fais une référence X sur x mais à chaque étape, comment savoir s'il faut faire X:= !X *. !X ou X:= !X *. !X *. x à chaque étape ?

    merci de l'aide !

  2. #2
    Expert éminent
    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
    Points : 8 586
    Points
    8 586
    Par défaut
    Citation Envoyé par Sokoudan
    Bonjour,

    J'essaie de transformer ce programme récursif :
    let rec puiss x n = match n with
    | 0 -> 1.0
    | _ -> let y = puiss x (n/2) in
    if n mod 2 = 0 then puiss y (n/2) else x *. puiss y (n/2)
    ;;
    en un programme itératif.

    Alors je fais une référence X sur x mais à chaque étape, comment savoir s'il faut faire X:= !X *. !X ou X:= !X *. !X *. x à chaque étape ?

    merci de l'aide !
    De la même façon que dans le récursif.

    --
    Jedaï

  3. #3
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    l'algo d'exponentiation rapide itératif est classique... et simple à faire

    indication : 1 boucle while et 2 références


    essaies, on corrigera
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  4. #4
    Candidat au Club
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    10
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 10
    Points : 2
    Points
    2
    Par défaut
    Merci pour les réponses je regarderai ce soir.

    Je signale juste qu'il y a une erreur dans le programme c'est plutôt :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    let rec puiss x n = match n with
      | 0 -> 1.0
      | _ -> let y = puiss x (n/2) in
                 if n mod 2 = 0 then y *. y else x *. y *. y
    ;;

  5. #5
    Candidat au Club
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    10
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 10
    Points : 2
    Points
    2
    Par défaut
    L'exponentiation rapide c'est justement ce qu'on est en train d'apprendre mais on a pas encore vraiment de méthode.
    L'algorithme a utilisé est :
    x^0 = 1
    x^n = x^(n/2) * x^(n/2) si n est pair
    x^n = x^(n/2) * x^(n/2) * x sinon
    Mais le problème avec l'itération c'est qu'on part du bas, on part de X = ref x (du moins, je pense) donc en partant du bas, comment peut-on savoir si on doit aller à x^2 par exemple pour calculer x^4 ou si on doit aller à x^3 pour aller à x^6 par exemple ?
    Vous parlez du deuxième référence, donc sur n je suppose, mais je vois pas trop quoi en faire, car si on fait une référence sur n, ça suppose qu'on parte "du haut" et en itératif je vois pas vraiment comment on peut partir du haut.

    Merci.

  6. #6
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    une petite indication


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    données a n0
    initialisation res = 1 ; n = n0 ; x = a
     
    invariant de boucle  res * x^n = a^n0
     
    donc à la fin, on a n=0 et on renvoie res = a^n0


    il te reste à trouver comment on y arrive
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  7. #7
    Candidat au Club
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    10
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 10
    Points : 2
    Points
    2
    Par défaut
    Mais ça fait trois références et pas deux ?

  8. #8
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    Citation Envoyé par Sokoudan
    Mais ça fait trois références et pas deux ?

    en fait t'as pas besoin du x...
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  9. #9
    Candidat au Club
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    10
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 10
    Points : 2
    Points
    2
    Par défaut
    Je comprends mal tes notations, je chercher à calculer x^n.
    Alors n0 est la référence sur n ? res c'est le résultat d'accord.
    Mais alors tu dis que x = a est inutile donc l'invariant de boucle devient quoi ?

  10. #10
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    tu cherches à calculer a^n0 !!!! (ceux sont les données)

    n est un référence sur n0, et res une référence initialisée à 1

    l'invariant est en fait res * a^n = a^n0

    mais si je le donne ainsi, l'algo est immédiat, c'est moins drole
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  11. #11
    Candidat au Club
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    10
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 10
    Points : 2
    Points
    2
    Par défaut
    Je dois être vraiment mauvais car je vois pas où tu veux en venir !
    Avec ton point de départ, je ne vois qu'un seul chemin : utiliser l'algorithme naïf :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    res := !res * a; n := !n - 1
    ;
    Enfin, jpense pas que tu pensais à ça ...

    Je me dis que de toute façon il faudra faire n := !n / 2 mais alors pour que l'invariant de boucle soit respecté il faudrait que dans res on ait : a^(n0/2) à la première boucle et c'est impossible.

    Sûrement une petite 'subtilité' que jvois pas.

    Merci de m'aider.

  12. #12
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 58
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    Citation Envoyé par Sokoudan
    Je dois être vraiment mauvais car je vois pas où tu veux en venir ![...]
    Si c'est la première fois que tu le vois ce n'est pas évident.

    Regardes bien l'indication de Gorgonite.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    données a n0
    initialisation res = 1 ; n = n0 ; x = a
     
    invariant de boucle  res * x^n = a^n0
     
    donc à la fin, on a n=0 et on renvoie res = a^n0
    Remarques qu'il a initialisé un x par a.

    Pourquoi, à ton avis, n'a-t-il pas simplement écrit la chose suivante ?
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    invariant de boucle  res * a^n = a^n0
    Ensuite remarques que ce que

    x^n = x^(n/2) * x^(n/2) si n est pair

    pourrait être réécrit

    x^n = (x^2)^(n/2) si n est pair.

    Est-ce que ça t'aide ?

  13. #13
    Candidat au Club
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    10
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 10
    Points : 2
    Points
    2
    Par défaut
    Merci pour la réponse, mais il y a quelques soucis :

    Remarques qu'il a initialisé un x par a.

    Pourquoi, à ton avis, n'a-t-il pas simplement écrit la chose suivante ?
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    invariant de boucle  res * a^n = a^n0
    Dans ses messages #8 et #10, gorgonite dit que le x est en fait inutile et que l'invariant de boucle est bien : res * a^n = a^n0.
    Ensuite remarques que ce que

    x^n = x^(n/2) * x^(n/2) si n est pair

    pourrait être réécrit

    x^n = (x^2)^(n/2) si n est pair.
    Le fait de changer l'écriture nous fait changer d'algorithme, l'algorithme que tu décris fait l'objet d'un deuxième exercice déjà corrigé par le professeur et en effet il utilise une référence sur a.
    Donc il faut garder la première écriture.

    Merci de m'aider

  14. #14
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    Citation Envoyé par Sokoudan
    Le fait de changer l'écriture nous fait changer d'algorithme, l'algorithme que tu décris fait l'objet d'un deuxième exercice déjà corrigé par le professeur et en effet il utilise une référence sur a.
    Donc il faut garder la première écriture.

    changer l'implémentation ne modifie pas forcemment l'algorithme qui est derrière... mais peut modifier radicalement ses performances

    un indice supplémentaire :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    let exp a n0 =
         let x = ref a and n = ref n0 and res = ref 1 in
         while (!n > 0) do
            if (!n mod 2) = 1 then (
    ...
    	)
    	else (
    ...
    	)
    done;
    !res;;
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  15. #15
    Candidat au Club
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    10
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 10
    Points : 2
    Points
    2
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    let exp a n0 =
       let x = ref a and n = ref n0 and res = ref 1. in
         while (!n > 0) do
            if (!n mod 2) = 1 
              then  begin n := !n-1; res := !ref *. !x; end
    	  else begin x := !x *. !x; n := !n / 2; end
         done;
         !res
    ;;
    Je pense que t'essaies de m'amener là.
    Mais comme je l'ai dit, ce n'est pas ce que le prof attend, pour lui x^2n = x^n * x^n et x^2n = (x*x)^n ce n'est pas pareil

  16. #16
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 58
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    Citation Envoyé par Sokoudan
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    let exp a n0 =
       let x = ref a and n = ref n0 and res = ref 1. in
         while (!n > 0) do
            if (!n mod 2) = 1 
              then  begin n := !n-1; res := !ref *. !x; end
    	  else begin x := !x *. !x; n := !n / 2; end
         done;
         !res
    ;;
    Je pense que t'essaies de m'amener là.
    Mais comme je l'ai dit, ce n'est pas ce que le prof attend, pour lui x^2n = x^n * x^n et x^2n = (x*x)^n ce n'est pas pareil
    Bon tu as peut-être reçu des indications particulières. Dans ce cas c'est avec ton prof que tu dois en discuter. Si tu gardes
    x^2n = x^n * x^n
    explicitement, tu auras du mal à trouver une formule itératif (la formule récursive n'est pas sous forme terminale).

    Reposes lui la question peut-être ça vaut mieux que de croire qqchose.
    Indiques lui ta solution et comment tu y es arrivé.

  17. #17
    Candidat au Club
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    10
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 10
    Points : 2
    Points
    2
    Par défaut
    En fait il nous a donné des poly à étudier pendant les vacances, dans un des paragraphes on étudie ça sous forme x^2n = x^n * x^n. Il nous propose la manière récursif et nous demande de transformer en itératif pour avoir une complexité spatiale constante.
    Dans le paragraphe suivant il nous dit qu'on peut aussi faire de la manière x^2n = (x*x)^n et il nous donne alors directement les programmes récursifs et itératifs à utiliser (le programme itératif que j'ai recopié).
    Voilà, et merci quand même d'avoir pris le temps de m'aider
    Bonne soirée

  18. #18
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    voilà ce que j'attendais...

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    let exp a n0 =
    let x = ref a and n = ref n0 and res = ref 1 in
    while (!n > 0) do
        if (!n mod 2) = 1 then (
            res := !res * a;
            n := !n - 1;
        )
        else (
            res := !res * !x;
            n := !n / 2;
            x := !x * !x;
        )
    done;
    !res;;

    je pense que c'est assez proche de ce que ton prof veut... car cela constitue un morceau d'une partie d'un des écrits pour le concours des mines (2003 si je me souviens bien )
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  19. #19
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Elle est chelou leur exponentiation rapide !
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  20. #20
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    Citation Envoyé par InOCamlWeTrust
    Elle est chelou leur exponentiation rapide !

    la mienne... ou la sienne ?


    en ce qui concerne la mienne, elle n'est pas vraiment optimal car le nombre de tour de boucles dépend du nombre de 1 dans la représentation binaire de n0 (mais tu dois t'en souvenir... on l'avait eu en DS de Spé )

    il existe une autre version qui fait vraiment log2(n0) tours de boucle... mais elle sera un peu plus compliquée à comprendre
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

Discussions similaires

  1. Explication de la résolution de récurrence diviser pour régner
    Par mamioop dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 26/12/2011, 21h25
  2. Diviser Pour Régner
    Par touftouf57 dans le forum Algorithmes et structures de données
    Réponses: 13
    Dernier message: 01/11/2011, 19h48
  3. stratégie "Diviser pour régner"
    Par z_meryem dans le forum C
    Réponses: 7
    Dernier message: 31/03/2008, 04h03
  4. [complexité] Diviser pour règner, resolution recurrence
    Par rvfranck dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 22/10/2007, 11h59

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