Les exercices corrigés suivants concernent les structures algorithmiques, les structures de contrôle et les structures de données. L’objectif est de proposer les structures les plus adaptées à l’énoncé.
Exercice 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 ?
Dans la plupart des langages de programmation le dernier exemple (1.6) ne générera pas d’erreur mais le résultat ne sera pas souvent ’3’. Selon le langage, ce sera la concaténation de ces caractères en une chaîne de caractères “ab” (cas des langages Python ou javascript), voire “a+b” (cas du shell) ou bien la somme des codes ASCII correspondant aux caractères ’1’ et ’2’, soit 49 + 50 = 99 : le caractère ’c’ (cas des langages C, C++ ou java). Dans très peu de langages, comme PHP ou perl, en revanche, le résultat sera bien 3. Enfin dans d’autres langages comme pascal, qui est un langage fortement typé, la compilation générera une erreur.
Exercice 2
Cette technique de multiplication, utilisée dans l’Egypte antique, ne nécessite pas de connaitre toutes les tables de multiplication jusqu’à 10 mais seulement l’addition et la multiplication par 2.
En voici par exemple la multiplication de 13 par 78. Il faut d’abord écrire la table des puissances de 2 inférieures ou égales à 13. Ensuite, écrire la table des doubles du nombre 78.
Ensuite, il faut cocher les plus grandes puissances de 2 décomposant le nombre 13 (c’est à dire que le bit binaire est égale à 1). Autrement dit, cochez les puissances de 2 entrant dans la conversion binaire du nombre 13 = 1101
La somme est 78+312+624=1014.
a – Calculer le produit de votre choix à l’aide de l’algorithme de la division égyptienne.
b – Est-il plus facile de calculer le produit de 78 par 13 ? Pourquoi ?
c – Ecrire l’algorithme de la multiplication égyptienne (d’après votre réponse de b !). Essayez de l’optimiser au mieux !
Le plus facile est de choisir le plus petit nombre pour la puissance de 2 et donc le plus grand nombre à doublé. En effet, le nombre d’itération est égale au nombre de fois qu’il faut multiplié 2 par lui même pour être plus grand que le nombre moins une itération (on ne garde que ce qui est strictement inférieur. On aura donc un nombre d’itération n tel que 2n > a (a décrit le nombre). On en déduit que n>log2(a) d’où l’intérêt que a soit le plus petit.
On rappelle tout d’abord la transformation binaire d’un nombre décimal.
Ce qui donne l’algorithme suivant :
Vous n’êtes pas obligé d’utiliser une variable temp pour permuter deux valeurs. Voici une autre version de l’algo :
Exercice 3
a – Ecrire un algorithme dont les paramètres sont trois variables réelles et qui permute circulairement les valeurs de celles-ci.
b – Ecrire un algorithme dont les paramètres sont trois variables réelles et retourne la valeur maximale parmi ces trois valeurs.
c – Ecrire un algorithme qui permette les valeurs de deux variables sans utiliser de variable supplémentaire.
d – Ecrire un algorithme qui retourne vrai si deux entiers a et b sont de même signe, sinon faux
a – Les variables a, b et c sont des variables définies à l’extérieur de l’algorithme. Ces valeurs sont modifiés même si l’on ne retourne rien. Attention à l’ordre de vos opérations !
Vous pouvez aussi le faire sans prendre de variable supplémentaire. Dans ce cas on aura au début (a,b,c). On permute par exemple a et b grâce aux opérations suivantes :
a ← a + b
b ← a – b
a ← a – b
On a donc le triplé de valeurs (b,a,c). Il reste à permuter a et c pour avoir le triplé (b,c,a).
Ou alors vous pouvez aussi permuter les trois valeurs à l’aide d’une série de calculs.
a ← a + b + c ;
c ← a – b – c ;
b ← a – b – c ;
a ← a – b – c ;
b- Ici l’algorithme doit retourner une valeur, il y a donc des entrées et des sorties. Il y a beaucoup de façon de faire les choses, à vous de trouver des variantes (avec plusieurs conditions dans le branchement par exemple).
L’idée serait de retourner le maximum sans utilisation de variables supplémentaires.
Ce n’est pas très joli là non plus, on va donc chercher à retourner le maximum une seule fois sans utiliser de nouvelles variables. On va permuter les valeurs pour stocker le maximum dans x (attention, en fonction des langages vous pouvez avoir un réel impact sur les valeurs dans x y et z, donc à utiliser avec précaution !)
c- On vient de le faire plusieurs fois… pour ceux qui n’ont pas suivi.
d- On va réfléchir à un algo bien optimisé pour éviter de faire plein d’embranchement. Deux entiers de même signe auront leur produit positif ! (0 est à la fois positif et négatif)
Exercice 4
Ecrire un algorithme pour résoudre chacun des problèmes suivants : (essayer avec différentes structures de contrôles POUR, TANT QUE, FAIRE … TANT QUE, etc.).
1- Calcul de la somme des N premiers nombres entiers.
2- Recherche du minimum et du maximum dans un ensemble de N nombres.
3- Calcul du quotient et reste de la division de deux entiers A et B sans utiliser l’opération de division.
4- Le calcul du produit de deux entiers en utilisant uniquement l’opération d’addition ‘+’.
5- Détermination si A est divisible par B. Avec A et B des entiers positifs.
6- Déterminer tous les diviseurs d’un entier X donné.
7- Déterminer si un nombre entier X est premier ou non.
8- Calcule la somme des chiffres qui composent un entier naturel N.
9- Un magasin de reprographie facture 2 euros les dix premières photocopies, 1.50 euros les vingt suivantes et 1 euros au-delà.
10- Ecrire un algorithme permettant d’afficher la saison en introduisant le numéro du mois.
Erratum : au début R = N, sinon l’algo ne fait rien (on dit qu’il n’est pas correct car il ne résout pas le problème posé).
9-
Il est possible de mettre les embranchements en séquentiel, mais cela est moins performants en temps de calcul.
10-
Exercice 5
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 strictement 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 6
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.
1-
2-
3-
4-
Exercice 7
Écrire un algorithme pour afficher les n premiers termes des suites suivantes (n demandé à l’utilisateur) :
Exercice 8
Écrire un algorithme qui calcule les n premiers nombres premiers.
Exercice 9
Exercice 10
Un entier positif est dit parfait s’il est égal à la somme de ses diviseurs (excepté lui-même). Par exemple 6 est parfait, car 6 = 1 + 2 + 3 ; de même 28 est parfait, car 28 = 1 + 2 + 4 + 7 + 14.
Ecrire une fonction booléenne parfait pour un entier n. Optimiser.
Faire une procédure crible_parfait qui recherche et affiche, à l’aide d’un crible, les nombres parfaits sur un intervalle de 1 à M .
On prévoit de stocker pour chaque entier la somme de ses diviseurs, somme qui sera calculée pendant le crible : le principe du crible est, pour chaque entier i de l’intervalle, de parcourir les multiples de i auxquels on somme le diviseur i.
Voici un algorithme assez simple à penser pour trouver un nombre parfait.
On peut aussi initialiser s à 1 et démarrer la boucle à 2, mais attention la fonction doit renvoyer false pour i = 1 ; on doit alors rajouter un test à l’initialisation.
On peut optimiser la fonction en constatant que si i divise n, alors (n div i) est aussi un diviseur puisque i (n div i) = n.
Il suffit de faire varier i de 2 à √n : si i est diviseur, alors le diviseur (n div i) est dans l’intervalle √n à n ; donc on a tous les diviseurs.
Il faut penser à démarrer à 2 pour ne pas ajouter n. Il y a aussi un problème si n est un carré : on aura ajouté 2 fois le diviseur r = √n.
Voici un algorithme pour crible_parfait :
Les nombres parfaits entre 1 et 10 000 000 sont 6, 28, 496, 8128.
Exercice 11
Ecrire une fonction qui renvoie le nombre d’occurrences de la valeur maximum présente dans un tableau non trié. Construire l’algorithme en 0(n).
Il est possible de le faire un deux temps, on aura une complexité de 2n=O(n)
Ou alors de tout faire dans une seule boucle :
Exercice 12
On considère un carré Q dans lequel on positionne aléatoirement un grand nombre de points. Le rapport entre le nombre de points figurant dans le cercle inscrit dans Q et le nombre de points tirés s’approche du rapport entre la surface du disque inscrit dans Q et la surface du carré Q. On en déduit une valeur approchée de π. Cette méthode s’appelle une simulation de Monte-Carlo (très utile en finance !).
Soit r le rayon du cercle. L’aire du cercle est πr2 et l’aire du carré est 4r2. Pour simplifier on prend r = 1, et on se limite au quart de plan R+ × R+ .
random(m) fournit un entier entre 0 et m-1, tandis que random sans paramètre fournit un réel entre 0 et 1.
Pour savoir si un point (x, y) ∈ au quart de cercle on teste si √(x² + y²) ≤ 1.
Comme le calcul de la racine carrée est couteux, on se contente de faire le test équivalent (x² + y²) ≤ 1. Pour cela on peut utiliser la fonction sqr qui est plus optimisé que x*x.
n est le nombre total de points tirés (tous dans le quart de carré) ; c est le nombre de ces points qui est dans le quart de cercle.
FR 
EN 
ES