Fouad NAFIS Filière : MP

December 23, 2024 Complexité algorithmique - Tris

Exercices Complémentaires : Complexité algorithmique et Tris

Exercice 01
Soit un tableau V de taille 10 et de type entier
1. Remplir V tel que chaque case contienne le carré de son indice.
0 1 2 3 4 5 6 7 8 9
V 0 1 4 9 16 25 36 49 64 81

2. Afficher V
3. Calculer et afficher la somme des éléments de V.
4. En déduire leur moyenne

Exercice 02
Soit un tableau de taille 20 et de type entier
1. Remplir les N premiers cases de V à partir du clavier. Afficher V. (N entier lu au clavier)
2. Déterminer et afficher le minimum et le maximum des éléments de V
3. Calculer et afficher la moyenne des valeurs ¿ 0 de V ainsi que la moyenne des valeurs paires de V.
4. Déterminer le maximum des valeurs paires de V ainsi que le minimum des valeurs impaires

Exercice 03
Soit un tableau V de taille 20 et de type entier.
1. Remplir les N premiers cases de V à partir du clavier. Afficher V.
2. Déterminer en un seul parcours de V le maximum de V ainsi que son nombre d’occurrences dans V.
3. Créer un tableau W tel que W(I) contienne le nombre d’occurrence de V(I) dans V.

Indication : un seul parcours : une seule boucle

Exercice 04
Une enquête a été réalisée apures d’un échantillon de N personnes (N <= 100) afin de déterminer des
statistiques sur les lieux et durées de vacances dans le pays.

1. Remplir un tableau V1 avec une liste de 10 villes du pays tel que 1-Rabat,2-Casa,3-Agadir,4-
Tanger,5-Fes,6-Meknes,. . . . . . ..10-Oujda. Afficher V1.
2. Remplir les tableau V2 et V3 tel que V2(I) contienne le n° de la ville visitée par les personnes I et
V3(I) la durée du séjour.
3. Afficher l’état suivante : N° personne Ville visitée Durée de séjour
4. Calculer la durée d’un séjour dans la capitale et la durée moyenne d’un séjour en dehors de la capitale.
5. Créer un tableau V4 tel que V4(I) contienne le nombre total des visiteurs de la ville I. Afficher V1
et V4.
6. Afficher les villes les plus visitées du pays.

Exercice 05
Écrivez un algorithme qui inverse l’ordre des éléments d’un tableau dont on suppose qu’il a été préalablement
saisi (”les premiers seront les derniers...”)

Programmation Python 1 fouadnafis@[Link]

Fouad NAFIS Filière : MP
Exercice 06
Écrivez un algorithme permettant, à l’utilisateur de saisir les notes d’une classe. Le programme, une
fois la saisie terminée, renvoie le nombre de ces notes supérieures à la moyenne de la classe.

Exercice 07
Écrivez un algorithme permettant à l’utilisateur de saisir un nombre quelconque de valeurs, qui devront
être stockées dans un tableau. L’utilisateur doit donc commencer par entrer le nombre de valeurs qu’il
compte saisir. Il effectuera ensuite cette saisie.
Enfin, une fois la saisie terminée, le programme affichera le nombre de valeurs négatives et le nombre
de valeurs positives.

Exercice 08
Écrivez un algorithme constituant un tableau, à partir de deux tableaux de même longueur préalablement
saisis. Le nouveau tableau sera la somme des éléments des deux tableaux de départ.
Tableau 1 :
4 8 7 9 1 5 4 6
Tableau 2 :
7 6 5 2 1 3 7 4
Tableau à constituer :
11 14 12 11 2 8 11 10

Exercice 09
Écrivez un algorithme qui trie un tableau dans l’ordre décroissant. Vous Écrirez bien entendu deux
versions de cet algorithme, l’une employant le tri par insertion, l’autre le tri à bulles.

Exercice 10
Écrivez un algorithme qui permette la saisie d’un nombre quelconque de valeurs. Toutes les valeurs
doivent être ensuite augmentées de 1, et le nouveau tableau sera affiché à l’écran.

Exercice 11
Ecrivez l’algorithme qui recherche un mot saisi au clavier dans un dictionnaire. Le dictionnaire est
supposé être codé dans un tableau préalablement rempli et trié.

