Corrigé C25.  Enoncé

A : Exercice 1 : Mise à jour sur vecteur

I. Structure de donnée

Un élément du vecteur est défini comme suit :
    TYPE Type_element = STRUCTURE
        Val : Typequelconque
        Sup : Booleen
    FIN
    VAR V : TABLEAU[1..M] DE Type_element

II. Initialisation

Vecteur :
    POUR I = 1, M DIV 2 :
        LIRE( V(I).Val )
        V(I).Sup := FAUX
    FINPOUR

Variables globales :

    N := M div 2     Taille initiale du sous vecteur
    NSup := 0         Nombre de suppressions logiques (trous)
    Ndon := M div 2    Nombre de données présentes
   
Module de recherche d'une valeur v donnée

Nous l'écrivons sous la forme d'une fonction : SI v existe, R est son indice dans V SINON R = 0.
   
    I := 1 ; Trouv := FAUX
    TANTQUE I <= N ET NON Trouv :
        SI Non V(I).Sup ET V(I).Val = V : Trouv := VRAI
        SINON I := I + 1 FSI
    FINTANTQUE
    SI Trouv : R := I SINON R := 0 FSI

Module d'insertion d'une valeur v après une Valeur v' de V

    SI R(V') = 0 ou N = M :
        " Insertion impossible"
    SINON
        POUR I = N, R(V')+1 , -1 :
            V(I+1) := V(I)
        FINPOUR
        V( R(V')+1) := (V, FAUX)
        N := N + 1
        Ndon := Ndon + 1
    FSI

Module de suppression d'une valeur v

    SI R(v) = 0 :
        " suppression impossible"
    SINON
        V( R(v) ).Sup := VRAI /* suppression logique */
        NSup := NSup + 1
        Ndon := Ndon - 1
        SI NSup > Ndon/3 : Recuperer ( V ) FSI
    FSI
   
Module Récuperer : éliminer les trous
   
    I := 1
    TANTQUE I <= N :
        SI V(I).Sup :
            POUR J = I+1, N : V(J-1) := V(J) FINPOUR
            N := N - 1
        SINON I := I + 1 FSI
    FINTANTQUE
    NSup := 0

Mesure

    t(R)    :     N/2 (comparaisons)
    t(I)    :    t(R) + N/2 affectations

Gain après le lancement de Récupérer :

Avant le lancement, parmi les N éléments du vecteur il y a 3/4 de données réellement présentes et 1/4 de données supprimés ( puisque Nsup = 1/3 (Ndon) + 1 ):

    N/2 - ( (3/4)N ) / 2 = N / 8

Exercice 2 : Représentation d'un tableau à 3 dimensions en mémoire

Ordre de rangement des éléments

    POUR I = 1, N
        POUR J = 1, M
            POUR K = 1, P
                ECRIRE ( I, J, K)
            FINPOUR
        FINPOUR
    FINPOUR


Formule donnant la position de T(i, j, K) dans le tableau T(1..N, 1..M, 1..P)

    (I-1)*(M*P) + (J-1)*P + K

Généralisation : position de T(i1, i2, .....in) dans le tableau T(1..N1, 1..N2, ....)

    (I1-1) * (N2*N3....*Nn) + (I2-1) * (N3*N4*.....*Nn) + .....(In-1 -1)*Nn + In.