Scribd
Importer
8 vues3 pages

Algorithmes Récursifs et Complexité

Ce document contient des exercices sur la récursivité et le calcul de complexité d'algorithmes. Il présente 10 exercices sur l'écriture de fonctions récursives et le calcul de complexité d'algorithmes récursifs et itératifs.

Transféré par

moha.elayady
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
8 vues3 pages

Algorithmes Récursifs et Complexité

Ce document contient des exercices sur la récursivité et le calcul de complexité d'algorithmes. Il présente 10 exercices sur l'écriture de fonctions récursives et le calcul de complexité d'algorithmes récursifs et itératifs.

Transféré par

moha.elayady
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

UNIVERSITE IBN ZOHR Année Universitaire 2023/2024

ENSIASD -TAROUDANT

Travaux dirigés d’algorithmique : Série N°3


Objectifs :

• Ecrire des fonctions récursives


• Calculer la complexité d’un algorithme

Récursivité :

Exercice 1 :

Ecrire un algorithme qui permet de calculer la division entière comme suite :

Exercice 2 :

Ecrire une procédure récursive qui permet d'afficher la valeur binaire d'un entier n.

Exercice 3 :

Ecrire une fonction récursive en C qui permet de calculer la puissance d’un nombre.

Exercice 4 :

Ecrire une fonction récursive qui permet d’afficher les valeurs d’un tableau.

Exercice 5 :

Ecrire le corps des fonction récursives suivantes :

void affiche_inverse(char c[], int l); // Afficher en inverse une chaine de caractères
void affiche_pyramide(char c, int h); // Afficher un pyramide de caractères

Complexité

Exercice 6 :

1
UNIVERSITE IBN ZOHR Année Universitaire 2023/2024
ENSIASD -TAROUDANT
Calculer la complexité de l’algorithme suivant :

Algorithme afficher;
variables n,i: entier;
Début
Ecrire("Entrer un nombre:");
Lire(n);
Pour i<- n + 1 jusqu'à n+5 faire
Ecrire(i);
FinPour
Fin

Exercice 7 :

Algorithme Tab2D; Ecrire("Affichage des éléments du tableau :");


variables Tableau T[][],n,i,j: entier; Pour i<-0 jusqu'à n-1 faire
Début Pour j<-0 jusqu'à n-1 faire
Ecrire("Donner la taille du tableau:"); Ecrire(T[i][j]);
Lire(n); FinPour
Redimensionner T[n][n]; FinPour
Ecrire("Entrer les éléments du tableau:"); Fin
Pour i<-0 jusqu'à n-1 faire
Pour j<-0 jusqu'à n-1 faire
Lire(T[i][j]);
FinPour
FinPour

Exercice 8 :
Calculer la complexité de cette fonction récursive :

Fonction Fibo(n:entier): entier;


DébutFonction
Si (n<=0) Alors
Returner 1
Sinon
Returner Fibo(n-1) + Fibo(n-2);
FinFonction

2
UNIVERSITE IBN ZOHR Année Universitaire 2023/2024
ENSIASD -TAROUDANT

Exercice 9 :
Calculer la complexité de cette fonction :
void ex9(int n, int s){
int p=n; s=0;
while(p>=1){
int i = 1;
while(i<=n){
s+=p;
i++;
}
p/=2;
}

Exercice 10 :
Calculer la complexité de cette fonction :
void ex10(int n){
for(int i=n; i>0 ; i=i/2){
for(int j=1; j<n ; j=j*2){
for(int k=0; k<n ; k=k+2) // instructions
}
}
}

Vous aimerez peut-être aussi