Corrigé C13. Enoncé

Exercice 1 : Parties d'un ensemble

    ALGORITHME Parties
    TYPE T = STRUCTURE
        Tete     : Pointeur(Typemaillon)
        Nb     : ENTIER
    FIN
    TYPE Typemaillon = Structure
        Val : ENTIER
        Adr : Pointeur(Typemaillon)
    FIN
    VAR Liste1, Liste2 : TABLEAU[1..N] DE T
    DEBUT
        LIRE(V)
        LIRE(N)
        ECRIRE({})
        POUR I=i, N
            Allouer(Typemaillon, Q)
            AffVal(Q, V(I) )
            AffAdr(Q, Nil)
            Liste1(I).Tete := Q
            Liste1(I).Nb := 1
            Imprimer(Q)
        FINPOUR
        N1 := N ; N2 := 0
        Aig := VRAI
        Long := 2 ; Compt := 1 + N
        TANTQUE N # 1 :
            POUR I=1, N :
                POUR J=I+1, N :
                    Union(Aig, I, J, L, Nb)
                    SI NON Exist(Aig, L) ET Long = Nb:
                        SI Aig :
                            N2 := N2 + 1
                            Liste2(N2).Tete := l
                            Liste2(N2).Nb := Nb
                        SINON
                            N1 := N1 + 1
                            Liste1(N1).Tete := l
                            Liste1(N1).Nb := Nb
                        FSI
                    FSI
                FINPOUR
            FINPOUR
            SI Aig :
                N1 := 0 ; N := N2
                POUR K:=1, N : Imprimer(Liste2(K).Tete FINPOUR
            SINON
                N2 := 0 ; N := N1
                POUR K:=1, N : Imprimer(Liste1(K).Tete FINPOUR
            FSI

            Aig := NON Aig
            Long := Long + 1
            Compt := Compt + 1
        FINTANTQUE
    FIN


Module Union :

    ACTION Union ( Aig, I, J, L, Nb)
    VAR
        Aig : BOOLEEN ;
        I,J,L, Nb : ENTIER
    DEBUT
        SI Aig :
            l1 := Liste1(I).Tete
            Nb1 :=Liste1(I).Nb
            L2 := Liste1(J).Tete
        SINON
            L1 := Liste2(I).Tete
            Nb1 :=Liste2(I).Nb
            L2 := Liste2(J).Tete
        FSI
       
        L := L1
        Nb := Nb1
        TANTQUE L2 # NIL :
            SI NON Recherche(Valeur(L2), L1)
                {Ajout au début de L1}
                Nb := Nb + 1
                Allouer(Typemaillon, Q)
                AffVal(Q, Valeur(L2))
                AffAdr(Q, L)
                L := Q
            FSI
            L2 := Suivant(L2)
        FINTANTQUE
    FIN

Module Exist

    ACTION (Aig, L)
    VAR
        Aig : BOOLEEN
        L , I: ENTIER
    DEBUT   
        I := 1
        Trouv := FAUX
        SI Aig :
            TANTQUE I <= N2 ET NON Trouv :
                SI Aig :
                    SI Egal(Liste2(I).Tete, Liste2(I).Nb, L, Nb) :
                        Trouv := VRAI
                    SINON I := I + 1
                    FSI
                FSI
            FINTANTQUE
        SINON
            TANTQUE I <= N1 ET NON Trouv :
                SI Aig :
                    SI Egal(Liste1(I).Tete, Liste1(I).Nb, L, Nb) :
                        Trouv := VRAI
                    SINON I := I + 1 FSI
                FSI
            FINTANTQUE
        FSI
        Exist := Trouv
    FIN


Module Egal

    ACTION EGAL (L1, Nb1, L2, Nb2)
    VAR
        L1, L2, Nb1, Nb2 : ENTIER
    DEBUT   
        SI Nb1 = Nb2 :
            Trouv := FAUX
            TANTQUE L2 # NIL ET NON Trouv :
                SI NON Recherche( Valeur(L2), L1) :
                    Trouv := VRAI
                SINON
                    L2 := Suivant(L2)
                FSI
            FINTANTQUE
            Egal := NON Trouv
        SINON
            Egal := FAUX
        FSI
    FIN


Module Recherche

    ACTION Recherche ( Val, L)
    VAR
        Val, L : ENTIER
        Trouv : BOOLEEN
    DEBUT
        Trouv := FAUX
        TANTQUE L # NIL ET NON Trouv :
            SI Valeur(l) = Val :
                Trouv := VRAI
            SINON
                L := Suivant(L)
            FSI
        FINTANTQUE
        Recherche := Trouv
    FIN

Programmation

Se référer au programme P5.