Algorithmes divers sur une ou plusieurs liste(s)

Algorithme de détection du premier entier divisible par 3 d'une liste d'entiers

/* tab de taille longueur */

i <== 0

Tant que (tab[i] non divisible par 3) ET (i < longueur)

i <== i + 1

fin_tantque

si tab[i] est divisible par 3

alors rendre i

sinon rendre -1

Algorithme de suppression, en place du dernier élément pair d'une liste d'entiers

/* Supprime le dernier éléments pair de tab (de taille longueur) dans tab elle même */

/* recherche du dernier entier pair */

i <== longueur -1

Tant que (tab[i] est impair) ET (i >= 0)

i <== i -1

fin_de_tantque

si i <> -1 /* la liste comporte bien au moins un élément pair */

alors

/* suppression de l'élément en question */

Répéter pour j allant de i à longueur - 1

tab[j] <== tab[j+1]

fin_de_répéter

longueur <== longueur - 1

Algorithme de comptage du nombre d'entiers apparaissant plus d'une fois dans une liste d'entiers positifs

/* tab de taille longueur ne contient que des entiers positifs ou nuls */

/* ATTENTION tab est modifiée !! */

resultat <== 0

Répéter pour i allant de 0 à longueur -1

        j <== i+1

        Tant que (tab[i] <> tab[j]) ET (j < longueur-1)

                j <== j + 1

        fin_de_tantque

        si tab[i] = tab[j]

        alors resultat <== resultat + 1

                /* Remplacement dans tab de toutes les occurences de tab[i] par un élément "bidon" (ici -1 car tab est une liste d'entiers positifs) */

                Répéter pour k allant de j à longueur - 1

                        si tab[k] = tab[i]

                        alors tab[k] <== -1

                fin_de_répéter

fin_de_répéter

rendre resultat

Exemples :

résultat = 0 pour tab : 3 7 11 14 18 22 car aucun entier n'apparaît plus d'une fois
résultat = 1 pour tab : 18 27 14 23 27 3 27 5 car seul 27 apparaît plus d'une fois
résultat = 3 pour tab : 10 15 10 15 22 4 4 25 78 car 10, 15et 4 apparaissent plus d'une fois

Algorithme de fusion en copie de deux listes triées d'entiers

/* tab1 et tab2 sont deux listes de longueurs respectives longueur1 et longueur2 */

indice1 <== 0

indice2 <== 0

long_res <== 0

Répéter pour i allant de 0 à longueur1 + longueur2 -1

si (tab1[indice1] < tab2[indice2]) ET (indice1 < longueur1)

alors res[i] <== tab1[indice1]

indice1 <== indice1 + 1

sinon si (indice2 < longueur2)

alors res[i] <== tab2[indice2]

indice2 <== indice2 + 1

sinon res[i] <== tab1[indice1]

indice1 <== indice1 + 1

fin_de_répéter

long_res <== i