Algorithmique – Travaux Dirigés

Master “Technologie et Handicap” : Intensifs d’Automne

Exercice 1 – Affectations
1. Considérons les algorithmes ci-dessous.
(a) Quel sera le contenu des variables a, b et éventuellement c après leur exécution ?
(b) Dans chacun des cas ci-dessus, y a-t-il des lignes inutiles, et si oui lesquelles ?
1 // algo 1.1 1 // algo 1.2 1 // algo 1.3
2 var a, b, c : entier 2 var a, b : entier 2 var a, b : entier
3 debut 3 debut 3 debut
4 a ←1 4 a ← 1 4 a ← 2
5 b ←a + 2 5 b ← a + 2 5 b ← a + 2
6 c ←b - 3 6 a ← 3 6 a ← a + 2
7 fin 7 fin 7 b ← a - 2
8 fin
1 // algo 1.4 1 // algo 1.5 1 // algo 1.6
2 var a, b, c : entier 2 var a, b, c : entier 2 var a, b : car
3 debut 3 debut 3 debut
4 a ←2 4 a ← 1 4 a ← ’1’
5 b ←4 5 b ← 2 5 b ← ’2’
6 c ←a + b 6 b ← a + b 6 a ← a + b
7 a ←1 7 c ← a + b 7 fin
8 c ←b - a 8 fin
9 fin

2. Considérons l’algorithme ci-contre 1 var a, b : entier

(a) Permet-il de permuter les valeurs des valeurs des variables a et b ? 2 debut
(b) Proposer des solutions pour permuter les valeurs de 2 variables 3 a ← 1
numériques ? Chacune des solutions proposées marche-t-elle dans 4 b ← 2
le cas de variables non numériques. 5 a ← b
6 b ← a
(c) Étant données 3 variables a, b et c, proposer un algorithme pour
7 fin
les permuter circulairement, en transférant les valeurs initiales de
a à b, de b à c, et de c à a.

Exercice 2
1. Quels sont les affichages provoqués par les algo- 1 // algo 2.1 1 // algo 2.2
rithmes ci-contre. 2 var a, b : reel 2 var a, b : entier
2. Écrire un algorithme qui demande un entier à l’uti- 3 var c : entier 3 var c : reel
lisateur, puis affiche son carré. 4 debut 4 debut
5 a ← 4.21 5 a ← 5
6 b← a * 2 6 b ← 2
7 ecrire a, b 7 ecrire a, b
8 ecrire b * 2 8 ecrire a / b
9 c← b * 2 9 c ← a / b
10 ecrire c 10 ecrire c
11 fin 11 fin

Master Handi – Université Paris 8 Algo – TD – 1

Exercice 3 – Conditionnelles
1. Écrire un algorithme qui demande un entier à l’utilisateur, teste si ce nombre est positif (≥ 0) ou non, et affiche
“positif” ou “négatif”.
2. Écrire un algorithme qui demande un entier à l’utilisateur, teste si ce nombre est strictement positif, nul ou stricte-
ment négatif, et affiche ce résultat.
3. Écrire un algorithme qui demande un réel à l’utilisateur et affiche sa valeur absolue (sans utiliser de fonction
prédéfinie évidemment).
4. Écrire un algorithme qui demande un réel à l’utilisateur et l’arrondit à l’entier le plus proche (les x,5 seront arrondis
à l’entier supérieur).
5. Écrire un algorithme qui demande le numéro d’un mois et affiche le nombre jours que comporte ce mois (sans
tenir compte des années bissextiles).
6. Écrire un algorithme qui vérifie si une année est bissextile. On rappelle qu’il y a des années bissextiles tous les
4 ans, mais la première année d’un siècle ne l’est pas (1800, 1900 n’étaient pas bissextiles) sauf tous les 400 ans
(2000 était une année bissextile).
7. Écrire un algorithme qui demande une date sous la forme de 2 nombres entiers (numéro du jour et numéro du
mois) et affiche la saison (ex : 12/02 ; hiver). On supposera que le premier jour de la saison est toujours le 21.
8. Écrire un programme qui demande les coordonnées (x, y) des sommets A, B et C d’un triangle et affiche la nature
du triangle (isocèle, équilatéral, rectangle ou quelconque).

