12 Exercices corrigés sur les structures algorithmiques

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é.

structures algorithmiques

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 ?

structure données

structure données

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.

algorithme multiplication égyptienne

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

algorithme multiplication égyptienne

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.

algorithme multiplication égyptienne

Ce qui donne l’algorithme suivant :

multiplication egyptienne

Vous n’êtes pas obligé d’utiliser une variable temp pour permuter deux valeurs. Voici une autre version de l’algo :

multiplication egyptienne

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 !

algorithme permutation

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).

algorithme maximum

L’idée serait de retourner le maximum sans utilisation de variables supplémentaires.

algorithme maximum trois variables

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 !)

algorithme maximum optimisé

c- On vient de le faire plusieurs fois… pour ceux qui n’ont pas suivi.

algorithme permutation

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)

algorithme signe identique

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.

algorithme somme

algorithme minimum maximum

algorithme reste du quotient

algorithme produit

algorithme diviseur

algorithme diviseurs

algorithme nombre premier

algorithme somme des chiffres

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-

algorithme facture

Il est possible de mettre les embranchements en séquentiel, mais cela est moins performants en temps de calcul.

10-

algorithme saison

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-

structure de controle

2-

structure de controle

3-

structure de controle

4-

structure de controle

Exercice 7

Écrire un algorithme pour afficher les n premiers termes des suites suivantes (n demandé à l’utilisateur) :

algorithme suite

Exercice 8

Écrire un algorithme qui calcule les n premiers nombres premiers.

Exercice 9

algorithme triangle de pascal

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.

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.

nombre parfait

Voici un algorithme pour crible_parfait :

crible nombre 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)

algorithme nombre de maximum

Ou alors de tout faire dans une seule boucle :

algorithme nombre de maximum

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é) ; est le nombre de ces points qui est dans le quart de cercle.

algorithme calcul pi monte-carlo

Partager