Université de la Polynésie Française

Partiel Algo et programmation C Deug MIAS 2 Année 2002-03 Jeudi 17 Octobre

0. Modalités

1.Vous disposez de une heure,

2.vos documents personnels sont autorisés,

3.le barème est donné à titre indicatif et est susceptible d'être modifié.

1. Opérations sur UNE liste d’entiers

1.1. Ecrire, sous forme de pseudo-code, un algorithme de détection du premier entier divisible par 3 d’une liste d’entiers tab de taille longueur (env 2 pts)

Il s’agit de rendre la position de l’élément en question ou –1 si aucun élément ne correspond.

1.2. Ecrire, sous forme de pseudo-code, un algorithme de suppression, en place du dernier élément pair d’une liste d’entiers tab de taille longueur (env. 3 pts)

Il s’agit bien de faire « disparaître » l’élément en question et donc d’obtenir une liste de taille longueur –1.

1.3. Ecrire, sous forme de pseudo-code, un algorithme de comptage du nombre d’entiers apparaissant plus d’une fois dans une liste d’entiers positifs tab de taille longueur (env. 5 pts)

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, 15 et 4 apparaissent plus d’une fois

2. Opérations sur DEUX listes d’entiers

2.1. Ecrire, sous forme de pseudo-code, un algorithme de fusion en copie de deux listes triées d’entiers tab1 de taille longueur1 et tab2 de taille longueur2 (env 6 pts)

Exemple : tab1 : 3 7 11 14 18 22

tab2 : 8 10 14 23 27 30 45

donne

tabres : 3 7 8 10 11 14 14 18 22 23 27 30 45

3. Faire tourner l’algorithme à la main

3.1. Donner, étape par étape, la valeur de la liste resultat pour la valeur ci-dessous de la liste tab (env 4 pts)

tab : 13 27 18 1 15 31 4 12

longueur : 8

donald <== 0

Répéter

minnie <== 0

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

si tab[i] < tab[minnie]

alors minnie <== i

        fin_de_répéter

        resultat[donald] <== tab[minnie]

        donald <== donald + 1

        Répéter pour i allant de minnie à longueur - 2

tab[i] <== tab[i+1]

fin_de_répéter

longueur <== longueur - 1

tant que (longueur > 0)