TP N°8
La Récursivité
Exercices
Ecrire les fonctions récursives suivantes :
1. Etant donné un entier n > 0, retourne 1+2+3+…+N
2. Etant donné 2 entiers n et m avec n>=0 et m>=0 retourne n + m
3. Etant donné 2 entiers n et m avec n>0 et m>0 retourne n * m
4. Etant donné 2 entiers n et m avec n>=0 et m>0 retourne pgcd(m, n)
5. Etant donné 2 entiers n et m avec n>0 et m>=0 retourne nm
6. Etant donné 2 entiers n,m>0 avec n<=m affiche n,n+1,n+2,...,m-1,m
7. Etant donné 2 entiers n,m>0 avec n<=m affiche m,m-1,...,n+1,n
8. Etant donné un entier n > 0, retourne la somme des chiffres de n
9. Etant donné un entier n > 0, retourne l'entier inverse de n. Exemple si n = 1245 cette fonction retourne 5421.
10. Etant donné 2 entiers n et k (k<=n), retourne le coefficient binomiale C(n, k). Le coefficient binomiale C(n, k) est le nombre de combinaisons possibles de k éléments à partir d'un ensemble de n éléments. Utiliser les propriétés: C(n, 0) = C(n, n) = 1 et C(n, k) = C(n-1, k) + C(n-1, k-1)
11. Etant donné un pointeur vers une chaine de caractères s, affiche cette chaine de caractères inversée (void reverse(char *s))
12. Etant donné une chaine de caractères détermine si cette chaine de caractères est un palindrome ou non (int palindrome(char s[], int i, int j))
13. Etant donné une chaine de caractères, vérifie si cette chaine de caractères est un mot carré c'est-à-dire de la forme ww (comme bonbon, chercher) (int motCarre(char s[], int i, int n))
14. Etant donné une chaine de caracteres s et un caractere c, retourne le nombre d'occurrences de c dans s.
15. Rechercher un caractère c dans une chaine de caractère s et retourne un pointeur vers la première occurence de c si c existe dans s; sinon retourne NULL
16. Duplique une chaine de caractères n fois. Exemple: repeterChaine("Hi", 3) retourne "HiHiHi".
17. Copy une sous chaine d'indice start et end d'une chaine de caractères s dans une autre chaine.
18. Copy une chaine de caractères dans une autre chaine mais en enlevant toutes les voyelles.
19. Etant donné un entier dont la valeur est exprimée en base 10, affiche la valeur correspondante en binaire (void decToBin(int n))
20. Etant donné une chaine de caractères représentant la valeur en binaire d’un entier, retourne la valeur en décimale de cet entier (int binToDec(char s[], int last))
21. Décomposer un nombre entier N en ses chiffres qui seront sauvegardés dans un tableau (void decToChiffres(int n, int A[], int *i))
22. Etant donné un entier détermine si cet entier est un nombre premier ou non (int isPrime(int num,int i))
23. Etant donné un tableau de nombres entiers non trie fait une recherche linéaire d’une valeur val dans le tableau (int search(int A[], int n, int val))
24. Etant donné un tableau de nombres entiers trie fait une recherche binaire (dichotomique) d’une valeur val dans le tableau (int recBinarySearch (int A[], int val, int lo, int hi))
25. Etant donné 2 tableaux d’entiers triés dans l’ordre croissant, A (de taille n<=50) et B (de taille m<=30), fait la fusionne de A et B dans un tableau C trié dans l’ordre croissant.
26. Etant donné un tableau de nombres entiers, détermine si les n premiers elements du tableau sont triés par ordre croissant (int isSorted(int A[], int n))
27. Etant donné un tableau quelconque de nombres entiers retourne le maximum des n premiers éléments de ce tableau.
28. Etant donné un tableau quelconque de nombres entiers retourne le minimum des n premiers elements de ce tableau.
29. Etant donné un tableau quelconque de nombres entiers retourne la somme des n premiers elements elements de ce tableau.
30. Etant donné un tableau quelconque de nombres entiers retourne le produit des n premiers éléments de ce tableau.
31. Etant donné un tableau quelconque de n nombres entiers inverse les elements de ce tableau.
32. Etant donné un tableau quelconque de n nombres entiers affiche tous les sous-tableaux (Exemple: Si T[1 2 3 4] alors on doit afficher [ 1 ] [ 1 2 ] [ 1 2 3 ] [ 1 2 3 4 ] [ 2 ] [ 2 3 ] [ 2 3 4 ] [ 3 ] [ 3 4 ] [ 4 ]). Utiliser fonction: void afficherTouslesSousTab(int V[], int N, int idx) où N est la taille du tableau et faire varier idx de 0 à N.
33. Etant donné un tableau quelconque de n nombres entiers implementer l'algorithme tri par fusion (merge sort): diviser chaque fois de manière recursive le tableau par 2 et fusionner (en ordonnant par ordre croissant) les 2 parties du tableau. Utiliser fonction: void mergeSort(int V[], int lo, int hi) qui sera appelée initialement avec mergeSort(V, 0, n - 1) où n est le nombre d'elements dans V.
34. Etant donné un tableau de n nombres entiers distincts affiche toutes les permutations des nombres du tableau. Idée: Fixer chacun des éléments du tableau en position 0 et permuter le reste du tableau de la même manière (récursivité en considerant les positions 1, 2, ..., n et on arrive à la base lorsqu'il reste un seul élément dans le tableau). On fixe chacun des éléments restant dans le tableau à une position id en permutant l'élément avec le 1er élément à la position id.
35. En utilisant la même idée que en 34) faire le tri par permutation d'un tableau quelconque d'entiers en faisant toutes les permutations possibles jusqu'a arriver à un tableau trié et afficher dans ce cas le tableau trié (et arrêter aussi les permutations).
36. Afficher les éléments d’une liste chainée de point d’entrée tete (void afficherListe(entList *tete)).
37. Affiche les éléments d'une liste chainée simple dans le sens inverse (void afficherListeInverse(entList *tete))
38. Recherche une valeur val dans une liste chainée simple (int rechercheListe(entList *tete, int val)).
39. Inverse une liste chainée de point d’entrée tete (entList *inverserListe(entList *tete)). La fonction sera appelée comme inverserListe(tete) et retournera la nouvelle tête (l'adresse de l'ancien dernier noeud).
40. Etant donnée 2 listes triées par ordre croissant, fusionne ces 2 listes (sans allocation) en une liste triée par ordre croissant.
41. Ecrire le main pour tester toutes ces fonctions