Exercices d'algorithmique : série 1
N.B. Rechercher sur Wikipedia (ou autre) les définitions inconnues nécessaires à la résolution des exercices.
Exercice 1.1.
a) Avec un mot-mémoire de 32 bits, combien peut-on représenter
d'entiers naturels ? d'entiers relatifs ? de caractères ? de
chaines de caractères ?
b) Quel taille de mot-mémoire faudrait-il pour coder tous les
chiffres ? pour donner un identifiant unique à chaque être humain de la
planète ? Pour représenter tous les réels compris entre 0 et 1 ?
c) Quel est le rapport de l'algorithme Encadrer avec les
questions précédentes ?
algorithme Encadrer
Donnée : un entier naturel n.
Résultat : un entier naturel k tel que
2
k−1 < n ≤ 2
k.
k←0;
p←1;
Tantque p<n
faire
k←k+1;
p←2*p;
d) Quelle taille de mot-mémoire faudrait-il pour représenter le nombre
π avec sept chiffres après la virgule ?
Exercice 1.2.
a) Quel est l'effet de chacune des instructions de l'algorithme :
algorithme 12a
Donnée un entier n.
Résultat : ...
a← 5;
b←b+n;
c=4;
c→4;
s="ok";
x←(s≠"ko");
y←(x ou a=5);
a←3a;
a*3←a+2;
b) Ecrire un algorithme qui affiche la conjugaison au singulier du
futur de l'indicatif d'un verbe du premier groupe dont l'infinitif est donné.
(L'opérateur de concaténation de chaine est noté +)
c) Ecrire un algorithme qui affiche toute la conjugaison du
conditionnel présent d'un verbe du premier groupe dont l'infinitif est donné.
Exercice 1.3.
a) Ecrire une procédure Echanger qui échange les valeurs
de deux variables x et y quelconques.
b) Faire la trace de l'algorithme ci-dessous pour x=−5 et y=4,
puis préciser de qu'il fait.
algorithme 13b
Donnée : deux entiers n et p.
Résultat : ...
n←n+p;
p←n−p;
n←n−p.
c) Ecrire une fonction qui transforme une température en Farenheit en
une température en Celsius. Ecrire la fonction réciproque.
d) Ecrire une fonction IMC qui donne l'indice de masse
corporelle d'une personne. Pourquoi ne peut-on écrire la fonction
réciproque ?
Exercice 1.4.
a) Ecrire une fonction qui détermine si un nombre est pair.
De quel type est le retour de cette fonction ?
b) Que fait l'algorithme précisé suivant ?
fonction Estconforme
Entrée : un entier n.
Sortie : ...
x←0; y←1; z←2 ;
Retourner ((x+y+z+n) mod 2 = 0).
Exercice 1.5.
a) Ecrire une fonction Distance qui calcule la distance
entre deux points du plan.
b) Ecrire une fonction qui vérifie si un point du plan appartient à
une droite d'équation ax+by+c=0.
c) En utilisant la fonction Distance, écrire une
fonction qui vérifie si un triangle est équilatéral. Même question pour un
triangle isocèle, puis pour un triangle rectangle.
Exercice 1.6.
a) Ecrire un algorithme général qui détermine si une année est
bissextile.
b) Ecrire un algorithme qui détermine si une date est valide.
(Quel structure de contrôle utiliser pour vérifier le nombre de jours des
différents mois ?)
c) Ecrire un algorithme qui calcule le nombre de jour entre le premier
janvier et une date de la même année.
d) Ecrire un algorithme qui convertit une durée en jours, heures,
minutes et secondes en une durée en secondes.
Ecrire l'algorithme réciproque.
Exercice 1.7.
a) Quelle est la complexité de l'algorithme Encadrer
de la question 1.1.c) ?
b) Pour chacun des autres algorithmes ci-dessus, montrer que le
problème correspondant est en O(1). Pourquoi une complexité algorithmique
en O(1) rend-elle évidente la preuve d'arrêt d'un algorithme ?
c) Pourquoi le problème suivant est-il semi-décidable ?
Problème Résolution
Donnée : une équation ax2+bx+c=0 à coefficients réels.
Résultat : les solutions de cette équation.