Il s’agit d’un exercice du contrôle de L2 de cette année.
Énoncé
Écrire une fonction récursive qui permet d’insérer un nouvel entier v (obtenu en entrée) dans un tableau d’entiers trié (ordre croissant) T de taille N, de manière à conserver le tri.
- Le tableau
Ta une taille physique deN+1cases (la dernière case est libre pour l’insertion) - Exemple : Si
T = {1, 3, 5, 7, _}etv = 4, le résultat seraT = {1, 3, 4, 5, 7} - Ne pas utiliser de variable statique
- la fonction peut être sans valeur de retour (le résultat sera dans le tableau utilisé comme argument de fonction).
Solution 1
void decaler(int *t, int n){
if(n!=0){
t[n] = t[n-1];
decaler(t, n-1);
}
}
void inserer(int v, int *t, int n){
if(n==0 || v<*t){
decaler(t,n);
*t = v;
} else
inserer(v,t+1,n-1);
}
C’est la première solution à laquelle j’ai pensé. Elle utilise une fonction auxiliaire decaler() qui est elle aussi récursive (si l’on y met une boucle, la solution n’est plus entièrement récursive !).
Solution 2
void inserer(int v, int *t, int n){
if(n==0 || v>t[n-1])
t[n]=v;
else {
t[n]=t[n-1];
inserer(v,t,n-1);
}
}
Solution beaucoup plus succincte. Est-elle meilleure en terme de complexité également ?
Solution 3
void inserer_rec(int v, int *t, int n, int i){
if(i==n)
t[i] = v;
else {
inserer_rec(v, t, n, i+1);
if(t[i]>v){
t[i+1]=t[i];
t[i]=v;
}
}
}
void inserer(int v, int *t, int n){
inserer_rec(v,t,n,0);
}
Ici la fonction récursive est invoquée indirectement car elle comporte un paramètre supplémentaire i servant d’indice pour le parcours du tableau.
Solution 4
void inserer(int v, int *t, int n){
if(n==0)
t[0]=v;
else {
int v2=v;
if(t[0]>v){
v2=t[0];
t[0]=v;
}
inserer(v2,t+1,n-1);
}
}
Ici, contrairement à la solution 2, le décalage des éléments du tableau commence à la première case qui suit la position de la valeur insérée (et non à la dernière).
Cette solution et la suivante m’ont été inspirées par la copie de l’examen de contrôle de l’un de nos étudiants de L2 informatique.
Solution 5
void inserer_rec(int v, int *t, int n, int i){
if(i==n)
t[i] = v;
else {
int v2=v;
if(t[i]>v){
v2=t[i];
t[i]=v;
}
inserer_rec(v2, t, n, i+1);
}
}
void inserer(int v, int *t, int n){
inserer_rec(v,t,n,0);
}
Celle-ci ressemble à la solution 3, mais ici l’appel récursif n’est pas terminal. La récursivité terminale dans cette solution permettrait de paramétrer le compilateur pour éviter les dépassements de pile si le tableau était trop grand.
Pour tester
Voici un exemple de programme avec une fonction main() où vous pourrez mettre les fonctions d’une des solutions à tester :
#include <stdio.h>
#include <ctype.h>
#define MAX 10
// ... fonction inserer() à mettre ici
void afficher(int *t, int n){
if(n>0){
printf("%d ",*t);
afficher(t+1,n-1);
}
}
int main(void){
int n=0, t[MAX];
puts("Insertions dans un tableau trié");
char encore;
do{
printf("Donnez la valeur à insérer : ");
int v;
scanf("%d",&v);
inserer(v,t,n);
afficher(t,++n);
if(n<MAX){
printf("\nUne autre ? [o/n] ");
scanf(" %c",&encore);
} else {
printf("Maximum atteint (%d valeurs).\n",MAX);
encore='n';
}
}while(tolower(encore)=='o');
puts("Game over.");
}
Et avec une variable statique ?
Pourquoi l’énoncé dit-il de ne pas utiliser de variable statique ?
Peut-on utiliser une variable statique i pour éviter le paramètre supplémentaire dans les solutions 3 et 5 précédentes ?
Avec recherche dichotomique
Si le tableau est trié, ne vaut-il pas mieux chercher l’emplacement de la nouvelle valeur par dichotomie ? Cela améliorerait beaucoup la complexité…
(Mise à jour de l’article du 11/12/2012)
Introduction
Le C est un langage qui a été créé par Dennis Ritchie pour écrire un système d’exploitation. Les premiers programmes en C ont été ceux qui composent le système Unix. Celui-ci est connu pour être très modulaire, constitué de petits programmes qui font une seule tâche précise et communiquent entre eux à travers des fichiers, des tubes, des sockets etc. La conversation avec l’utilisateur n’est pas ce qui a de plus simple en C.
Problématique
En faisant des petits programmes comme ceux de nos TP, vous avez sûrement remarqué que pour demander à l’utilisateur un texte contenant des mots séparés par des espaces, cela pouvait poser des problèmes.
En effet, quand nous débutons en C, on nous dit souvent que pour lire une chaîne de caractères, on utilise scanf avec le code de format %s. C’est bien mais quand on essaie, on se rend compte que ça marche pour un mot, mais quand on en met deux avec une espace entre eux, le deuxième est ignoré par scanf. Pire, si on a un deuxième scanf, le deuxième mot va être récupéré par lui !
On se rend compte assez vite que cette façon d’utiliser scanf n’est pas la bonne méthode, non seulement pour la raison ci-dessus mais aussi parce que si l’utilisateur donne n’importe quoi, on perd le contrôle de notre programme.
Exemple :
char a[20], b[20] ;
printf("Donnez un mot : ");
scanf("%s",a);
printf("Un autre : ");
scanf("%s",b);
printf("1er : %d lettres, 2e : %d lettres\n",strlen(a), strlen(b)");
Si l’utilisateur tape : bonjour anticonstitutionnellement pour le premier mot, non seulement le programme n’attend pas le deuxième mot après avoir affiché « Un autre », mais, ce qui est encore plus grave, les lettres qui débordent de la chaîne b (qui n’est pas assez grande) vont provoquer un dépassement de tampon.
Si vous avez de la chance, et si vous avez un compilateur assez récent (GCC > 4.0) un message à l’exécution peut parfois vous prévenir du débordement (mais ça ne marche pas toujours) :
Donnez un mot : bonjour anticonstitutionnellement Un autre : 1er : 7 lettres, 2e : 25 lettres *** stack smashing detected ***: ./programme terminated Aborted (core dumped)
Autrefois, ce genre de problèmes pouvait faire planter votre PC…
Cherchons une solution
scanf avec %s
Une manière d’éviter ce genre de désagréments est de préciser la longueur maximale au code de format %s. Par exemple, scanf("%20s",... indique à scanf de ne prendre que les 20 premiers caractères de la chaîne introduite. Cela évite les débordements mais ne règle pas le problème des espaces, qui stoppent toujours la lecture de la chaîne.
scanf avec %c
On pourrait aussi utiliser le code de format %c. Quand on l’utilise seul, il ne permet de lire qu’un seul caractère, mais on peut lui préciser le nombre de caractères à lire. Par exemple, scanf("%20c",... lit tous les caractères, même les espaces et s’arrête au 20e. Un inconvénient de ce code format est que contrairement à %s, il n’ajoute pas tout seul le caractère nul de fin de chaîne, il faut le faire soi-même. Mais le plus gros problème c’est qu’il lit aussi les retours à la ligne générés par la touche Entrée, et ne s’y arrête pas, ce qui fait que dans l’exemple l’utilisateur est obligé de taper 20 caractères…
scanf avec %[^\n]
Cette solution est parmi les meilleures et les plus simples. Le code (ou spécificateur) de format %[] permet de lire des caractères en précisant entre les crochets [] quels sont ceux que l’on veut prendre ou, s’ils sont précédés d’un « chapeau » ^, ceux dont on ne veut pas. Ici ce sera le caractère \n de retour à la ligne qui ne sera pas pris et qui arrêtera la lecture par scanf.
Il faut pourtant savoir comment régler certains problèmes :
1er problème : si le premier caractère présent est une espace ou une tabulation ils ne seront pas ignorés et si c’est un retour à la ligne, la lecture s’arrêtera en laissant le \n et tout ce qui suit dans le tampon d’entrée.
Exemple : Supposons que l’on veuille lire un entier avant la chaîne de caractères ainsi:
scanf("%d",&nombre);
scanf("%[^\n]",chaine);
Si l’utilisateur tape un nombre puis la touche Entrée puis une chaîne de caractères, cela ne fonctionnera pas. Le premier scanf lit le nombre mais ne prend pas le \n (qui a été ajouté quand l’utilisateur a appuyé sur Entrée). Quand le deuxième scanf commencera la lecture il trouvera ce caractère et arrêtera sans avoir rien lu.
Ce qui se produit ressemble aux cas où on essaie de lire un nombre puis un caractère. Pour que cela fonctionne bien, on met une espace avant le %c pour ignorer les retours à la ligne (ainsi que les espaces et tabulations) comme ceci :
scanf("%d",&nombre);
scanf(" %c",chaine); // l'espace "consomme" le \n au début
Ici aussi, la solution peut être de mettre une espace ainsi :
scanf("%d",&nombre);
scanf(" %[^\n]",chaine);
Le même problème peut se produire si l’on veut lire deux chaînes de caractères. On pourra alors le faire comme ceci :
scanf(" %[^\n]",chaine1);
scanf(" %[^\n]",chaine2);
2e problème : plus grave, cette solution peut être dangereuse si le tableau de caractères dans lequel sera mise la chaîne lue n’a pas été déclaré avec une taille suffisante. L’arrêt de la lecture dépend du caractère de retour à ligne. S’il y a trop de caractères lus, c’est un dépassement de tampon.
Solution : comme précédemment avec %s on peut limiter le nombre de caractères lus avec scanf(" %20[^\n]",chaine); mais il faut prévoir la place pour le caractère nul de fin de chaîne '\0'. Celui-ci sera ajouté après la lecture de la chaîne, il faut donc que le nombre de caractères lus soit moins grand que la taille déclarée du tableau de caractères.
Exemple :
char chaine[21];
scanf(" %20[^\n]",chaine); // lit au maximum 20 caractères
// (le 21e contiendra alors '\0')
3e problème : Dans la solution ci-dessus, si l’utilisateur a tapé trop de caractères, la lecture s’arrête en laissant les caractères qui restent dans le tampon d’entrée. Si un autre scanf veut ensuite lire une autre chaîne (ou simplement un caractère), il trouvera les caractères laissés par le scanf précédent et il les prendra sans attendre l’utilisateur.
Exemple :
char chaine1[21], caractere, chaine2[21];
scanf(" %20[^\n]",chaine1);
scanf(" %c",&caractere);
scanf(" %20[^\n]",chaine2);
Cela fonctionnera bien si l’utilisateur tape par exemple :
bonjour Z au revoir
Mais pas s’il donne :
anticonstitutionnellement
Dans ce cas, chaine1 prendra le début de mot "anticonstitutionnell" (20 caractères) et le programme ne s’arrêtera pas pour attendre que l’utilisateur tape un caractère puis une autre chaine : caractere prendra directement la valeur 'e' et chaine2 contiendra le reste du mot : "ment".
L’espace avant le % dans les deux derniers scanf était nécessaire dans le premier exemple, pour ignorer les retours à la ligne après "bonjour" et après 'Z', mais il n’a pas permis d’éliminer le surplus ("ement\n") dans le 2e exemple, puisqu’il était constitué de lettres.
Solution : Pour éliminer tous les caractères qui n’ont pas été lus par le premier scanf (ainsi que le '\n' à la fin de la ligne), on peut utiliser une boucle qui répète la lecture d’un caractère jusqu’à ce qu’elle lise le caractère de retour à la ligne. On peut utiliser pour cela la fonction getchar() en testant son résultat :
char chaine1[21], caractere, chaine2[21];
scanf(" %20[^\n]",chaine1);
while(getchar()!='\n')
;
scanf("%c",&caractere); //pas besoin d'espace avant %c ici
scanf(" %20[^\n]",chaine2);
Remarque : Vous trouverez peut-être une (fausse) solution à ce dernier problème sur certains sites web qui permettrait de vider le tampon d’entrée avec la fonction fflush() de la bibliothèque standard. En réalité, la fonction fflush() ne doit être utilisée que pour vides les tampons de sortie, pas ceux d’entrée. Cela ne fonctionne généralement pas, et ce n’est pas dans la norme du C.
gets : le bug de la bibliothèque standard
La bibliothèque standard fournit des fonctions spécialement faites pour les chaînes de caractères. La plus simple était gets. Simple oui, mais boguée ! Enfin, c’est ce que disait même son propre manuel (qui déconseillait son utilisation). En fait, gets avait le même « bug » que scanf utilisé avec "%s" ou avec "%[^\n]": si l’utilisateur donne une chaîne trop longue pour la variable, on obtient un dépassement de tampon. Cela a constitué des failles de sécurité dans tellement de programmes que cette fonction a été supprimée du langage C depuis la norme C11 de 2011 (auparavant elle était qualifiée d’obsolète). Elle n’existe plus dans la bibliothèque standard fournie avec les compilateurs récents, qui donnent un message d’erreur si on essaie de l’utiliser.
fgets
Une fonction plus intéressante est fgets, qui a parmi ses paramètres la taille de la chaîne à lire, ce qui permet, comme dans l’exemple avec scanf("%20s",..., de limiter le nombre caractères lus. Comme scanf("%c"... mais contrairement à scanf("%s"..., fgets lit les espaces et continue aux mots qui les suivent, et lit le retour à la ligne donné par la touche Entrée. Cependant, fgets arrête la lecture après le retour à la ligne et ajoute un caractère nul de fin à la chaîne.
Exemple :
char chaine[81]; // 80 caractères + '\0' terminal
printf("Donnez une phrase (pas plus de 80 car.) : ");
fgets(chaine, 81, stdin);
chaine[strlen(chaine)-1]='\0'; //enlève le '\n'
Remarques :
fgets est faite pour lire une chaîne depuis un fichier, mais en C la lecture d’une chaîne saisie au clavier revient à lire l’entrée standard stdin, qui est vue par le programme comme un fichier.
Nous avons mis 81 pour la taille de la chaîne en paramètre de fgets. C’est pour pouvoir lire 80 caractères, car fgets réserve toujours le dernier pour le caractère nul de fin.
La dernière ligne permet de supprimer le caractère de retour à la ligne qui a été lu par fgets. Il y aura deux caractères nuls après le dernier caractère de la phrase lue mais de toute façon, avec les chaînes tout ce qui se trouve après un caractère nul est toujours ignoré.
Cette fonction est assez satisfaisante mais il reste un inconvénient : la taille de la variable qui recevra la chaîne de caractères doit être fixée à l’avance. On ne sait jamais vraiment combien réserver pour optimiser la mémoire utilisée.
Allocation dynamique
Dans le cas où l’on veut demander plusieurs chaînes à l’utilisateur, un moyen simple d’économiser de la mémoire consiste à suivre les étapes suivantes :
- lire ces chaînes dans une variable commune « tampon » (appelons-là
buffer), qui va resservir pour chaque chaîne ; - une fois la chaîne lue, nous pourrons savoir quelle taille lui réserver en mémoire, en utilisant une fonction d’allocation dynamique ;
- après avoir transféré la chaîne dans l’espace alloué dynamiquement,
bufferpeut être utilisé pour la chaîne suivante, on répète donc l’opération pour toutes les chaînes.
Exemple :
for (int i=0; i<n; i++) {
printf("Nom %d : ",i+1);
char buffer[TAILLE_BUFFER];
fgets(buffer, TAILLE_BUFFER, stdin);
buffer[strlen(buffer)-1]='\0'; // enlève le '\n' à la fin
nom[i]=malloc(strlen(buffer)+1);
if (nom[i] == NULL) {
fputs(stderr,"Erreur d'allocation mémoire");
exit(EXIT_FAILURE);
}
strcpy(nom[i], buffer);
}
Nous avons appelé malloc() sans utiliser sizeof, car sizeof(char) vaut toujours 1 par définition. Mais on aurait aussi bien pu faire :
nom[i]=calloc(strlen(buffer)+1,sizeof(char));
N’oubliez pas de réserver un caractère pour le caractère nul de fin de chaîne, car strlen() ne le compte pas.
N’oubliez pas de considérer le cas où malloc() n’arrive pas à allouer assez de mémoire. Ça peut toujours arriver et si vous ne le prévoyez pas, vous risquez de gros ennuis.
Ici, nous avons choisi dans ce cas d’afficher (fputs) un message sur la sortie d’erreurs standard (stderr). Puis de terminer le programme (exit()) en renvoyant un code de sortie qui indique qu’une erreur s’est produite (EXIT_FAILURE). Vous pourriez réfléchir à un traitement des erreurs plus sophistiqué.
N’oubliez pas non plus de faire le ménage quand vous en aurez terminé avec ces chaînes de caractères : vous leur avez réservé de l’espace, il faudra le libérer vous-même, en appelant free() autant de fois que vous avez appelé malloc() (un appel pour chacune des chaînes du tableau, dans une boucle for par exemple).
Cette solution est assez simple mais n’est pas la meilleure : on se pose toujours la question de déterminer la bonne valeur pour la constante TAILLE_BUFFER.
Solution « fait-main »
Nous allons construire une fonction qui permet de lire une chaîne en résolvant les problèmes que l’on vient de voir.
Puisque l’on veut optimiser la taille de la mémoire utilisée, on doit bien sûr allouer la chaîne dynamiquement.
Ne sachant pas quelle sera la taille de la chaîne, nous allons utiliser realloc() pour l’agrandir au fur et à mesure.
Mais attention, j’ai vu un étudiant faire une boucle qui lisait chaque caractère de la chaîne et à chaque itération appelait realloc() en incrémentant la taille allouée de 1 octet. C’est un très bon raisonnement mais c’était quand même une mauvaise idée : realloc() est une fonction lourde qui ralentit l’exécution, et l’appeler de façon répétée ainsi n’est pas très malin si l’on veut optimiser notre code.
La solution adoptée par de nombreux programmeurs consiste à faire croître la taille du buffer non pas de façon arithmétique, mais de manière géométrique, en la faisant tout simplement doubler à chaque fois qu’il est plein.
/* lire_chaine : affiche un message et lit une chaine de
* caractères (avec allocation dynamique)
* Paramètre :
* - message : invite à afficher
* Résultat : retourne l'adresse de la chaîne créée
* dynamiquement contenant le texte lu ou NULL en cas
* d'échec.
*/
char * lire_chaine(char * message){
printf("%s", message);
size_t taillbuff = MIN_BUFFER;
char *buffer = malloc(taillbuff);
if (buffer == NULL) return NULL; // échec de malloc()
char *p;
for(p=buffer ; (*p=getchar()) != '\n' && *p!=EOF ; ++p)
if (p - buffer == taillbuff - 1) { // buffer plein,
p = realloc(buffer, taillbuff *= 2); //on le double
if (p == NULL) { // échec de realloc()
free(buffer);
return NULL;
} else buffer = p; //bloc réalloué != buffer
p += taillbuff/2 - 1; // p reprend sa place dans
} // la nouvelle zone
*p = 0;
p = realloc(buffer, p - buffer + 1); //réajustement
if (p == NULL) { // échec de realloc
free(buffer);
return NULL;
} else return p;
}
Remarques :
- La taille initiale
MIN_BUFFERpeut être choisie à 7 ou 8 par exemple. - La fonction
getchar()lit un caractère à la fois. realloc()est une fonction à utiliser avec précaution : pour pouvoir changer la taille de la zone allouée, il lui arrive souvent de déplacer cette zone vers un autre endroit de la mémoire, c’est pourquoi elle renvoie en résultat la nouvelle adresse. Non seulement l’ancienne adresse qui lui a été transmise en paramètre n’est plus valide, mais s’il reste des pointeurs qui pointaient vers une partie de l’ancienne zone, il faut les mettre à jour pour qu’ils pointent sur la nouvelle zone.
Dans une première version de cette fonction, j’ai omis ce détail et cela ma coûté quelques soucis.
- Puisque cette fonction fait une allocation dynamique, il ne faudra pas oublier de libérer avec
free()la mémoire pointée par sa valeur de retour une fois que la chaîne lue n’est plus utilisée.
Références
Méthodologie de la programmation en C Norme C 99 – API POSIX Achille Braquelaire Collection: Sciences Sup, Dunod 2005 – 4ème édition EAN13 : 9782100490189. Disponible aux bibliothèques de l’EPST (Bel-Horizon) et de la faculté des Sciences (Chetouane).
Pages de manuel : scanf(3), gets(3), malloc(3). Disponibles en tapant la commande man 3 <fonction>.
Here are two exercises on recursion in C:
Exercise 1
Write a recursive function that calculates xn (with x real, and n integer, n can be negative)
Exercise 2
Write a recursive function that displays a given natural number from right to left.
e.g.: n=12345 ==> displays « 54321 »
(The number must be displayed, not returned)
Solutions
Exercise 1
It is the same principle as the recursive function that calculates the factorial. The recursive way to define the power operation is:
- for any strictly positive value of n, xn = x.xn-1
- if n is zero, we know that x0 = 1
- if n is negative, there is a simple way to calculate it: xn = 1/x-n
So here is the function written in C:
double power(double x, int n){
if (n>0)
return x*power(x,n-1);
else if (n==0)
return 1;
else // n<0
return 1/power(x,-n);
}
Or just with a one-line statement, using the conditional operator:
double power(double x, int n){
return n>0 ? x*power(x,n-1) : n<0 ? 1/power(x,-n) : 1;
}
Exercise 2
To display the digits of a number in the reverse order, we can use this recursive algorithm:
- display the last digit of the number first
- then, display in the reverse order the number which results from removing the last digit
e.g.:
- To display the number ‘123’ from right to left:
- display ‘3’
- then, display the number ’12’ from right to left
- To display the number ’12’ from right to left:
- display ‘2’
- then, display the number ‘1’ from right to left
- To display the number ‘1’ from right to left:
- display ‘1’
- then… nothing <== if the number had only one digit, do nothing
We notice that the terminating condition is n<10 (which means n has only one digit) and in that case, we do nothing after printing the (last) digit.
Let's write the function in the C language now:
void display_reversed(int n){
printf("%d",n%10); // the last digit
if (n>=10) // n has more than 1 digit
display_reversed(n/10); // with last digit removed
}
Other solution
A student sent me his solution which looks like:
void display_reversed(int n){
if (n!=0){
printf("%d",n%10);
display_reversed(n/10);
}
}
It works well for almost all the cases. Can you figure out the issue of this solution?
The issue here is that his solution doesn’t work if n is zero.
It comes from the terminating condition that he chose: n=0.
If n>0 the successive recursive calls will divide it by 10 each time and when the result reaches the zero value, it will stop. That zero must not be printed because it is not a digit of the number.
But in the case where n is zero from the start, that zero must be printed, which his function doesn’t do.
Voici un exercice à faire en langage C pour les étudiants de première année qui fait suite au cours sur les structures de contrôle conditionnelles (instructions de test).
Énoncé
Écrire un programme qui demande à l’utilisateur un nombre entier positif inférieur à 100000 puis :
1. affiche la somme de ses chiffres
2. affiche le nombre à l’envers (de droite à gauche).
Attention: Votre programme ne doit ni contenir des boucles ni définir des fonctions autres que main().
Solutions
Comme toujours, ne regardez pas la solution si vous n’avez pas encore essayé de résoudre l’exercice par vous-même.
Le principe de la solution à cet exercice est simple : pour obtenir les chiffres d’un nombre, on peut utiliser le fait que la division entière par 10 supprime le dernier chiffre d’un nombre et que le reste de la division est le dernier chiffre.
Voici un programme qui donne une solution pour la question 1 et deux solutions pour la question 2 :
#include <stdio.h>
int main() {
printf("Entrez un entier positif n < 100000 : ");
int n;
scanf("%d",&n);
if(n<0 || n>99999) {
printf("Erreur!");
return 1;
}
int a=n/10000, b=n/1000%10, c=n/100%10,
d=n/10%10, e=n%10;
printf("Somme des chiffres : %d\n",a+b+c+d+e);
printf("Nombre à l'envers (1re méthode) : ");
printf("%d",e);
if(n>9) {
printf("%d",d);
if(n>99) {
printf("%d",c);
if(n>999) {
printf("%d",b);
if(n>9999)
printf("%d",a);
}
}
}
printf("\nNombre à l'envers (2e méthode) : ");
int envers=n%10;
if((n/=10)>0) {
envers=envers*10+n%10;
if((n/=10)>0) {
envers=envers*10+n%10;
if((n/=10)>0) {
envers=envers*10+n%10;
if((n/=10)>0)
envers=envers*10+n; //ici n%10 = n
}
}
}
printf("%d\n",envers);
}
Les expressions utilisées comme conditions dans les if de la 2e méthode ((n/=10)>0)modifient la valeur de n en la divisant par 10 et vérifient si le résultat est différent de zéro. Comme ce sont des if imbriqués, la première division par 10 qui donnera 0 entraînera la sortie des if. On voit clairement comment on aurait pu obtenir la même chose en utilisant une boucle puisque les mêmes instructions se répètent tant que n est différent de zéro.
Voici un exercice à faire en langage C pour les étudiants de première année qui fait suite au cours sur les structures de contrôle conditionnelles (instructions de test).
Écrire un programme qui demande à l’utilisateur la date et l’heure au format JJ/MM/AAAA – HH:MM:SS puis qui ajoute une seconde et affiche le résultat (au même format).
Exemple 1 : 30/10/2025 – 08:30:15 –> 30/10/2025 – 08:30:16
Exemple 2 : 31/12/2025 – 23:59:59 –> 01/01/2026 – 00:00:00
Remarque : reprenez le raisonnement de l’exercice 4 (validité de la date) de la fiche de TP 2.
Voici la fiche de TP supplémentaire sur les structures de contrôle conditionnelles que j’ai donnée à faire aux étudiants du groupe B2 qui avaient terminé la fiche de TP 2 (le jour du test) :
Voici les 4 sujets de test de TP du groupe B2:
Voici un exercice à faire en langage C pour les étudiants de première année qui fait suite au cours sur les structures de contrôle conditionnelles (instructions de test).
Un « palindrome » est un mot qui s’écrit pareil à l’endroit et à l’envers.
Exemples : RADAR, KAYAK, ELLE, BOB
Écrire un programme qui demande à l’utilisateur un mot de 3 à 5 lettres puis l’affiche à l’envers ou, si c’est un palindrome, affiche « Ce mot est un palindrome ».
Attention: Votre programme ne doit ni contenir des boucles ni définir des fonctions autres que main().
Essayez d’abord de trouver la solution sans aide. Si vous n’y arrivez pas, voici un fichier PDF qui contient des indications pouvant vous aider :
Enoncé de l’exercice
Ecrire une fonction récursive en C qui détermine si tous les éléments d’un tableau sont distincts (c’est-à-dire que le tableau ne contient aucun élément répété).
Paramètres et valeur de retour
Données en entrée
Pour moi, cette fonction ne devrait avoir que 2 paramètres : le tableau et sa taille
Résultat
Le résultat renvoyé doit être une valeur logique, booléenne, ce qui peut être 0 ou 1 en langage C.
Solution vue en cours
#include <stdio.h>
int distinctValues_rec(int tab[], int i, int j, int n)
{
if(i==n-1) return 1; // cas d’arret
if(j==n) return distinctValues_rec(tab, i+1, i+2, n) ;
if(tab[i]==tab[j]) return 0;
return distinctValues_rec(tab, i , j+1, n) ;
}
int tousdistincts(int n, int t[n]) {
return distinctValues_rec (t, 0, 1, n);
}
int main() {
int t[] = {1, 2, 3, 2}, n = sizeof t / sizeof *t;
printf("%s distincts\n", tousdistincts(n, t)?"tous":"pas tous");
}
Explication
pour savoir si tous les éléments d'un tableau sont distincts:
voir si tous les éléments du tableau à partir du 1er sont différents de tous les éléments à partir du 2e
pour savoir si tous les éléments du tableau à partir du N°i sont différents de tous les éléments à partir du N°j:
si i n'est pas le dernier:
si j n'est pas hors limite du tableau:
si l'élément N°i est égal à l'élément N°j:
la réponse est non
sinon:
voir si tous les éléments à partir du N°i sont différents de tous les éléments à partir du N°j+1
sinon: (si j a dépassé la fin du tableau)
voir si tous les éléments à partir du N°i+1 sont différents de tous les éléments à partir du N°i+2
sinon: (si i est le N° du dernier élément du tableau)
la réponse est oui (il n'y a rien à comparer, tous les éléments sont distincts)
Avec des commentaires dans le code (j’ai changé l’ordre des tests, mais ça reste le même programme) :
#include <stdio.h>
int distinctValues_rec(int tab[], int i, int j, int n);
//pour savoir si tous les éléments d'un tableau sont distincts:
int tousdistincts(int n, int t[n]) {
/* voir si tous les éléments du tableau à partir du 1er
sont différents de tous les éléments à partir du 2e */
return distinctValues_rec (t, 0, 1, n);
}
/*pour savoir si tous les éléments du tableau à partir du N°i
sont différents de tous les éléments à partir du N°j: */
int distinctValues_rec(int tab[], int i, int j, int n)
{
//si i n'est pas le dernier:
if (i < n-1)
//si j n'est pas hors limite du tableau:
if (j < n)
//si l'élément N°i est égal à l'élément N°j:
if (tab[i]==tab[j])
//la réponse est non
return 0;
//sinon:
else
//voir si tous les éléments à partir du N°i sont
//différents de tous les éléments à partir du N°j+1
return distinctValues_rec(tab, i , j+1, n) ;
//sinon: (si j a dépassé la fin du tableau)
else // (j==n)
//voir si tous les éléments à partir du N°i+1 sont
//différents de tous les éléments à partir du N°i+2
return distinctValues_rec(tab, i+1, i+2, n) ;
//sinon: (si i est le N° du dernier élément du tableau)
else // (i==n-1)
//la réponse est oui (il n'y a rien à comparer, tous les
//éléments sont distincts)
return 1;
}
int main() {
int t[] = {1, 2, 3, 2}, n = sizeof t / sizeof *t;
printf("%s distincts\n", tousdistincts(n, t)?"tous":"pas tous");
}
Ma solution
#include <stdio.h>
int existe(int v, int n, int t[n]) {
return n > 0 && (v == t[0]
|| existe(v, n - 1, t + 1));
}
int tousdistincts(int n, int t[n]) {
return n < 2 || (!existe(t[0], n - 1, t + 1)
&& tousdistincts(n - 1, t + 1));
}
int main() {
int t[] = {1, 2, 3, 2}, n = sizeof t / sizeof *t;
printf("%s distincts\n", tousdistincts(n, t)?"tous":"pas tous");
}
Voici comme promis les séries de TD 1 (révision du langage C) et 2 (récursivité) :
