Exercices de révision

Exercice 1 : Tri par sélection

L'algorithme de tri par sélection trie un tableau en trouvant de façon répétée l'élément minimum (en considérant l'ordre croissant) de la partie non triée et en le mettant au début. Pour un tableau donné l'algorithme maintient deux sous-tableau ( un sous-tableau trié et un non trié) .

Dans chaque itération de tri par sélection, l'élément minimum (dans l'ordre croissant) du sous-tableau non trié est prélevé et déplacé vers le sous-tableau trié. 

Exemple:


1- Ecrire une fonction swap qui permute deux éléments d’indice i et j dans un tableau donné T.
2- E
crire la fonction tri_selection.

Exercice 2 : Statistique d’une chaîne de caractère
1- Ecrire une fonction qui calcule le nombre de caractères, le nombre de voyelles, le nombre de chiffres et le nombre de mots d’une chaîne de caractère passée en argument.

Exercice 3 : Cube palindromique
1- Ecrire une fonction qui vérifie si un entier passé en argument est un palindrome. La fonction retourne 0 ou 1.
Exemple: 1221 est un palindrome.
2-  Ecrire une fonction qui détermine si un entier n est un cube palindromique. Un cube palindromique est un entier qui est à la fois un palindrome et un cube parfait.
Exemple: 
343 est un cube palindromique (343=7³ ).
                 1221 n'est pas un cube palindromique.
3- Ecrire un programme qui affiche les 6 premiers cube palindromiques.

Exercice 4 : La recherche dichotomique
La recherche dichotomique est un algorithme de recherche qui trouve la position d'une valeur cible dans un tableau trié. La recherche dichotomique compare la valeur cible à l'élément central du tableau.  S'ils ne sont pas égaux, la moitié dans laquelle la cible ne peut pas se trouver est éliminée et la recherche continue sur la moitié restante, en prenant à nouveau l'élément du milieu pour le comparer à la valeur cible.

1- E tant donné un tableau trié T de n éléments, écrire une fonction pour rechercher un élément donné x dans T. La fonction retourne l’indice de x ou -1 si x ne figure pas dans T.
2- Ecrire la forme récursive de la fonction.

Exercice 5 : Le triangle de Pascal
1- Etant donnée un nombre de ligne n, écrire la fonction qui retourne une matrice contenant les coefficients binomiaux du triangle de Pascal. Allouer dynamiquement l’espace mémoire nécessaire pour chaque ligne de la matrice.   
Exemple: Pour n égale à 5:

Exercice 6 : Les points-cols
1- Ecrire une fonction qui détermine les points-cols d’une matrice T. Les points-cols sont les éléments qui sont à la fois un minimum sur leur colonne et un maximum sur leur ligne.  La fonction affiche les valeurs et les positions de tous les éléments-cols trouvés.
Exemple: pour la matrice suivante:
|3  8  6  8|
|4  9  0  9|
|6  6  4  8|

Les points-cols : 8 en position [2,3] et 8 en position [0,3].

Exercice 7 : Fréquence des caractères.
1- Ecrire une fonction qui détermine la fréquence de chaque caractère d’une chaîne de caractère donnée.

Exercice 8 : Purger un tableau
1- Ecrire une fonction qui élimine les répétitions d'un tableau donné.
Remarque : ne pas utiliser un tableau intermédiaire.

Exercice 9 : Purger un tableau
1- Ecrire une fonction qui détermine si une chaîne S2 est incluse dans une chaîne S1. Elle retourne l'indice de la première occurrence de S2 dans S1 ou -1 (si S2 n'existe pas dans S1)
2- Déterminer si une chaîne S2 est incluse dans une chaîne S1 à partir d'une position K. Elle retourne l'indice de la première occurrence de S2 dans S1 (à partir de l'indice K) ou -1 (si S2 n'existe pas dans S1)
3- Ecrire une fonction qui supprime toutes les occurrences de S2 dans S1.

Modifié le: vendredi 27 décembre 2019, 13:29