Exercice 4 – Itérations
1. Écrire un algorithme qui demande un entier positif, et le rejette tant que le nombre saisi n’est pas conforme.
2. Écrire un algorithme qui demande 10 entiers, compte le nombre d’entiers positifs saisis, et affiche ce résultat.
3. Écrire un algorithme qui demande des entiers positifs à l’utilisateur, les additionne, et qui s’arrête en affichant le
résultat dès qu’un entier négatif est saisi.
4. Modifier ce dernier algorithme pour afficher la moyenne de la série d’entiers positifs saisis.

Exercice 5 – Conversion en binaire

1. Écrire un algorithme de conversion d’un nombre entier en binaire.
2. (Facultatif) Écrire un algorithme de conversion d’un nombre entier en une base b quelconque.

Exercice 6 – Suites
1. Écrire un algorithme pour afficher les n premiers termes des suites suivantes (n demandé à l’utilisateur) :
(a) Suite arithmétique (b) Suite de Newton (c) Suite de Fibonacci
u0 = a2
  
u0 = 1  u0 = 0
un+1 = un + 2 un+1 = 12 (un + uan ) u1 = 1
un+2 = un+1 + un

(a réel demandé à l’utilisateur)
2. (facultatif) La suite de Newton converge vers la racine carrée de a. Modifier l’alogorithme (b) pour calculer la
racine carrée d’un nombre selon une précision donnée.

Exercice 7 – Devinez un nombre

1. Écrire un algorithme permettant de joueur au jeu du plus petit-plus grand. On tire un nombre au hasard pour le
faire deviner au joueur en lui disant à chaque tour si le nombre proposé est plus grand ou plus petit que le nombre
à chercher. Lorsque le joueur a trouvé, l’algorithme se termine en affichant le nombre de tours.
Note : On suppose qu’on a une fonction entier nombreAléatoire(var max : entier) qui tire un
nombre au hasard et le renvoie.
2. Modifier ensuite cet algorithme pour limiter à 10 le nombre de propositions du joueur, et afficher "Perdu !" si le
joueur n’a pas trouvé.

Master Handi – Université Paris 8 Algo – TD – 2

Exercice 8 – Boucles imbriquées
1. Échiquiers
(a) Écrire un algorithme permettant d’écrire un carré de 8 fois 8 caractères ’x’.
(b) Écrire un algorithme permettant d’écrire un échiquier. On représentera les case noires par des ’x’ et les cases
blanches par des espaces.
(c) Modifier l’algorithme précédent pour afficher un cadre autour de l’échiquier, en utilisant les caractères ’|’ ,
’−’ et ’+’.
(d) Modifier de nouveau cet algorithme pour afficher l’ensemble des cases avec ces mêmes caractères (voir
exemple 4 ci-dessous – incomplet).
// a // b // c // d
+−−−−−−−−+ +−+−+−+ ... +
xxxxxxxx x x x x |x x x x | |x| |x| ... |
xxxxxxxx x x x x | x x x x| +−+−+−+ ... +
xxxxxxxx x x x x |x x x x | | |x| | ... |
xxxxxxxx x x x x | x x x x| +−+−+−+ ... +
xxxxxxxx x x x x |x x x x | |x| |x| ... |
xxxxxxxx x x x x | x x x x| +−+−+−+ ... +
xxxxxxxx x x x x |x x x x | ... .
xxxxxxxx x x x x | x x x x| ... .
+−−−−−−−−+ +−+−+−+ ... +

2. Écrire un algorithme permettant d’écrire une 1 2 3 4 5 6 7 8 9 10

table de multiplication comme celle présentée ci- 2 4 6 8 10 12 14 16 18 20
contre. Dans un premier temps on ne s’occupera 3 6 9 12 15 18 21 24 27 30
pas du nombre d’espaces entre les nombres, puis 4 8 12 16 20 24 28 32 36 40
on affinera en en tenant compte. 5 10 15 20 25 30 35 40 45 50
...
10 20 30 40 50 60 70 80 90 100
Exercice 9 – Tableaux
1. Que font les algorithmes suivants ?
1 var i, n[10] entier 1 var i, n[10] entier
2 debut 2 debut
3 n[0] ← 1 3 pour i allantde 0 a 9
4 pour i allantde 1 a 9 4 faire
5 faire 5 n[i] ← 2 * i
6 n[i] ← n[i-1] + 2 6 fin
7 fin

