Exercices dirigés séance n04 – corrigé Tableaux, Méthode de construction par récurrence Exercice 1 : Le palindrome On appelle palindrome un mot qui se lit de la même façon de gauche à droite ou de droite à gauche par exemple rotor, elle. On souhaite écrire un programme qul teste si un mot est un palindrome ou non. Question 1 Ecrire l’algorithme qui détermine si un mot est un palindrome, en utilisant une méthode de construction de boucle par récurr Question 2 Traduire cet algorith complet.
Question 3 S. wp next page écrire le programme ?crire un programme java qui initialise un tableau de caractères, détermine si c’est un palindrome et affiche le résultat. Exercice 2 : Le tri par sélection L’idée du tri par sélection est de parcourir le tableau et à chaque étape de partitionner le tableau en un sous-tableau trié et un sous-tableau non trié, tel que tout élément du sous-tableau trié soit inférieur ou égal à tout élément du sous-tableau non trié.
Un tableau est trié si tout élément du tableau est inférieur ou égal à l’élément suivant; Le partitionnement se fait de la manière suivante : on recherche ‘élément minimum dans la partie non triée et on l’échange avec le premier élément de la partie non du tri par sélection.
On considèrera deux niveaux de raffinement : Parcours du tableau de gauche à droite : o Pour toute position dans le tableau 1- Rechercher l’élément minimum à partir de cette position , 2- Placer l’élément minimum à cette position On utilisera la méthode de construction par récurrence pour construire les boucles à chaque niveau Traduire cet algorithme en une fonction, puis écrire le programme Exercice 1 Solutions Algorithme ——Question 1
Idée : parcourir simultanément le tableau à partir de la gauche et à partir de la droite, tester s’il ya égalité des caractères correspondants, SI non ce n’est pas un palindrome, si oui poursuivre le parcours, itérer le test jusqu’au parcours complet du tableau. a) Hypothèse de récurrence Soit le tableau T, à chaque pas de récurrence, on a V ke [O.. i-l], b) Condition d’arrêt soit TC] et ce n’est pas un palindrome, soit et c’est un palindrome. c) Construire le corps de b 2 Initialisation ; ; // vérifie l’hypothèse qui devient un invariant {V kC [O.. -l], } ) Algorithme { V [O.. i-ll, tant que i System. out. println(« tapez le nombre d’entiers a trier int n = in. nextlnt(); int[] t = new int[n]; // saisie et affichage de la suite de nombres à trier System. out. println (« tableau a trier for (int i=O;i
