Exercices corrigés td1 algorithmique et programmation 2 nomb
Télécharger PDFTravaux Dirigés d'Algorithmique et Programmation
Ce document présente une série d'exercices d'algorithmique et de programmation, accompagnés de leurs corrigés en langage C. Ces exercices couvrent des concepts fondamentaux tels que les nombres parfaits, les fonctions de puissance, les suites numériques (arithmétique et Fibonacci) et le calcul du PGCD, ainsi que l'approximation de fonctions mathématiques via des séries.
Exercice 1 : Nombre Parfait
Un nombre est dit parfait s'il est égal à la somme de ses diviseurs propres (c'est-à-dire tous ses diviseurs positifs, y compris 1, mais à l'exception du nombre lui-même). Par exemple :
- 6 = 1 + 2 + 3, est un nombre parfait.
- 28 = 1 + 2 + 4 + 7 + 14, est un nombre parfait.
Question :
- Définir une fonction itérative retournant 1 si le nombre passé en arguments est un nombre parfait et 0 sinon.
- Donner un programme principal (
main) de test.
Exercice 2 : Fonction Puissance
La fonction puissance est définie pour un nombre réel x et un entier n comme xn.
Question :
- Définir cette fonction en langage C en donnant :
- Une version itérative.
- Une version récursive.
- Un programme principal (
main) de test.
Exercice 3 : Suite Numérique \(u_n\)
Soit une suite \(u\) définie par :
u0 = 2un = un-1 + 3sin ≥ 1
Cette suite est une suite arithmétique de premier terme u0 = 2 et de raison 3.
Question :
- Définir une fonction
uqui détermine lan-ième valeurunoùnest un entier passé en paramètres.- Donner une version itérative.
- Donner une version récursive.
- Donner un programme principal (
main) de test.
Exercice 4 : Suite de Fibonacci
La suite de Fibonacci est définie par :
f0 = 1f1 = 1fn = fn-1 + fn-2sin ≥ 2
Chaque terme est la somme des deux précédents. C'est une séquence fondamentale en mathématiques et en informatique.
Question :
- Écrire la fonction
fibpermettant de calculer len-ième terme de cette suite, oùnest un entier passé en arguments.- Donner une version itérative.
- Donner une version récursive.
- Donner un programme principal (
main) de test.
Exercice 5 : PGCD (Plus Grand Commun Diviseur) avec l'Algorithme d'Euclide
Le PGCD de deux nombres entiers a et b est obtenu en utilisant l'algorithme d'Euclide, qui repose sur une suite de divisions euclidiennes :
- Effectuer la division euclidienne de
aparbet noterrle reste. - Ensuite,
aprend la valeur debetbprend la valeur der. - Recommencer les étapes (i) et (ii) jusqu'à ce que
bsoit nul.
Ainsi, le PGCD est la dernière valeur non nulle prise par a (soit la valeur de a lorsque b devient nul).
Question :
- Définir la fonction
pgcdqui calcule le PGCD de deux nombres entiers passés en arguments :- Donner une version itérative.
- Sachant que :
pgcd(a, b) = pgcd(b, a % b)sib ≠ 0, etpgcd(a, 0) = a, donner une version récursive. - Donner un programme principal (
main) de test.
Exercice 6 : Approximation de la fonction \(\sin(x)\) par développement en série de Taylor
La fonction \(\sin(x)\) peut être approchée par le développement en série de Taylor suivant (autour de 0) :
sin(x) = Somme de k=0 à l'infini de ((-1)k * x(2k+1)) / (2k+1)!
Puisqu'il est impossible de calculer une somme infinie, on propose d'arrêter la sommation lorsque la valeur absolue du terme courant x(2k+1) / (2k+1)! devient inférieure à une petite valeur d'epsilon (par exemple, 10-5), pour garantir une précision suffisante.
Question :
- En utilisant la fonction
powdéfinie dansmath.h, donner la fonctionSinpermettant de calculer la valeur approximative de \(\sin(x)\). - Donner un programme principal (
main) de test.
Corrigé des Travaux Dirigés
Corrigé Exercice 1 : Nombre Parfait
#include <stdio.h>
int parfait(int n) {
int i, s = 0;
// Les diviseurs propres (sauf n lui-même) sont <= n/2. Le 1 est toujours un diviseur.
for (i = 1; i <= n / 2; i++) {
if (n % i == 0) {
s += i;
}
}
if (s == n) {
return 1; // Le nombre est parfait
}
return 0; // Le nombre n'est pas parfait
}
int main() {
int n;
printf("Donner un entier : ");
scanf("%d", &n);
if (parfait(n)) {
printf("%d est un nombre parfait \n", n);
} else {
printf("%d n'est pas un nombre parfait \n", n);
}
return 0;
}
Corrigé Exercice 2 : Fonction Puissance
#include <stdio.h>
double puissance_it(double x, int n) {
double p = 1;
int i, m;
if (n < 0) {
m = -n; // Traiter la valeur absolue de n pour le calcul itératif
} else {
m = n;
}
for (i = 0; i < m; i++) {
p *= x;
}
if (n < 0) {
return 1 / p; // Si n est négatif, le résultat est 1/x^|n|
} else {
return p;
}
}
double puissance_rec(double x, int n) {
if (n == 0) {
return 1; // Cas de base : x^0 = 1
} else if (n < 0) {
return 1 / puissance_rec(x, -n); // Cas n négatif : x^-n = 1 / x^|n|
} else {
return x * puissance_rec(x, n - 1); // Cas n positif : x^n = x * x^(n-1)
}
}
int main() {
int n;
double x;
printf("Donner un réel : ");
scanf("%lf", &x);
printf("Donner un entier : ");
scanf("%d", &n);
printf("En utilisant puissance_it : %lf\n", puissance_it(x, n));
printf("En utilisant puissance_rec : %lf\n", puissance_rec(x, n));
return 0;
}
Corrigé Exercice 3 : Suite Numérique \(u_n\)
#include <stdio.h>
int u_it(int n) {
int s = 2, i; // Initialisation de s à u0
for (i = 0; i < n; i++) {
s += 3; // Ajout de la raison n fois
}
return s;
}
int u_rec(int n) {
if (n == 0) {
return 2; // Cas de base u0 = 2
}
return u_rec(n - 1) + 3; // Relation de récurrence un = u(n-1) + 3
}
int main() {
int n;
printf("Donner un entier : ");
scanf("%d", &n);
printf("En utilisant u_it : %d\n", u_it(n));
printf("En utilisant u_rec : %d\n", u_rec(n));
return 0;
}
Corrigé Exercice 4 : Suite de Fibonacci
#include <stdio.h>
int fib_rec(int n) {
if (n == 0 || n == 1) {
return 1; // Cas de base f0 = 1, f1 = 1
}
return fib_rec(n - 1) + fib_rec(n - 2); // Relation de récurrence
}
int fib_it(int n) {
int a = 1, b = 1, c, i;
// Initialisation pour les premiers termes. c est le terme courant.
// Si n=0 ou n=1, le résultat est 1.
if (n == 0 || n == 1) {
return 1;
}
// Calcul des termes à partir de f2
for (i = 2; i <= n; i++) {
c = a + b; // Le nouveau terme est la somme des deux précédents
a = b; // Décalage : l'ancien 'b' devient 'a'
b = c; // Décalage : le nouveau 'c' devient 'b'
}
return c;
}
int main() {
int n;
printf("Donner un entier : ");
scanf("%d", &n);
printf("En utilisant fib_it : %d\n", fib_it(n));
printf("En utilisant fib_rec : %d\n", fib_rec(n));
return 0;
}
Corrigé Exercice 5 : PGCD (Algorithme d'Euclide)
#include <stdio.h>
int pgcd_rec(int a, int b) {
// Pas nécessaire de vérifier que a > b car l'algorithme d'Euclide gère cela automatiquement
// pgcd(a,b) = pgcd(b, a%b)
if (b == 0) {
return a; // Cas de base : pgcd(a, 0) = a
}
return pgcd_rec(b, a % b);
}
int pgcd_it(int a, int b) {
// Pas nécessaire de vérifier que a > b car l'algorithme d'Euclide gère cela automatiquement
int r;
while (b != 0) {
r = a % b; // Calcul du reste
a = b; // a prend la valeur de b
b = r; // b prend la valeur du reste
}
return a; // Lorsque b est 0, a contient le PGCD
}
int main() {
int a, b;
printf("Donner un entier a : ");
scanf("%d", &a);
printf("Donner un entier b : ");
scanf("%d", &b);
printf("En utilisant pgcd_it : %d\n", pgcd_it(a, b));
printf("En utilisant pgcd_rec : %d\n", pgcd_rec(a, b));
return 0;
}
Corrigé Exercice 6 : Approximation de la fonction \(\sin(x)\)
#include <stdio.h>
#include <math.h> // Pour la fonction pow et fabs (valeur absolue flottante)
#define EPSILON 0.00001 // Définir la précision souhaitée pour l'approximation
// Fonction pour calculer la factorielle d'un nombre
long fact(long n) {
long p = 1, i;
for (i = 1; i <= n; i++) {
p *= i;
}
return p;
}
// Fonction pour approximer sin(x) en utilisant la série de Taylor
float Sin(float x) {
float s = 0; // Somme des termes de la série
int k = 0; // Compteur pour les termes (indice de la série)
float term_value; // Valeur du terme courant de la série (sans le signe)
do {
// Calcul du terme courant : x^(2k+1) / (2k+1)!
// Cast en (float) pour assurer une division flottante même si fact retourne un long
term_value = (float)pow(x, 2 * k + 1) / fact(2 * k + 1);
// Ajout du terme à la somme en alternant le signe (-1)^k
// On gère le signe manuellement pour des raisons de robustesse et performance (pow(-1, k) peut être imprécis)
if (k % 2 == 0) { // Si k est pair, le signe est +1
s += term_value;
} else { // Si k est impair, le signe est -1
s -= term_value;
}
k++;
} while (fabs(term_value) > EPSILON); // Continuer tant que la valeur absolue du terme courant est supérieure à epsilon
return s;
}
int main() {
double test_value = 3.1415926535; // Utilisation de double pour une meilleure précision pour PI
printf("Approximation de sin(%f) par notre fonction Sin : %f\n", test_value, Sin((float)test_value));
printf("Valeur de sin(%f) avec la fonction standard sin() : %f\n", test_value, sin(test_value));
return 0;
}
Note: Dans la solution originale, la variable e a été renommée en EPSILON pour éviter toute confusion avec la constante mathématique \(e\). De plus, l'implémentation de pow(-1, k) a été remplacée par une gestion explicite du signe (if (k % 2 == 0)) pour des raisons de performance et de robustesse en C, la fonction pow étant principalement conçue pour les exposants réels positifs.
Foire Aux Questions (FAQ)
Q1: Qu'est-ce qu'un nombre parfait en programmation ?
En programmation, un nombre parfait est un entier positif qui est égal à la somme de ses diviseurs positifs stricts (c'est-à-dire tous ses diviseurs sauf lui-même). L'exercice 1 en fournit un exemple avec le nombre 6, dont les diviseurs stricts sont 1, 2, et 3 (1+2+3 = 6).
Q2: Quelle est la différence entre une fonction itérative et une fonction récursive ?
Une fonction itérative utilise des boucles (comme for ou while) pour répéter un bloc de code jusqu'à ce qu'une condition soit remplie. Une fonction récursive, en revanche, s'appelle elle-même pour résoudre des sous-problèmes plus petits, jusqu'à atteindre un cas de base qui peut être résolu directement. Les exercices 2, 3, 4 et 5 illustrent ces deux approches, chacune ayant ses avantages et inconvénients en termes de lisibilité et de performance.
Q3: Comment l'algorithme d'Euclide calcule-t-il le Plus Grand Commun Diviseur (PGCD) ?
L'algorithme d'Euclide calcule le PGCD de deux nombres entiers en remplaçant répétitivement le plus grand des deux nombres par le reste de la division euclidienne du plus grand par le plus petit, jusqu'à ce que l'un des nombres devienne zéro. Le PGCD est alors le nombre non nul restant. Ce processus est expliqué et implémenté dans l'exercice 5 sous des formes itératives et récursives.