2. Écrire un algorithme qui déclare un tableau de 10 éléments et initialise toutes ses valeurs à 1
3. Écrire un algorithme qui calcule les n premiers nombres premiers.

Exercice 10 – Le triangle de Pascal

Écrire un algorithme permettant de calculer le triangle de Pascal au rang n, dans 1
lequel à la ligne i et à la colonne j (0 ≤ j ≤ i) est placé le coefficient binomial Cji . 1 1
On le construit aisément par récurrence, en remarquant qu’à chaque ligne i, le coef- 1 2 1
ficient numéro j est la somme des coefficients j − 1 et j de la ligne précédente (pour 1 3 3 1
0 < j < i). Les lignes 1 et 2 sont initialisées à 1 ainsi que les coefficients 1 et i de 1 4 6 4 1
chaque ligne i. 1 5 10 10 5 1
Autrement dit :
i−1
∀i, j | 0 < j < i, Cji = Cj−1 + Cji−1

0 i
Ci = Ci = 1

Master Handi – Université Paris 8 Algo – TD – 3

Exercice 11 – Fonctions numériques
1. Écrire une fonction qui calcule la somme de 3 entiers fournis en arguments
2. Écrire une fonction qui calcule la moyenne des éléments d’un tableau. Le tableau et la taille du tableau sont fournis
en argument
3. Écrire une fonction qui affiche la décomposition en facteurs premiers d’un nombre. Indication : le plus petit
diviseur strictement supérieur à 1 d’un nombre est nécessairement premier.
|ab|
4. En utilisant la fonction PGCD vue en cours, écrire une fonction PPCM. On rappelle que P P CM (a, b) = P GCD(a,b) .

Exercice 12 – Fonctions de traitement de chaînes de caractères

On donne le type chaine pour représenter les chaînes de caractères. On utilisera l’opérateur + pour concaténer des chaînes
et on donne les 2 fonctions suivantes :
fonction taille(var s : chaine par variable) : renvoie la taille de la chaîne, en entier.
fonction charAt(var s : chaine par variable, var i : entier par valeur) :
renvoie le caractère numéro i de la chaîne.
1. Écrire une fonction contient qui prend 2 chaînes en paramètres en renvoie vrai si la seconde est incluse dans la
première.
2. Écrire une fonction qui purge une chaîne d’un caractère, la chaîne comme le caractère étant passés en argument.
Si le caractère spécifié ne fait pas partie de la chaîne, celle-ci devra être retournée intacte. Par exemple :
— purge("Bonjour","o") renverra "Bnjur".
— purge(" J’aime pas les espaces "," ") renverra "J’ aimepaslesespaces ".
— purge("Moi, je m’en fous ", "y") renverra "Moi, je m’en fous".
3. Écrire deux fonctions start et end qui prennent 1 chaîne s et un entier n en paramètres et qui renvoient une chaîne
contenant respectivement les n premiers caractères et les n derniers caractères de s
4. Écrire une fonction middle qui prend 1 chaîne et 2 entiers p et q en paramètres et qui renvoie la partie de la chaîne
comprise entre les caractères p et q. On utilisera les fonctions définies précédemment.

Exercice 13 – Fonctions récursives

1. Écrire un algorithme de PGCD récursif. On rappelle que si q < p alors P GCD(p, q) = P GCD(p − q, q).
2. On reprend la Suite de Fibonacci, qu’on a déjà utilisée dans l’exercice 6 sur les suites.

u0 = 0, u1 = 1
un+2 = un+1 + un

(a) Écrire une fonction récursive de calcul du terme de rang n de cette suite. Qu’en pensez vous ?
(b) On peut montrer que :
u2k = 2uk−1 uk + u2k = (2uk−1 + uk )uk

u2k+1 = u2k+1 + u2k
En déduire une nouvelle fonction récursive. Est-elle plus efficace ?

Exercice 14 – Problème des 8 reines

Il s’agit de trouver les différentes façons de placer 8 reines sur un échiquier (8x8 cases) sans qu’elles ne se menacent
mutuellement, conformément aux règles du jeu d’échecs (on ne tient pas compte de la couleur des pièces).

Master Handi – Université Paris 8 Algo – TD – 4