Exercice 12
Écrivez un algorithme qui permette à l’utilisateur de supprimer une valeur d’un tableau préalablement
saisi. L’utilisateur donnera l’indice de la valeur qu’il souhaite supprimer.
Attention, il ne s’agit pas de remettre une valeur à zéro, mais bel et bien de la supprimer du tableau
lui-même ! Si le tableau de départ était :
12 8 4 45 64 9 2
Et que l’utilisateur souhaite supprimer la valeur d’indice 4, le nouveau tableau sera :
12 8 4 45 9 2
Programmation Python 2 fouadnafis@[Link]
Fouad NAFIS Filière : MP
Exercice 13
Écrivez un algorithme permettant, toujours sur le même principe, à l’utilisateur de saisir un nombre
déterminé de valeurs. Le programme, une fois la saisie terminée, renvoie la plus grande valeur en
précisant quelle position elle occupe dans le tableau. On prendra soin d’effectuer la saisie dans un
premier temps, et la recherche de la plus grande valeur du tableau dans un second temps.

Exercice 14
Écrire un algorithme se servant d’une fonction MOYENNE du type réel pour afficher la moyenne
arithmétique de deux nombres réels entrés au clavier.

Exercice 15
Écrire deux fonctions qui calculent la valeur X N pour une valeur réelle X (type réel) et une valeur
entière positive N (type Entier)

Exercice 16
1. Écrire la fonction NCHIFFRES du type Entier qui obtient une valeur entière N (positive ou
négative) du type Entier comme paramètre et qui fournit le nombre de chiffres de N comme résultat.
2. Écrire algorithme qui teste la fonction NCHIFFRES

Exemple:
Introduire un nombre entier : 6457392 Le nombre 6457392 a 7 chiffres.

Exercice 17
1. Écrire la fonction INSERER qui place un élément X à l’intérieur d’un tableau qui contient N
éléments triés par ordre croissant, de façon à obtenir un tableau à N+1 éléments triés par ordre crois-
sant. La dimension du tableau est incrémentée dans la fonction INSERER.

2. Écrire un algorithme profitant des fonctions définies plus haut pour tester la fonction INSERER.

Exercice 18
Écrire la fonction ECRIRE MATRICE à quatre paramètres MAT, L, C et CMAX qui affiche les
composantes de la matrice de dimensions L et C.

Exercice 19
Écrire une fonction estPremier(n) qui renvoie 1 si a est premier

Exercice 20
Écrire une fonction Somme permettant de calculer la somme S=1+2+3+...+N : N étant un entier
positif supérieur ou égal à 2. (Donner deux versions)

Exercice 21
Écrire une fonction prochain premier prenant un paramètre entier n et retournant le plus petit nombre
premier plus grand ou égal à n.

Programmation Python 3 fouadnafis@[Link]

Fouad NAFIS Filière : MP
Exercice 22
Écrire une fonction Convertir permettant de convertir un entier N pris en paramètre en une base B

Exercice 23
Écrivez un algorithme qui trie un tableau dans l’ordre décroissant.
Vous écrirez bien entendu deux versions de cet algorithme, l’une employant le tri par sélection, l’autre
le tri à bulles.

Exercice 24
Écrivez un algorithme qui permette de saisir un nombre quelconque de valeurs, et qui les range au fur
et à mesure dans un tableau. Le programme, une fois la saisie terminée, doit dire si les éléments du
tableau sont tous consécutifs ou non.

Exercice 25
Écrivez un algorithme qui fusionne deux tableaux (déjà existants) dans un troisième, qui devra être trié.

Attention ! On présume que les deux tableaux de départ sont préalablement triés : il est donc ir-
rationnel de faire une simple concaténation des deux tableaux de départ, puis d’opérer un tri : comme
quand on se trouve face à deux tas de papiers déjà triés et qu’on veut les réunir, il existe une méthode
bien plus économique (et donc, bien plus rationnelle...)

Exercice 26
Appliquer l’algorithme de tri à bulles ”à la main” au tableau ci-dessous :

1 6 9 82 1 4 1 6 9 82 1 4

Exercice 27
Soit TAB un tableau de N (N <= 100) entiers.
Écrire un algorithme qui permet de :
ˆ Remplir le tableau TAB.
ˆ Vérifier et afficher si le tableau est trié ou non dans l’ordre croissant.
ˆ Si le tableau est trié :
- Déterminer et afficher le plus grand nombre pair s’il existe.
- La moyenne des nombres positifs s’ils existent.

Remarques :

ˆ Le tableau TAB peut ne contenir aucun nombre pair. Dans ce cas, le message à afficher est : ”Aucun
nombre pair existe dans le tableau TAB”.
ˆ Le tableau TAB peut ne contenir aucun nombre positif. Dans ce cas, le message à afficher est :
”Aucun nombre positif existe dans le tableau TAB”.

Programmation Python 4 fouadnafis@[Link]