Ecole Nationale Supérieure des Télécommunications
Base de Connaissances Indispensables
Initiation et exercices simples
Exercice 1:
Créer un répertoire tp_algo
mkdir tp_algo
Aller dans ce répertoire et regarder ce qu'il y a dedans
cd tp_algo
ls
Copier le fichier coucou.c
Editer son contenu avec xemacs.
xemacs coucou.c &
Compiler dans la fenêtre d'exécution (ou bien dans l'environnement xenacs) avec la commande
gcc -o coucou -Wall coucou.c
Exécuter le programme dans la fenêtre de commande
coucou
Regarder quels fichiers ont été créés et les détruire avec la commande
rm nom_de_fichier
Exercice 2:
Première partie
Lire un entier N strictement positif et indiquer si ce nombre est premier.
Corrigé
Seconde partie
Lire un entier N strictement positif et imprimer tous les nombres premiers
compris entre 1 et N. On réutilisera, en le modifiant, le code de l'exercice
précédent.
exemple : si on indique l'entier 10, le résultat doit être : 1 2 3 5 7 .
Un corrigé avec seulement une fonction main
Un corrigé utilisant une fonction est_premier
Facultatif : faire le même exercice mais
en cherchant les nombres premiers avec N ; exemple : si on indique l'entier 10,
le résultat doit être 3 7 9
Un corrigé pour la partie facultative
Exercice 3: impression d'une matrice de Hilbert
Demander à l'utilisateur un entier compris entre
1 et 6 puis imprimer de façon claire la matrice de Hilbert d'ordre n .
La matrice de Hilbert (aij) est telle que aij=1 / (i + j - 1) (division non entière).
Attention : on ne demande pas de mémoriser la matrice, il s'agit d'écrire
dans la fenêtre d'exécution les éléments de la matrice au fur et à mesure de
leurs calculs.
Le spécificateur de format qui permet d'écrire un réel en précisant le nombre
total p de caractères et le nombre d de chiffres après la virgule est le
suivant: %p.df ; par exemple %8.3f si on veut 8
caractères dont 3 décimales (en comptant le point).
Exercice 4: recherche dichotomique
L'utilisateur indique la valeur d'un
"réel" a et deux
"réels" nommés min et max. Ces trois réels seront codés avec des
variables de type double. Le
programme contient la définition de la fonction f(x) = x3 - a. On pourra avoir une variable
globale a ; la fonction f aura pour prototype : double f(double x);le paramètre x correspond à la valeur de la variable x et la valeur de retour à la valeur de f(x).
Il s'agit de chercher une éventuelle solution comprise entre min et max
de l'équation f(x) = 0 et cela
par dichotomie.
Si f(min) et f(max) sont de même signe, le programme
indique qu'il ne peut pas répondre à la question et s'arrête. Dans le cas
contraire, la solution est calculée à 10-6 près.
On prévoira le programme pour qu'il puisse fonctionner si on change de fonction f.
Un point technique : pour saisir un double avec scanf, l'indicateur de format est %lf.
Exercice 5: algorithmes de Horner
Il s'agit de réaliser l'implémentation du calcul de la valeur d'un polynôme P
en un point en utilisant l'algorithme de Horner :
P(x) = ((...((anx
+ an - 1)x + an - 2)... a1)x + a0).
Le polynôme sera saisi en indiquant son degré puis tous ses coefficients ;
ces derniers seront mis dans un tableau.
Première partie
Après la saisie du polynôme, le programme demande à l'utilisateur la valeur de
x pour lequel il demande le calcul de P(x) et indique alors la valeur cherchée.
Un corrigé
Seconde partie
Après la saisie du polynôme, le programme demandera à l'utilisateur s'il veut
l'évaluer ; si oui, celui-ci répondra par le caractère 'o' ; il devra alors
donner la valeur de x pour lequel il demande le calcul de P(x). le programme
redemandera alors si l'utilisateur veut à nouveau évaluer le polynôme P, et
cela jusqu'à ce que l'utilisateur réponde par le caractère 'n'.
Un point technique :L'instruction :
getchar();
devra probablement être utilisée avant la saisie d'un caractère pour vider le buffer de lecture (qui pourrait contenir un "caractère
de retour à la ligne").
Un corrigé
Exercice 6: triangle donné par les longueurs de ses côtés
Etant donné trois nombres réels, ces trois nombres peuvent-ils être les longueurs des côtés d'un triangle ? Si oui, donnez des coordonnées des sommets du triangle, en mettant un des sommets à l'origine et un autre sur l'axe des abscisses. Le plus grand des côtés devra être le côté horizontal.
Sur la figure ci-dessus, on peut remarquer :
y2 + x2 = b2
y2 + (a - x)2
= c2
Donc :
(a - x)2 - x2
= c2 - b2
ce qui donne :
a2 - 2 a x = c2
- b2
et donc :
x = (a2 + b2 - c2) / 2 a
y = sqrt( b2 - x2)
On pourra essayer de tracer ce triangle en utilisant une bibliothèque graphique dont on peut trouver une documentation ici. En particulier :
On mettra #include <graphique.h> en début de programme ;On utilisera l'instruction Initialisation_Graphique<(-1, -1, alpha, beta); où alpha sera supérieur au plus grand côté du triangle et beta supérieur à sa hauteur.
pour avoir une fenêtre graphique capable de contenir le triangle.
On tracera le triangle avec la fonction :
void Trait (float x1, float y1, float x2, float y2, int couleur);
où couleur sera un entier
compris entre 0 et 14.
On utilisera l'instruction
Fin_Graphique();pour supprimer l'application graphique ;
on pourra compiler avec : gcc -Wall -g triangle.c -o triangle -lgraphique -lX11 -lm
Exercice 7: Ensembles de JULIA (ou bien vous passez à l'exercice 8, qui demande plus de connaissances, mais est instructif)
La théorie des fractales (le terme "fractal a été employé pour la 1ère fois en 1975 par Benoît Mandelbrot) a permis de faire le lien entre des modèles mathématiques déterministes et le comportement, apparemment "chaotique", de certains systèmes physiques.
Soit c 
C et un système dont les états successifs so>C et un système dont les états successifs sont modélisés par la suite complexe :
zn+1
= zn2 + c pour n >= 0 et z0 C.
On définit les ensembles suivants :
Ac = {z0
C 
|zn|
quand n } et Kc
= {z0 C 
r R, tq 
n
N |zn| < r }
L'ensemble de Julia proprement dit (d'après le
mathématicien français Gaston Julia qui étudia ces suites dès 1918 ) est
l'ensemble Jc frontière de Kc (et de Ac
). L'ensemble Kc, est connexe si 0 Kc ; sinon il est
constitué d'une "poussière de Cantor".
À part J0 et J-2 = [-2,+2], les ensembles Jc sont fractals.
Pour tracer Jc
on utilise la méthode des "orbites inverses": soit z'0,
quelconque ; on peut alors définir une infinité de suites {z'n}n
N par z'n+1
= 
pour n >= 0 ;
chacune de ces suites définies ce qu'on appelle une orbite inverse de e z'0.
Les points d'une orbite de z'0 se répartissent, sauf les premiers,
sur Jc.
Programmer un algorithme de dessin de Jc en traçant m points successifs d'une orbite inverse {z'0, z'1,..., z'm
} où le signe de chacun des z'n successifs
est choisi "au hasard" ( en utilisant la fonction rand définie dans stdlib
par int rand(void) dont le
résultat est un nombre aléatoire entier [0, RAND_MAX[)
Soit z = a + ib . Le nombre z'= x + iy vérifie (z')2 = z si
On pourra fixer m à 100 000 ;
le premier point pourra être fixé à 2 + 2i ;
on se renseignera ici pour faire du graphique.En particulier :
On mettra #include <graphique.h>en début de programme ;
o On utilisera l'instruction
Initialisation_Graphique(-2, -2, 2, 2);
pour avoir une fenêtre graphique ; cette fenêtre permet d'utiliser des abscisses comprises entre -2 et +2, de même pour les ordonnées.
void
Point (float x, float y,
int couleur);
où couleur sera un entier
compris entre 0 et 14.
o On utilisera l'instruction
Fin_Graphique();
pour supprimer l'application graphique ;
On pourra compiler avec : gcc -Wall julia.c -o monJulia -lgraphique -lX11 -lm
La valeur de c sera indiquée par l'utilisateur ; on pourra essayer en particulier ; c = -1, c = i, c = -0.12 + 0.74 i, c = 0.31 + 0.004, c = 0.05 + 0.95i, c = 0.12 + 0.68i.
Et s'il reste du temps : Exercice 8: trier des
mots
