Récursivité en C - Applications résolues
1) Calculez n! dans la version iterative.
#include<stdio.h> long int factoriel (int n) { long int f=1; for (int i=1; i<=n;i++) f=f*i; return f; } void main() { int n; printf("Introduire n= "); scanf("%d", &n); if(!n) printf("0!=1\n"); else printf("%d!=%ld\n",n,factoriel(n)); getchar(); int var; scanf("%d", var); }
2) Calculer n! dans la version recursive.
// factoriel(3)=3*factoriel(2)=3*2*factoriel(1)=3*2*1 #include<stdio.h> long int factoriel (int n) { if (n==1) return 1; else return n*factoriel(n-1); } void main() { int n; printf("Introduire n= "); scanf("%d", &n); if(!n) printf("0!=1\n"); else printf("%d!=%ld\n",n,factoriel(n)); getchar(); int var; scanf("%d", var); }
3) Calculer recursivement la somme des elements d’une chaine.
#include<stdio.h> int somme(int n) { if (n==0) return 0; else return (n + somme(n-1)); } void main() { int n; printf("Introduire n: "); scanf("%d", &n); printf("La somme des elements est %d\n",somme(n)); getchar(); int var; scanf("%d", var); }
4) Ecriver une fonction propre qui realise le calcule recursive de la somme des elements d’un vecteur, de n<=10, de nombre reel. Ecriver la fonction main qui lit les dates du clavier, calcule la somme, en utilisant la fonction recursive anterieurement definie et affiche la valeur obtenue.
#include <stdio.h> #include <conio.h> int a[10], n; int somme (int n, int a[10]) { if(n==0) return 0; else return(a[n]+somme(n-1,a)); } void main() { // Lire les dates d’entree printf("Introduire le nombre des elements: "); scanf("%d", &n); for (int i=1; i<=n; i++) { printf("element [%d] = ", i); scanf("%d", &a[i]); } // Affichage des resultats printf("somme = %d", somme(n,a)); getch(); }
5) Ecrire un programme C, pour rezoudre le cmmdc entre deux nombres entiers sans signe (pour determiner le cmmdc-ului on va utiliser l’algrithme de Euclid par diminutions). Version iterative.
#include <stdio.h> #include <conio.h> unsigned int cmmdc(unsigned int a, unsigned int b) { while(a!=b) { if(a>b) a=a-b; else b=b-a; } return a; } void main() { unsigned int x,y; printf("Introduire x: "); scanf("%u",&x); printf("Introduire y: "); scanf("%u",&y); if(!x || !y) //si x=0 or y=0 printf("cmmdc(%u,%u) = 1\n",x,y); else printf("cmmdc(%u,%u) = %u\n",x,y,cmmdc(x,y)); getch(); }
6) Ecrire un programme C, pour rezoudre le cmmdc entre deux nombres entiers sans signe (pour determiner le cmmdc on va utiliser l’algorithme de Euclid par diminutions). Version recursive.
#include <stdio.h> #include <conio.h> unsigned int cmmdc(unsigned int a, unsigned int b) { if(a==b) return a; else if(a>b) return cmmdc(a-b,b); else return cmmdc(a,b-a); } void main() { unsigned int x,y; printf("Introduire x: "); scanf("%u",&x); printf("Introduire y: "); scanf("%u",&y); if(!x || !y) //si x=0 or y=0 printf("cmmdc(%u,%u) = 1\n",x,y); else printf("cmmdc(%u,%u) = %u\n",x,y,cmmdc(x,y)); getch(); }
7) Ecrire un programme C, pour rezoudre le cmmdc de n nombres entiers sans signe
(pour determiner le cmmdc on va utiliser l’algorithme de Euclid par diminutions). Version recursive.
#include <stdio.h> #include <conio.h> unsigned int cmmdc_2(unsigned int a, unsigned int b) { if(a==b) return a; if(a>b) return cmmdc_2(a-b,b); else return cmmdc_2(a,b-a); } unsigned int cmmdc_n(unsigned int x[], int n) { if (n==2) return cmmdc_2(x[0],x[1]); else return cmmdc_2(cmmdc_n(x,n-1),x[n-1]); } void main() { unsigned int x[20]; int n; printf("Introduire n: "); scanf("%d",&n); for(int i=0;i<n;i++) { printf("element %d= ",i+1); scanf("%u",&x[i]); } if (n==1) printf("\nCmmdc des nombres: %u",x[0]); else printf("\nCmmdc des nombres: %u",cmmdc_n(x,n)); getch(); }
8) On considere les suivantes declarations et conventions:
typedef int vector[20];
x – est un vecteur (chaine des elements)
n – est sa longueur (n>=1)
In faudra ecrire des fonctions recursives pour determiner, pour un vecteur x de longueur n, les suivantes:
a. lecture des components de la chaine
b. affichage des elements d’une chaine
c. somme ds components
d. produit des components
e. nombre des components negatifs
f. produit des components positifs
g. moyen aritmetique des elements
typedef int vector[20];
x – est un vecteur (chaine des elements)
n – est sa longueur (n>=1)
In faudra ecrire des fonctions recursives pour determiner, pour un vecteur x de longueur n, les suivantes:
a. lecture des components de la chaine
b. affichage des elements d’une chaine
c. somme ds components
d. produit des components
e. nombre des components negatifs
f. produit des components positifs
g. moyen aritmetique des elements
#include<stdio.h> #include<conio.h> /* type propre defini pour memoriser des chaines des elements entiers, avec une Dimension maximum de 20 de components */ typedef int vecteur[20]; //fonction de lire void lire(vecteur x,int n) //n est la dimension reelle de la chaine { //lire le dernier element de la chaine printf("\telement %d: ",n); scanf("%d",&x[n-1]); if(n>=2) lire(x,n-1); //l’appel recursive de la fonction } //fonction d’affichage void affichage(vecteur x,int n) //n est la dimension reelle (nombre d’elements de la chaine) { //afficher le dernier element printf("%d ",x[n-1]); if(n>=2) affichage(x,n-1); //appell recursive de la fonction } //addition des components d’une chaine int somme(vecteur x,int n) //n on condidere indice l’lement de la chaine { if(n==-1) return 0; /*la situation quand il n’y a pas d’elements dans la chaine, pozition n=-1 n’est pas dans la chaine*/ else return x[n]+somme(x,n-1); } //produit des components int produit(vecteur x,int n) { if(n==-1) return 1; else return x[n]*produit(x,n-1); } //nombre des components negatifs int nombre_negatif(vecteur x,int n) { //il faut se positioner sur le premier element de la chaine et verifier si’il est negatif if(n==0) return (x[n]<0); //l’expression reconditionee va retourner 1 en cas de vrai et 0 in caz de faux else return (x[n]<0)+nombre_negatif(x,n-1); } //produit des components positifes int produit_positife(vecteur x,int n) { if(n==0) return (x[n]>0?x[n]:1); /* on utilise l’opperateur de conditioner, qui, si l’expression evaluee comme vraie on va prendre en calcule x[n], autrement, la valeur 1 */ else return (x[n]>0?x[n]:1)*produit_positife(x,n-1); } //moyen aritmetique des components de la chaine float media(vecteur x, int m, int n) /*on notte avec m l’ indice des elementsr, et avec n la dimension reelle de la chaine*/ { return (float)x[m]/n + ((m!=0)?media(x,m-1,n):0); /* - am folosit expresia (float) pour une conversion explicite du resultat Vers un type reel - par x[m]/n on comprend un element (premierement, il sera le dernier de la chaine) divise au nombre des components */ } //fonction principale dans l’execution void main() { vecteur x; //chaine des elements int n; //sa dimension (nombrte des components lus) //realiser l’opperation de lire de la chaine printf("Entrer le nombre des elements: "); scanf("%d",&n); printf("Introduire les elements de la chaine:\n"); lire(x,n); //realization de l’opperation de’affichage de la chaine printf("La chaine des elements est: "); affichage(x,n); //la somme des elements printf("\nLa somme des elements: %d",somme(x,n-1)); /* on appel avec n-1, car on a dit que ce parametre represent l’indice du dernier element de la chaine */ //le produit des elements printf("\nLe produit des elements: %d",produit(x,n-1)); //nombre des elements negatifs de la chaine printf("\nNombre des elements negatifs: %d",nombre_negatif(x,n-1)); //produit des components positifs printf("\nproduit des elements positifs: %d",produit_positife(x,n-1)); //media componentelor din sir printf("\nMoyen des components de la chaine: %.2f",media(x,n-1,n)); /* premier parametre - chaine, deuxieme parametre – l’indice du dernier element de la chaine, le troixieme parametre – dimension reelle de la chaine (nombre ds elements lus) */ getch(); }
9) Ecrire une fonction recursive pour determiner la somme des ciffres d’un nombre naturel.
A savoir: On doit isoler la derniere ciffre, et pour n on attribue le reste de division entre la vieille valeur et 10.
#include<stdio.h> #include<conio.h> int somme(int n) { if(!n) return 0; //!n=s’il n’y a pas de n else return n%10+somme(n/10); } void main() { int n; printf("Introduire le nombre: "); scanf("%d", &n); printf("La somme des ciffres du nombre est: %d", somme(n)); getch(); }
10) Ecrire une fonction recursive pour transformer un nombre naturel n, de base 10 en base k (1<k<=10).
A savoir: On divise le nombre par k, on retient le reste, on le divise par k,... jusqu’a ce que le reste sera mois que le diviseur. On obtint le resultat en ecrivant en ordre enverse la chaine des restes obtenus.
On liste le reste apres l’autoapel.
#include<stdio.h> #include<conio.h> void transform(int n,int b) { int rest=n%b; if (n>=b) transform(n/b,b); printf("%d",rest); } void main() { int n,b; printf("n="); scanf("%d",&n); printf("base="); scanf("%d",&b); transform(n,b); getch(); }
11) Lire x de Z . On demande un sous-programme pour calculer la fonction Manna-Pnuelli:
x-1, x>=12 F(x)= F(F(x+2)), x<12
#include<stdio.h> #include<conio.h> int F(int x) { if (x>=12) return x-1; return F(F(x+2)); } void main() { int x; printf("x="); scanf("%d",&x); printf("La valeur de la fonction est: %d",F(x)); getch(); }
12) On considere la chaine de Fibonacci comme ca:
0, n=0 Un= 1, n=1 Un-1+Un-2, autreOn lit n, un nombre naturel. Calculez Un, version iterative.
#include<stdio.h> #include<conio.h> void main() { int n,U0=0,U1=1,U2; printf("n="); scanf("%d",&n); if(!n) printf("%d",U0); else if (n==1) printf("%d",U1); else { for (int i=2;i<=n;i++) { U2=U0+U1; U0=U1; U1=U2; } printf("%d",U2); } /* ptr. n=3 i=2: U2=U0+U1 U0=U1 U1=U2 i=3: U2=U1+U2 */ getch(); }
13) On considere la chaine Fibonacci comme:
0, n=0 Un= 1, n=1 Un-1+Un-2, altfelOn lit n, un nombre naturel. Calculez Un, version iterative.
#include<stdio.h> #include<conio.h> int U (int n) { if (!n) return 0; else if (n==1) return 1; else return U(n-1)+U(n-2); } void main() { int n; printf("Introduire n="); scanf("%d",&n); printf("La valeur de la chaine en n est: %d",U(n)); getch(); }