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
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 2
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 3
Un magasin de reprographie facture 2 euros les dix premières photocopies, 1.50 euros les vingt suivantes et 1 euros au-delà. Ecrivez un algorithme qui demande à l’utilisateur le nombre de photocopies effectuées puis affiche le montant correspondant.
Il est possible de mettre les embranchements en séquentiel, mais cela est moins performants en temps de calcul.
Exercice 4
Ecrire un algorithme permettant d’afficher la saison en introduisant le numéro du mois.
Exercice 5
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.
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é).
FR 
EN 
ES