Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 35

algorithmique permutations (ADA)



  1. #1
    magodeoz

    algorithmique permutations (ADA)


    ------

    Bonjour,
    J'ai quelques soucis concernant cet exercice:
    "Afficher en ordre à l'aide d'une permutation ordonnant S."
    1) Donner la valeur P,pour S=[40,70,80,50,30,45,72,60].
    Donc ça ça va, ça donne : P= 5,1,6,4,8,2,7,3
    Ensuite:
    On spécifie les actions suivantes:
    AfficherEnOrdreSelonP (S,P): une action (les données:une seq-Ent,un Tab_Ent)
    {affiche les éléments de S en ordre croissant sachant que P[1..LdeS] est une permutation ordonnant S}.
    CréerPerm (S,P):une action (la donnée:une Seq_Ent;le résultat:un Tab_Ent)
    {CréerPerm(S,P) construit dans P[1..LdeS] la permutation ordonnant la séquence S.}
    Pour AfficherEnOrdre:
    Pour i de 1 à LdeS
    Ecrire (S.T(P(i)))

    avec LdeS longueur de la séquence et S.T le tableau contenant les valeurs de S.

    Je peine pour CreerPerm...Pourriez-vous m'aider?

    D'avance merci,
    Cordialement,
    Mägodeoz

    -----

  2. Publicité
  3. #2
    kwariz

    Re : algorithmique permutations (ADA)

    Bonjour,

    il faut penser à la balise code quand tu insère du code ou un algo ou quelquechose du genre car ce sera plus lisible.

    Créer cette permutation n'est en soi pas plus complexe que trier un tableau, la séquence S dans ton cas.
    Une approche sera simplement de copier S en S' puis trier S'. T[i] est simplement l'indice de S'[i] dans S.

  4. #3
    magodeoz

    Re : algorithmique permutations (ADA)

    Merci de ta réponse kwariz. OK pour le code, c'est vrai que c'est plus lisible, quoique pour les petits programmes ça reste passable.
    Code:
    b<- faux
    for i in 1..S.L
    P(i)=i
    while not b
       c<-0
           for i in 1..S.L 
                if S.T(P(i+1))< S.T(P(i)) then c<- c+1
                  Echanger (P(i+1),P(i));
                end if;
             end loop;
                 if c=0 then b=true 
               enf if
    end loop;
    Bon c'est mi-algo mi-programmation mais voila ^^ Par contre on me dit en utilisant l'algo précédant mais je ne vois pas trop comment...

  5. #4
    kwariz

    Re : algorithmique permutations (ADA)

    Bon, le code est un peu mal indenté mais en l'ayant lu en diagonale je peux te dire que deux boucles imbriquées avec le même itérateur (dans ton cas tu utilises la variable i pour les deux boucles) est certainement faux.

  6. A voir en vidéo sur Futura
  7. #5
    magodeoz

    Re : algorithmique permutations (ADA)

    Erreur en recopiant...Le 1er for finit avant le while...
    Par contre c'est le "en modifiant l'algo précédant " qui pose problème....

  8. #6
    kwariz

    Re : algorithmique permutations (ADA)

    Juste pour que ce soit clair dans ma petite tête, on te donne :
    Code:
    AfficherEnOrdreSelonP (S,P)
    S : séquence d'entier de longueur L
    P : tableau d'entier de longueur L
    début
      pour i de 1 à L faire
        afficher S[P[i]]
      fin pour
    fin
    L'algo est correct pas de problèmes.
    Ensuite on te demande d'écrire CréerPerm qui va justement créer la permutation te permettant d'afficher une séquence par ordre croissant.
    L'algorithme que tu proposes est basé sur un tri à bulle et manipule directement la permutation (ce qui est plus élégant que de faire des copies et des tris).

    Alors comment transformer un tri à bulle en place (qui trie effectivement le tableau) en tri à bulle générant une permutation ?

    On part de l'algo du tri à bulle :
    Code:
    répéter
      échange_effectué = faux
      pour i de 1 à L-1
        si S[i] > S[i + 1], alors
          échanger S[i] et S[i + 1]
          échange_effectué = vrai
        fin si
      fin pour
    tant que échange_effectué
    Ensuite il faut juste se rappeler qu'en utilisant une permutation P, tu dois comparer non S[i] et S[i+1] mais S[P[i]] et S[P[i+1]] et que tu ne dois pas échanger les entiers dans la séquence mais leur position dans la permutation, i.e. il faut échanger P[i] et P[i+1]. Ce qui en gros doit donner :

    Code:
    répéter
      échange_effectué = faux
      pour i de 1 à L-1
        si S[ P[i] ] > S[ P[i + 1] ], alors
          échanger P[i] et P[i + 1]
          échange_effectué = vrai
        fin si
      fin pour
    tant que échange_effectué
    Tout algorithme de tri peut ainsi être transformé (c'est un peu plus coton avec quicksort ou heapsort ...).
    Dernière modification par kwariz ; 18/10/2012 à 16h01. Motif: emphase sur les modifs

  9. Publicité
  10. #7
    magodeoz

    Re : algorithmique permutations (ADA)

    De nouveau merci ta réponse

    Donc pour AfficherEnOrdre on est ok...
    Pour CréerPerm, on a la même chose il me semble non...?
    Je ne vois toujours pas comment modifier l'algo de AfficherEnOrdre pour obtenir CréerPerm...
    ça:
    Code:
    répéter
      échange_effectué = faux
      pour i de 1 à L-1
        si S[i] > S[i + 1], alors
          échanger S[i] et S[i + 1]
          échange_effectué = vrai
        fin si
      fin pour
    tant que échange_effectué
    représente la séquence dans l'ordre n'est ce pas?Est-ce que c'est AfficherEnOrdre?

    Code:
    répéter
      échange_effectué = faux
      pour i de 1 à L-1
        si S[ P[i] ] > S[ P[i + 1] ], alors
          échanger P[i] et P[i + 1]
          échange_effectué = vrai
        fin si
      fin pour
    tant que échange_effectué
    Code:
    b<- faux
    for i in 1..S.L
    P(i)=i
    while not b
       c<-0
           for i in 1..S.L 
                if S.T(P(i+1))< S.T(P(i)) then c<- c+1
                  Echanger (P(i+1),P(i));
                end if;
             end loop;
                 if c=0 then b=true 
               enf if
    end loop;
    même algo non?Avec les notations qui changent.
    EDIT: Ah non vous avez également fait sans compteur...
    Dernière modification par magodeoz ; 18/10/2012 à 16h43.

  11. #8
    kwariz

    Re : algorithmique permutations (ADA)

    Oui, j'ai repris ton idée de base c'est-à-dire l'utilisation du squelette du tri à bulle mais ton algo
    Code:
    b<- faux
    for i in 1..S.L
      P(i)=i
      while not b
        c<-0
        for i in 1..S.L 
          if S.T(P(i+1))< S.T(P(i)) then c<- c+1
            Echanger (P(i+1),P(i));
          end if;
        end loop;
        if c=0 then
          b=true 
        enf if
      end loop;
    est approximatif (même s'il n'y a rien de vraiment standard, il faut fermer ses boucles , et il contient une petite erreur au niveau des indices). Je pense que tu as voulu écrire une première boucle pour initialiser P à [1,2,....,L] que tu as oublié de fermer. Donc ce serait plus :
    Code:
    b<- faux
    for i in 1..S.L
      P(i)=i
    end loop
    while not b
      c<-0
      for i in 1..S.L 
        if S.T(P(i+1))< S.T(P(i)) then c<- c+1
          Echanger (P(i+1),P(i));
        end if;
      end loop;
      if c=0 then
        b=true 
      enf if
    end loop;
    Ensuite, plutôt que d'utiliser b et c (ok on se doute que b est pour booléen et c pour compteur ...), on peut utiliser quelque chose de plus explicite. Par exemple à la place de b on peut imaginer utiliser une variable nommée "arrêter". Ma version de bubblesort n'utilise pas un compteur d'échange (car on a pas besoin de savoir combien d'échanges sont faits mais juste s'il y en a eu au moins un, auquel cas on continue). Ma variante utilise une boucle do/while plutôt qu'un while ... mais c'est pareil.

    MAIS IL Y A UNE ERREUR (en rouge dans le code suivant) : tu compares un élément avec le suivant donc tu ne dois pas parcourir TOUS les éléments mais JUSTE les éléments qui ont un suivant (=tous sauf le dernier d'où le -1)

    Code:
    for i in 1..S.L
      P(i)=i
    end loop
    arreter<- faux
    while not arreter
      arreter<-vrai
      for i in 1..S.L-1
        if S.T(P(i+1))< S.T(P(i)) then
          Echanger (P(i+1),P(i));
          arreter<-faux;
        end if;
      end loop;
    end loop;
    Mais tu avais l'idée de base ... après les erreurs sont minimes et tu les aurais découvertes lors d'une trace par exemple.

    Maintenant, fort honnêtement, je ne vois pas en quoi c'est cohérent de demander de modifier AfficherEnOrdre pour créer CréerPerm ... Peut-être pourrais-tu donner l'énoncé exact pour clarifier ce qui est demandé ?

    EDIT: tu peux me tutoyer.

  12. #9
    magodeoz

    Re : algorithmique permutations (ADA)

    Tout compris pour l'algo, je vois pour S.L-1, S.L n'a pas de suivant donc non traité. En effet, j'ai oublié de fermer le 1er for
    Je te mets l'énoncé en pièce jointe.

    PS: Oui, j'ai du mal à tutoyer sans voir la personne à qui je m'adresse. Mais je vais me faire violence

    Tout est fait jusqu'à la question avant la Deuxième Partie.
    Images attachées Images attachées

  13. #10
    kwariz

    Re : algorithmique permutations (ADA)

    OK, la question qu ite pose problème ne demande pas de construire CréerPerm à partir de AfficherEnOrdreSelonP, mais d'utiliser ce qui a été fait au début c'est-à-dire IndicePlusPetitSup.
    Tu as donc fais fausse route (mais c'est toujours profitable ).
    Au lieu d'utiliser le tri à bulle (sorti de nulle part ) on te demande d'utiliser le tri par insertion un peu modifié.

  14. #11
    magodeoz

    Re : algorithmique permutations (ADA)

    ....Tragique...
    Pour IndicePlusPetitSup,j'ai fait:
    Code:
    im=un entier;
    im<-1
    Pour i in 1..Lmax
    
     if (T(im+1)>X et T(im+1)<T(im))
    im<-im+1
    Je dois donc me servir de ça..J'ai un peu de mal...
    Dernière modification par magodeoz ; 18/10/2012 à 17h55.

  15. #12
    magodeoz

    Re : algorithmique permutations (ADA)

    Me suis planté pardon...

  16. Publicité
  17. #13
    kwariz

    Re : algorithmique permutations (ADA)

    Moui ... c'est pas tout à fait bon ...
    Sans rentrer dans les détails, on peut remarquer que ton algo ne renvoie jamais 0 (le cas où on ne trouve pas un entier stricement plus grand que X), donc on peut supposer que c'est faux. En reprenant la même convention que l'énoncé (im = valeur de retour IndicePlusPetitSup(S,x) ), l'idée de base va être :

    * au départ on ne l'a pas trouvé, donc im<-0
    * on le cherche, si on le trouve on met le bon indice dans im

    Le dernier point s'implémente avec une simple boucle sur tous les éléments du tab;eau, si on trouve un élément qui est strictement plus grand que X alors il y a deux cas :
    * soit on a pas encore trouvé précédement de minimum (c'est le cas où im vaut 0) -> on vient de le trouver im vaut donc son indice
    * soit on a déjà un minimum sous la main (im ne vaut pas 0), il faut comparer l'élément pointé par im (le minimum courant) et l'élément sur lequel on est, si on a trouvé un nouveau minimum alors on met im à jour

    Tu comprends la démarche ?

  18. #14
    magodeoz

    Re : algorithmique permutations (ADA)

    Oui je comprends bien...D'ailleurs je suis incapable de réécrire ce que j'ai c'est dire... J'avais initialisé im à 0 car s'il n'y a aucun entier satisfaisant,on renvoit im=0.
    Je ne suis pas en grande forme ce soir, je posterais l'algo demain, j'espère que tu seras disponible
    Merci kwariz!
    Dernière modification par magodeoz ; 18/10/2012 à 18h38.

  19. #15
    magodeoz

    Re : algorithmique permutations (ADA)

    Re-bonjour kwariz,
    Bon,voila ma fonction IndicePlusPetitSup (IPPS):
    Code:
    Ecrire (S.T(IPPS(S,MinInt)));
    i=1
    im=0
    Tant que (im=0) et i<Lde S
    Si S.T(i)>X alors im<-i;
    i<-i+1
    Pour i de im à LdeS
    Si (S.T(i)) >X et S.T(i)<im)
    im<-i;
    Retourner im
    Comment m'en sortir pour CreerPerm?

  20. #16
    kwariz

    Re : algorithmique permutations (ADA)

    Bonjour,
    bon, il faut vraiment indenter ton pseudocode pour en montrer la structure (surtout quand on utilise pas les marqueurs de fin). En lisant ton code je ne sais pas si où s'arrête la boucle tant que, la boucle pour est-elle dans la boucle tant que ou en dehors ???
    Là ça va le code n'est pas compliqué et on arrive à déduire ce que tu veux faire :
    Code:
    IPPS(S, T, X) S:sequence d'entiers de longueur LdeS , T une permutation, X la valeur a dépasser
    renvoie l'indice im tel que S(T(im)) est le plus petit élément strictement plus grand que X s'il existe, sinon im=0
        i=1
        im=0
        Tant que (im=0) et i<Lde S
            Si S.T(i)>X alors
                im<-i;
            i<-i+1
        Pour i de im à LdeS
            Si (S.T(i)) >X et S.T(i)<im)
                im<-i;
    Retourner im
    Tu cherches d'abord un élément plus grand que X (qu'il faut également passer en paramètre) et tu vérifies si c'est c'est le minimum : ça me semble correct. Donc on une version de IPPS avec une permutation.

    Maintenant pour créer la permutation qui affiche en ordre une séquence :
    Évidemment on par avec la permutation identité P=[1,2,...,LdeS]
    IPPS(S,P,MinInt) renvoie l'indice I1 dans P du plus petit élément de S, comme c'est le plus petit c'est celui qui devra être en première position dans P ===> on échange P(I1) et P(1)
    IPPS(S,P,I1) revoie l'indice I2 dans P de plus petit élément de S mais plus grand que S.P[I1], c'est-à-dire le deuxième plus petit ====> on échange P(I2) et P(2)
    IPPS(S,P,I2) revoie l'indice I3 dans P de plus petit élément de S mais plus grand que S.P[I2], c'est-à-dire le troisième plus petit ====> on échange P(I3) et P(3)

    ... ainsi de suite ...

    Tu vois un algorithme se dégager ?

  21. #17
    magodeoz

    Re : algorithmique permutations (ADA)

    De nouveau merci de ta réponse...
    Tu vois un algorithme se dégager ?
    Disons que je comprends l'idée...L'écrire, ça c'est une autre affaire ^^
    Bon pour la IPPS de base, je n'avais que 2 données:la séquence et un entier.
    DOnc...pour CreerPerm...Je dois rajouter un argument en donnée qui sera la séquence P (séquence permutation identité initialement) c'est bien ça?

  22. #18
    kwariz

    Re : algorithmique permutations (ADA)

    Oui tout à fait.
    L'idée de ce genre d'exercice est de montrer comment manipuler un tableau en passant par une permutation, en gros on ne modifie jamais le tab;eau (on fait que le lire) et s'il y a des manipulations à faire on les fait dans la permutation (= un tableau d'index). Cela signifie que ta structure de données n'est plus uniquement la séquence mais la séquence et la permutation. Toute fonction de création, d'accès, de modification, ... devra obligatoirement prendre au moins ces deux paramèrtres.

  23. Publicité
  24. #19
    magodeoz

    Re : algorithmique permutations (ADA)

    C'est frustrant parce que ça me paraît tout simple mais je peine à l'écrire...
    L'idée c'est juste de modifier la séquence des permutations P à la base identité en ordonnant les indices des entiers dans l'ordre croissant...

  25. #20
    magodeoz

    Re : algorithmique permutations (ADA)

    Je pensais un truc du genre:
    im<-0
    X<- MinInt;
    Tant que (im=0) et i>LdeS
    if S.T(i)>X alors im<-i; Echanger (l'indice du plus petit entier de la séquence supérieur à MinInt et P(1))mais comment l'écrire....
    i<-i+1;
    Pour i de im à LdeS
    Si (S.T(i)) >X et S.T(i)<im)
    Echanger (P(S.T(i) et P(i)) mais ce que j'écris est faux car S.T(i) est la valeur dans la case et non l'indice...Bref je m'en sors pas ^^
    im<-i;
    retourner P;

    L'idée j'ai bien compris...Les notations beaucoup moins...
    Dernière modification par magodeoz ; 19/10/2012 à 17h41.

  26. #21
    kwariz

    Re : algorithmique permutations (ADA)

    Bon, on va partir de mon blabla :
    1. Évidemment on part avec la permutation identité P=[1,2,...,LdeS]
    2a. IPPS(S,P,MinInt) renvoie l'indice I1 dans P du plus petit élément de S, comme c'est le plus petit c'est celui qui devra être en première position dans P ===> on échange P(I1) et P(1)
    2b. IPPS(S,P,I1) revoie l'indice I2 dans P de plus petit élément de S mais plus grand que S.P[I1], c'est-à-dire le deuxième plus petit ====> on échange P(I2) et P(2)
    2c. IPPS(S,P,I2) revoie l'indice I3 dans P de plus petit élément de S mais plus grand que S.P[I2], c'est-à-dire le troisième plus petit ====> on échange P(I3) et P(3)
    ... ainsi de suite ...

    Le 1 ne pose pas de problème : c'est l'initialisation de la permutation P pour accéder aux entiers de S dans l'ordre de S

    Tu remarqueras que tous les deux se ressemblent fortement, on fait un appel à IPPS avec S et P et une valeur issue de la ligne qui précéde (ou MinInt la première fois) et on fait un échange avec P[1] la première fois, P[2] la seconde etc ...
    ==> c'est une boucle.

    On va certainement avoir quelque chose du genre :
    Code:
    P = [1,2, ..., LdeS]
    valeur_min = MinInt
    pour i de 1 à <à déterminer> faire
      indice_min = IPPS(S,P,valeur_min)
      échanger P[i] et P[indice_min]
      valeur_min=S.P[i]
    fin pour
    Les petits trucs :
    la première valeur min est initialisée avant la boucle
    la boucle utilisée est une boucle for
    En effet, on manipule une séquence d'entiers particulière, elle ne contient pas la valeur MinInt, elle ne contient pas doublons, la longueur de la séquence est connue. Parfois le plus difficile est de déterminer quand on s'arrête (le <à déterminer> en vert. On peut facilement prouver (le peux-tu en utilisant un invariant de boucle ?) qu'il va falloir LdeS-1 passage, on peut s'en convaincre en remarquant qu'à la fin de l'itération i, la permutaion représente la séquence triée entre 1 et i, tous les éléments de i+1 à LdeS étant plus grands que ceux entre 1 et i ...
    il ne faut pas oublier de donner à valeur_min la valeur du dernier minimum rencontré.

    C'est je pense l'approche la plus directe. Il y en a une autre que tu peux explorer (si tu en as l'envie ou le temps) : utiliser une boucle while sans utiliser LdeS. Dans les grandes lignes il faut penser à exploiter le fait que IPPS renvoie 0 quand il n'y a pas de plus petit élément plus grand que le paramètre (cela ressemble à une condition d'arrêt ...). Mais essaye déjà de comprendre et de refaire l'approche directe.
    Dernière modification par kwariz ; 19/10/2012 à 18h24.

  27. #22
    magodeoz

    Re : algorithmique permutations (ADA)

    Alors ça... les invariants d'itération c'est vraiment le truc que je mets en 1er position dans ce qui me dépasse en algo ada ^^
    Par exemple dans la fonction afficherenordre , il était demander de donner l'invariant de l'itération principale.J'ai passé cette partie de la question car j'étais incapable de trouver l'invariant ...
    On peut facilement prouver (le peux-tu en utilisant un invariant de boucle ?) qu'il va falloir LdeS-1 passage, on peut s'en convaincre en remarquant qu'à la fin de l'itération i, la permutation représente la séquence triée entre 1 et i, tous les éléments de i+1 à LdeS étant plus grands que ceux entre 1 et i ...
    il ne faut pas oublier de donner à valeur_min la valeur du dernier minimum rencontré.
    Néanmoins j'ai bien compris tout ce paragraphe.

    Code:
    P = [1,2, ..., LdeS]
    valeur_min = MinInt
    pour i de 1 à LdeS -1 faire
      indice_min = IPPS(S,P,valeur_min)
      échanger P[i] et P[indice_min]
      valeur_min=S.P[i]
    fin pour
    C'est fou comme ça paraît simple une fois que tu l'as fait... Merci à toi

    (si tu en as l'envie ou le temps)utiliser une boucle while sans utiliser LdeS.
    ça va j'ai les 2 Oui boucle while comme dans ma fonction IPPS initiale.
    Dernière modification par magodeoz ; 19/10/2012 à 18h47.

  28. #23
    magodeoz

    Re : algorithmique permutations (ADA)

    Petite question....L'invariant d'itération doit être vrai avant et après la boucle for c'est bien ça?

  29. #24
    kwariz

    Re : algorithmique permutations (ADA)

    Oui, avant, après et aussi pendant ... L'invariant c'est ce qui te permet de prouver que la boucle "fait effectivement" ce qu'elle est "censée faire", il n'est pas toujours évident de trouver le bon

  30. Publicité
  31. #25
    magodeoz

    Re : algorithmique permutations (ADA)

    Je ne peux que confirmer ^^Vu comme je galères à chaque fois....
    Il existe une méthode pour les trouver?
    L'invariant ce ne serait pas la séquence S elle-même puisqu'on ne la modifie pas dans cette action?

    PS: Je me reconnecterais demain matin. J'espère que vous serez disponible. Comprendre une approche pour déterminer les invariants me serait très utile...A commencer pour enfin trouver celui de la fonction AfficherEnOrdre. J'ai un peu de mal à me représenter ce que c'est. Je sais que ça peut concerner un indice, une somme...Exemple un indice pair ou impair.... Mais est-ce que ça peut concerner toute une séquence?

    Encore merci de ton aide.
    Dernière modification par magodeoz ; 19/10/2012 à 19h27.

  32. #26
    kwariz

    Re : algorithmique permutations (ADA)

    L'invariant est un prédicat que tu peux évaluer, et pas une variable. Qu'as-tu comme algo pour AfficherEnOrdre pour la partie 1 ?

  33. #27
    magodeoz

    Re : algorithmique permutations (ADA)

    Bonjour,
    Pour AfficherEnOrdre:
    Code:
    i<-IPPS(S,MinInt)
    while IPPS (S,T(i))≠0 (on arrête d'écrire quand on n'a plus de supérieur.)
        Ecrire (TdeS(IPPS(S,T(i)))
     i<-IPPS(S,T(i))
    fin while

  34. #28
    kwariz

    Re : algorithmique permutations (ADA)

    Bonjour,

    je parlais du début de l'énoncé qque tu posté un peu plus haut ... la version sans permutation.
    Pour AfficherEnOrdre avec la permutation c'est un peu trivial. Ce que tu cherches à démontrer est que AfficherEnOrdre affiche tous les éléments de la séquence du plus petit au plus grand. Un invariant possible serait (en rajoutant un compteur pour la démo)

    Inv(S,T,i, compteur) = (i=0 et compteur=LdeS) ou (i!=0 et S[T[i]] est le plus petit élément de S non encore affiché)
    La dernière partie peut aussi être énoncée comme
    "i!=0 et tous les éléments de S plus petit que S[T[i]] ont été affichés"
    "i!=0 et S[T[i]] est plus grand que le dernier affichage"
    Cela se montre par récurrence par exemple.

    Inv(S,T,i,compteur) doit être vérifé aux endroits suivants :
    Code:
    i<-IPPS(S,MinInt)
    compteur<-0
    *** si S est vide, i vaut 0 et compteur=LdeS=0 : vrai
    *** sinon i!=0, S[T[i]] est le plus petit élément de S, comme aucun n'a encore été affiché : vrai
    while IPPS (S,T(i))≠0 (on arrête d'écrire quand on n'a plus de supérieur.)
      Ecrire (TdeS(IPPS(S,T(i)))
      i<-IPPS(S,T(i))
      compteur<-compteur+1
    *** ici on a affiché quelque chose, 
    *** soit i=0, à toi de montrer que compteur=LdeS
    *** soit i!=0, à toi de montrer la seconde partie du prédicat Inv
    fin while
    *** ici on est sûr que i=0, à toi de montrer que compteur=LdeS
    Ici on assume beaucoup ... il y a beaucoup de propriété de IPPS à montrer avant (entre autre qu'itérer IPPS aboutit forcément à 0 .... gage de terminaison de l'algorithme AfficherEnOrdre)

  35. #29
    magodeoz

    Re : algorithmique permutations (ADA)

    Merci pour tout kwariz Je vais tâcher de montrer que l'invariant est vrai aux différentes étapes J'aurai jamais pensé à introduire un compteur comme ça... Va falloir que je m'entraîne sur les invariants ^^
    Y a quelque chose que je ne comprends pas par contre....
    je parlais du début de l'énoncé qque tu posté un peu plus haut ... la version sans permutation.
    La version que j'ai donné ,c'est celle sans permutation.J'ai mal réécris en fait....
    Code:
    i <- IPPS(S,minInt)
    Ecrire S.T(i)
      while IPPS(S , S.T(i) )/= 0 (different lol )
         Ecrire (S.T(IPPS(S , S.T(i) )
             i<- IPPS(S , S.T(i) );
    fin du while

  36. #30
    kwariz

    Re : algorithmique permutations (ADA)

    S.T(i) c'est quoi ? la valeur de l'entier à l'indice i dans la séquence S ???

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. ADA se trompe ???
    Par jameswell dans le forum Programmation et langages, Algorithmique
    Réponses: 0
    Dernier message: 14/06/2012, 17h40
  2. permutations
    Par Snowey dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 28/05/2012, 13h25
  3. Permutations
    Par jerome_010 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 14/12/2009, 11h39
  4. Nombre de lettres (ada)
    Par delphinounette dans le forum Internet - Réseau - Sécurité générale
    Réponses: 3
    Dernier message: 08/12/2005, 18h40
  5. petit pb avec ADA ..
    Par Yuna66 dans le forum Logiciel - Software - Open Source
    Réponses: 2
    Dernier message: 04/01/2005, 22h01