Algorithmique impérative/Problèmes

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

Inverser deux variables[modifier | modifier le wikicode]

Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problèmatique[modifier | modifier le wikicode]

Nous disposons de deux entiers a et b. Nous voulons intervertir ces deux nombres. À la fin du programme : la valeur de a sera égale à celle de b lors du lancement du programme et inversement : b sera égal au a initial.

Exemple : au début du programme nous posons a=2 et b=3. À la fin du programme nous aurons a=3 et b=2.

Solutions[modifier | modifier le wikicode]

Voici deux solutions acceptables :

Algorithme inversion_stockage
Variables
  a : entier
  b : entier
  temp : entier (* variable dans laquelle on stockera le contenu
                   d'une variable pour ne pas l'écraser au moment
                   de la première assignation *)
Début
  temp := a (* on sauvegarde a qui sera effacée à la ligne suivante
               pour pouvoir la placer dans b plus tard *)
  a := b
  b := temp
Fin
Algorithme inversion_calcul
Variables
  a : entier
  b : entier
Début
  a := a+b
  b := a-b
  a := a-b
Fin

Remarque[modifier | modifier le wikicode]

Ces deux solutions présentent en fait une notion clé de l'informatique : étudions nos deux solutions de plus près :

Simplifions le fonctionnement d'une machine au maximum : supposons

  • Qu'il faut utiliser une unité de mémoire pour stoker une variable en mémoire
  • Qu'il faut une unité de temps au processeur pour effectuer un calcul et qu'une opération entière et l'assignation consistent toutes en 1 calcul.

Temps de calcul requis par chaque algorithme :

  • Pour inversion_stockage : 3 unités de temps (3 assignations)
  • Pour inversion_calcul : 6 unités de temps (3 assignations + 1 somme + 2 différences)

Mémoire requise par chaque algorithme :

  • Pour inversion_stockage : 3 unités de mémoire (a, b et temps)
  • Pour inversion_calcul : 2 unités de mémoire (a et b)

On a donc que

  • inversion_stockage prend plus de mémoire mais moins de temps de calcul que inversion_calcul
  • inversion_calcul prend plus de temps de calcul mais moins de mémoire que inversion_stockage

Et c'est là un concept généralisable :

D'une façon générale, vous pouvez faire des algorithmes plus rapides en utilisant plus de mémoire et des algorithmes utilisant moins de ressources mémoire mais qui seront plus lents.

Attention cependant, cela ne veut surtout pas dire qu'aucun algorithme n'est améliorable sans perte de ressources en calcul ou en mémoire. Bien au contraire, vous devez toujours essayer d'être le plus efficace possible.

Ce constat ne permet pas de dire si un des algorithmes est plus efficace que l'autre : notre analyse a été trop simplifiée pour cela. En effet, nous n'avons pas considéré que :

  • la mise en mémoire peut aussi prendre un temps non négligeable ;
  • peut-être que les calculs de sommes et de différences sont très coûteux en temps ;
  • peut-être que le processeur est assez avancé technologiquement pour effectuer un premier calcul et en commencer un deuxième avant d'avoir obtenu le premier résultat ;
  • l'algorithme pourrait utiliser des réels, et, en général, les calculs sur les réels sont plus longs que sur les entiers.

Vous contesterez, avec raison, que sur cet exemple, aujourd'hui nos ordinateurs sont parfaitement capables d'exécuter ces deux programmes en un temps record et qu'on ne distinguera pas la différence suivant qu'on utilise l'un ou l'autre. C'est vrai, mais vous négligez que peut-être :

  • ce programme sera exécuté sur une machine minuscule, une micro-puce de quelques millimètres dans laquelle on n'a pu mettre que très peu de mémoire et un minuscule processeur ;
  • ce programme doit pouvoir être exécuté simultanément des milliers de fois sur la même machine ;
  • ce programme ne sera pas exécuté plusieurs fois en même temps mais des milliers de fois, les unes après les autres, et que le programme ayant besoin d'inverser des milliers de valeurs à la suite doit pouvoir donner un résultat dans la seconde...

En réalité, n'importe quel compilateur décent, depuis les années 80, va optimiser bien au delà de ce que le programmeur moyen aura le courage de faire. Par exemple sur l'échange : utiliser deux registres au lieu d'une variable supplémentaire (R1 := A; R2 := B; A := R2; B:= R1) si les données tiennent dans un mot machine, ou utiliser les instructions spécialisées du processeur d'échange de deux zones en mémoire. En écrivant la forme la plus simple d'échange, le compilateur reconnaitra (parce qu'on lui a inculqué un certain nombre de recettes) de quoi il s'agit, et fabriquera le meilleur code possible. Le temps consacré à de la micro-optimisation est en général une perte sèche, il est de loin préférable de la consacrer à une bonne conception, et à l'utilisation d'algorithmes efficaces.

Un menu de sélection simple[modifier | modifier le wikicode]

Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Ce problème traite de la création d'une interface graphique rudimentaire dans un environnement textuel (un terminal).

Problématique[modifier | modifier le wikicode]

Nous supposons que nous avons déclaré 3 procédures dont les identifiants sont les suivants (peu nous importe ce qu'elles font : le sujet n'est pas ici)

  • Procedure_A
  • Procedure_B
  • Procedure_C

Vous devez créer le programme principal permettant à l'utilisateur de choisir laquelle des trois il veut lancer. Le programme doit avoir les fonctionnalités suivantes :

  • Une fois que la procédure choisie par l'utilisateur a été exécutée, le menu est de nouveau proposé.
  • L'utilisateur doit pouvoir quitter le programme depuis le menu.
  • Le programme doit expliquer à l'utilisateur comment utiliser le programme.
  • (optionnel) on suppose que l'utilisateur est distrait et qu'il peut ne pas donner une bonne réponse. Gérez ce cas.

Première analyse[modifier | modifier le wikicode]

Voici quelques idées directrices formant une première analyse de la problématique. Chacun de ces points seront analysés dans la section suivante.

  • ...permettant à l'utilisateur de choisir... : l'utilisateur doit intervenir. Il va falloir faire intervenir un Lire afin qu'il puisse nous donner son choix.
  • ...laquelle des trois... :
  • ...le menu est de nouveau proposé : il s'agit d'une répétition.
  • ...quitter le programme depuis le menu : une autre possibilité. En fait, l'utilisateur aura le choix entre quatre possibilités : A, B, C ou quitter.
  • ...expliquer à l'utilisateur comment utiliser le programme' : on affichera les instructions avec Afficher.

Analyse approfondie[modifier | modifier le wikicode]

Voici les réflexions qu'il faut mener sur les questions clés du problèmes.

Gérer le choix de l'utilisateur[modifier | modifier le wikicode]

Nous allons représenter le choix de l'utilisateur par un entier. Finalement, l'utilisateur à quatre possibilités pour le menu (entre parenthèse : l'entier que nous allons y associer) :

  • Exécuter la procédure A (1)
  • Exécuter la procédure B (2)
  • Exécuter la procédure C (3)
  • Quitter (0)

Nous allons donc lui poser la question "Que voulez vous faire ?", il répondra par un entier en fonction duquel on fera un SÉLECTIONNER.

(optionnel) l'utilisation d'une chaîne de caractères nous permettra de contrôler l'erreur si l'utilisateur entre autre chose que 1,2,3 ou 0. Si on utilise un entier et que l'utilisateur entre "truc" il va y avoir un problème (sur une machine, le programme se bloquera...).

L'utilisateur retrouve le menu[modifier | modifier le wikicode]

Pour que l'utilisateur retombe sur le menu, il va falloir utiliser une structure itérative, mais laquelle ? Petite réflexion :

  1. A priori, on ne sait pas combien de fois l'utilisateur va exécuter une procédure. Cela exclut le POUR.
  2. REPETER ou TANTQUE ? Le menu va s'afficher au moins une fois ce qui nous laisse penser qu'un REPETER est plus approprié. De plus la situation est bien décrite par la phrase "Afficher le menu jusqu'à ce qu'il choisisse de quitter", ce qui conforme notre choix. Nous utiliserons donc un REPETER.

Solution finale[modifier | modifier le wikicode]

Algorithme menu
(* on suppose que les procédures sont déclarées *)
Procedure_A ...
Procedure_B ...
Procedure_C ...
Variables
  reponse : chaîne de caractères (* entrée de l'utilisateur *)
Debut
  Répéter
    Afficher("Que voulez-vous faire ? Donnez l'entier correspondant")
    Afficher("1 : exécuter la procédure A")
    Afficher("2 : exécuter la procédure B")
    Afficher("3 : exécuter la procédure C")
    Afficher("0 : quitter")
    Lire(reponse)
    Sélectionner reponse parmi
      1 : Procedure_A()
      2 : Procedure_B()
      3 : Procedure_C()
      0 : (* on ne fait rien *)
      * : Afficher("Merci d'entrer un code valide")
  Jusqu'à (reponse='0')
Fin

Somme des n premiers entiers[modifier | modifier le wikicode]

Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problématique[modifier | modifier le wikicode]

Écrire un algorithme sous forme d'une fonction qui calcule la somme des premiers entiers jusqu'à n inclus, n étant passé en paramètre.

Exemple : somme(5) calculera 1+2+3+4+5 et renverra donc 15

Solution[modifier | modifier le wikicode]

Voici une première réponse acceptable :

 Function somme(n : entier)
 Lexique
   somme : entier (* la somme qu'on complète au fur et à mesure et qu'on retournera à la fin *)
 Début
   somme:=0
   POUR i de 0 à n
     somme:=somme+i
   FP
   retourner somme
 Fin

Pourquoi partir de 0 et pas 1 ? Cela sert tout simplement à gérer le cas n=0. Cela ne change rien pour les autres cas puisque (en reprenant l'exemple de la problématique) somme(5) va calculer 0+1+2+3+4+5, c'est à dire 1+2+3+4+5 (=15).

Cependant, la boucle peut partir de 1 si elle ne s’exécute pas pour n=0. Dans ce cas, la somme sera 0 (valeur initiale de la variable somme).

Remarque[modifier | modifier le wikicode]

Essayons une analyse un peu plus mathématique du problème :

En fait notre fonction calcule pour n : . L'étude des séries nous apprend que

.

On peut en déduire que la fonction peut s'écrire

Function somme_directe(n : entier)
Début
  retourner (n*(n+1))/2
Fin

Ce qui d'une part est plus simple mais également, comme nous allons le voir, plus efficace.

Simplifions le fonctionnement d'une machine au maximum : supposons qu'il faut une unité de temps au processeur pour effectuer un calcul et qu'une opération entière et l'assignation consistent toutes en 1 calcul.

Supposons que nous voulions calculer somme(1000) : Avec somme() : nous allons effectuer :

  • 1000 incrémentation de i
  • 1000 sommes somme+i
  • 1000 assignation

Soit au moins 3000 calculs.

Avec somme_directe() : nous allons effectuer

  • une somme : n+1
  • une multiplication n*(n+1)
  • une division par 2

Soit 3 calculs.

Conclusion : 3000 calculs pour le premier algorithme, 3 calculs pour le second. La différence entre les deux : le mathématicien qui doit se retrouver en chaque algorithmicien.

Et dire que de nombreux étudiants en informatique sont souvent étonnés de la présence importante de mathématiques durant leur cursus...

(pour info : Wikilivres propose des cours de mathématiques...)

PGCD de deux nombres[modifier | modifier le wikicode]

Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problèmatique[modifier | modifier le wikicode]

Écrire un algorithme donnant le Plus Grand Commun Diviseur (PGCD) de deux nombres donnés par l'utilisateur. On supposera que l'utilisateur ne donne que des entiers strictement supérieurs à zéro.

Il faudra écrire une fonction, prenant en entrée deux entiers strictement positifs et renvoyant leur PGCD. L'algorithme principal y fera appel.

Question subsidiaire : on considérera que l'utilisateur peut entrer n'importe quels entiers. Tenez-en compte pour que l'algorithme ne commette pas d'erreur et qu'il informe l'utilisateur.

Aide[modifier | modifier le wikicode]

Il faut avoir étudié ce problème d'algèbre pour avoir la solution. Elle consiste à appliquer l'algorithme d'Euclide.

Solution[modifier | modifier le wikicode]

 1 Algorithme pgcd
 2 
 3 Fonction euclide( u : entier
 4                    v : entier ) : entier
 5 Variables
 6   r : entier (* le reste d'une division entière *)
 7 Début
 8   Tant que v <> 0 faire
 9     r := u mod v
10     u := v
11     v := r
12   FTQ
13   retourner u
14 Fin
15 
16 Variables
17   u,v : entier (* les deux entiers donnés par l'utilisateur *)
18 Début
19   Écrire("Donner les deux nombres : ")
20   Lire(u,v)
21   (* Début question subsidiaire *)
22   si u=0 et v=0 alors Écrire("Le PGCD n'existe pas")
23   sinon début
24     si u < 0 alors u := -u
25     si v < 0 alors v := -v
26     (* Fin Question subsidiaire *)
27     Écrire(euclide(u,v))
28   fin
29 Fin

Pas vraiment de difficulté pour l'algorithme principal. La difficulté étant la fonction implémentant l'algorithme d'Euclide. Le jeu d'assignation à répéter jusqu'à obtenir un reste nul est difficile à visualiser.

Question subsidiaire : il y a trois événements à contrôler :

  • Le cas où u=v=0 et où le PGCD n'existe pas et il faut arrêter le programme (ligne 22)
  • Le cas où u ou v (ou les deux) est négatif est il faut prendre son opposé (lignes 24 et 25)

Pour la solution sans la question subsidiaire : ôter les lignes 21 à 26 et la 28 de la solution proposée.

Trier un tableau[modifier | modifier le wikicode]

Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problématique[modifier | modifier le wikicode]

Voici un problème fondamental d'informatique.

Supposons qu'il soit déclaré tab, un tableau.

Pour écrire le programme on prendra la déclaration suivante

 var
   tab : tableau MIN à MAX de T

Pour simplifier le problème, vous pourrez considérer que T = entier.

Note : sachez toutefois que les opérateurs <, <=, >, >= sont génériques et permettent de comparer toutes données tant qu'elles font partie du même ensemble ordonné (Par exemple : l'alphabet).

Question subsidiaire : considérez le cas particulier où les éléments sont distincts. L'algorithme fonctionne-t-il ?

Solution[modifier | modifier le wikicode]

Il est tout d'abord important de savoir qu'il existe de nombreuses façon de procéder. Pour connaitre ces algorithmes de tri, élément important de la culture de tout algorithmicien, nous vous invitons à consulter l'article « Algorithme de tri » sur Wikipédia ainsi que les articles sur les différents algorithmes de tri existants.

Pour vous corriger : vérifiez que votre algorithme ne tombe pas sur une erreur courante en supposant que tous les entiers sont distincts. En effet, il est facile de faire un algorithme qui, voulant inverser deux éléments pour les remettre en ordre, boucle sans fin en voulant inverser sans fin : lorsqu'il tombe sur deux éléments égaux.

Une solution "simple"[modifier | modifier le wikicode]

Le tri par sélection est un des plus simples algorithmes de tri. Il consiste à rechercher le plus petit (ou le plus grand) élément du tableau et de le placer à sa place définitive : au début (ou à la fin du tableau). Une fois un tel élément placé à sa place définitive, on recommence avec le reste du tableau. Lorsqu'on place un élément, on n'écrase pas ce qui était là (on perdrait un élément du tableau) mais on le déplace à la position qu'on vient de libérer (ce qui revient à faire une permutation).

Une implémentation testable en Pascal[modifier | modifier le wikicode]

 1 program tris;
 2 
 3 const
 4 	DEB = 0;
 5 	FIN = 5;
 6 
 7 type
 8 	T_tabint = array [DEB..FIN] of integer;
 9 
10 procedure permuter(var i : integer; var j : integer);
11 (* à la fin, i vaut le j donné et j vaut le i donné *)
12 var
13 	tmp : integer; (* un tampon pour stocker l'élément que va remplacer l'élément minimum pendant l'inversion *)
14 begin
15 	tmp := i;
16 	i := j;
17 	j := tmp
18 end;
19 
20 procedure afficher(var t : T_tabint);
21 (* procédure qui affiche le tableau passé en paramètre *)
22 (* sur une ligne et sous la forme [a|b|c|d...|l|m] *)
23 
24 var
25 	i : integer; (* variable de boucle *)
26 begin
27 	write('[');
28 	for i := DEB to FIN-1 do write(t[i],'|');
29 	write (t[FIN],']');
30 end;
31 
32 procedure remplir(var t : T_tabint);
33 (* procédure qui remplit le tableau passé en paramètre *)
34 (* avec des nombres aléatoires pris entre 0 et 99 *)
35 
36 var
37 	i : integer; (* variable de boucle *)
38 begin
39 	for i := DEB to FIN do t[i] := random(99);
40 end;
41 
42 
43 procedure TriSelection(var t : T_tabint);
44 var
45 	i, j	: integer;	(* variables de boucle *)
46 	min		: integer;	(* indice du plus petit élément parmi ceux qui reste à trier *)
47 	
48 begin
49    for i:=DEB to FIN-1 do begin
50       min := i;
51       for j:=i+1 to FIN do
52          if (t[j] < t[min]) then min:=j;
53 
54       if (i <> min) then permuter(t[i],t[min]);
55    end; 
56 end;
57 
58 procedure TriBulle(var t: T_tabint);
59 var
60 	i, j	: integer;	(* variables de boucle *)
61  
62 begin
63   for i:=DEB to FIN-1 do begin
64     j := i+1;
65     for j := FIN-1 downto i do
66     	if t[j+1]<t[j] then permuter(t[j],t[j+1]);
67   end;
68 end;
69 
70 var
71 	tab : T_tabint;
72 
73 begin
74 
75 	(* pour chaque tri on recrée un tableau aléatoire, on l'affiche *)
76 	(* puis on le trie et on l'affiche à nouveau *)
77 
78 	(* Tri sélection *)
79 	writeln('TRI SELECTION');
80 	remplir(tab);
81 	afficher(tab);
82 	writeln(' <- tableau donné');
83 	TriSelection(tab);
84 	afficher(tab);
85 	writeln(' <- tableau trié');
86 		
87 	(* Tri bulle *)
88 	writeln('TRI BULLE');
89 	remplir(tab);
90 	afficher(tab);
91 	writeln(' <- tableau donné');
92 	TriBulle(tab);
93 	afficher(tab);
94 	writeln(' <- tableau trié');
95 	
96 end.

Voici un exemple d'exécution :

TRI SELECTION
[54|58|70|83|59|84] <- tableau donné
[54|58|59|70|83|84] <- tableau trié
TRI BULLE
[53|83|41|61|63|38] <- tableau donné
[38|41|53|61|63|83] <- tableau trié

Rechercher un élément dans un tableau[modifier | modifier le wikicode]

Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problèmatique[modifier | modifier le wikicode]

Supposons que nous avons déclaré un tableau tab d'entiers comme suit :

Variables
  tab : tableau MIN à MAX de entiers

Supposons que ce tableau est rempli d'entiers inconnus mais triés dans l'ordre croissant.

Proposez un algorithme qui, étant donné un entier indiqué par l'utilisateur, trouve son indice dans le tableau. On supposera que l'entier indiqué par l'utilisateur est effectivement dans le tableau.

Aide[modifier | modifier le wikicode]

Vous remarquerez que ce problème s'apparente au problème de recherche d'un mot dans le dictionnaire. Pensez donc à la méthode que vous employez dans cette situation...

Solutions[modifier | modifier le wikicode]

Solutions moyennes[modifier | modifier le wikicode]

Voici une solution, qui n'est pas celle attendue. L'algorithme parcourt le tableau du début à la fin et compare l'élément à l'entier indiqué par l'utilisateur. Il s'arrête lorsqu'il est trouvé. Remarquez que la faiblesse de cette algorithme provient du fait qu'il fonctionne même quand le tableau n'est pas trié, il n'exploite donc pas cet avantage trop important pour être négligé.

 1 Algorithme recherche
 2 Variables
 3   q : entier (* l'entier recherché *)
 4   i : entier (* ce sera l'indice de parcours *)
 5 Début
 6   Afficher("Donner l'entier à trouver")
 7   Lire(q)
 8   i ← MIN
 9   tantque tab[i] != q
10     i ← i+1
11   ftq
12   Afficher("L'indice où se trouve ", q ," est ", i)
13 Fin

L'algorithme suivant fonctionne mais à le défaut de continuer à parcourir le tableau même quand l'élément a été trouvé.

 1 Algorithme recherche_mauvais
 2 Variables
 3   q : entier (* l'entier recherché *)
 4   i : entier (* ce sera l'indice de parcours pour la boucle *)
 5   resultat : entier (* l'indice résultat sera stocké ici *)
 6 Début
 7   Afficher("Donner l'entier à trouver")
 8   Lire(q)
 9   i ← MIN
10   pour i de MIN à MAX (* on parcourt tout le tableau *)
11     si tab[i] = q alors resultat ← i (* si on a trouvé on mémorise l'indice *)
12   ftq
13   Afficher("L'indice où se trouve ", q ," est ", résultat)
14 Fin

Solution attendue[modifier | modifier le wikicode]

Voici enfin la solution attendue. Vous étiez peut-être arrivé à cette déduction seul ou en consultant l'aide mais vous avez compris que ce problème s'apparente à celui de la recherche dans un dictionnaire. En effet, on cherche un mot dans un ensemble de mots inconnus mais triés.

Si vous avez déjà cherché un mot dans le dictionnaire, vous avez certainement remarqué que lire le premier, regarder si c'est celui qu'on cherche, puis passer au suivant, et ainsi de suite n'est pas la solution la plus efficace...

La solution est donc l'algorithme de recherche dichotomique (du grec « dichotomie » : « couper en deux »). On ouvre le dictionnaire au milieu et un prend un mot au hasard, si le mot qu'on cherche est avant, recommence avec la première moitié du dictionnaire, s'il est après, avec la deuxième moitié. Dans la bonne moitié on prend un mot au milieu, etc...

 1 Algorithme recherche_dichotomique
 2 Variables
 3   q : entier         (* l'entier recherché *)
 4   i : entier         (* ce sera l'indice de parcours pour la boucle *)
 5   deb, fin : entiers (* deux entiers pour désigner le début et la fin de la zone dans laquelle on recherche *)
 6 Début
 7   Afficher("Donner l'entier à trouver")
 8   Lire(q)
 9   (* on commence en recherchant dans tout le tableau *)
10   deb ← MIN
11   fin ← MAX
12   répéter
13     i = arrondir((fin+deb)/2) (* on prend i entre deb et fin *)
14     si tab[i] > q
15       alors fin ← i (* on est tombé trop haut : on ramène la borne supérieure *)
16       sinon si tab[i] < q
17               alors deb ← i (* on est tombé trop bas : on ramène la borne inférieure *)
18   jusqu'à tab[i]=q
19   Afficher("L'indice où se trouve ", q ," est ", i)
20 Fin

Traduction en Pascal[modifier | modifier le wikicode]

Voilà sa traduction en Pascal, le tableau étant rempli à la main :

 1 program recherche_dichotomique;
 2 Const
 3   MIN = 0;
 4   MAX = 10;
 5 Var
 6   tab : array [MIN..MAX] of integer;
 7   q : integer;         (* l'entier recherché *)
 8   i : integer;         (* ce sera l'indice de parcours pour la boucle *)
 9   deb, fin : integer;  (* deux entiers pour désigner le début et la fin de la zone dans laquelle on recherche *)
10 Begin
11   tab[0] := 1;
12   tab[1] := 4;
13   tab[2] := 9;
14   tab[3] := 10;
15   tab[4] := 24;
16   tab[5] := 24;
17   tab[6] := 74;
18   tab[7] := 75;
19   tab[8] := 76;
20   tab[9] := 90;
21   tab[10] := 99;
22   Writeln('Donner l''entier à trouver : ');
23   Readln(q);
24   (* on commence en recherchant dans tout le tableau *)
25   deb := MIN;
26   fin := MAX;
27   repeat
28     i := round((fin+deb)/2); (* on prend i entre deb et fin *)
29     if tab[i] > q
30       then fin := i (* on est tombé trop haut : on ramène la borne supérieure *)
31       else if tab[i] < q
32               then deb := i; (* on est tombé trop bas : on ramène la borne inférieure *)
33   until tab[i]=q;
34   Writeln('L''indice où se trouve ', q ,' est ', i);
35 End.

Jeu du Tas de billes[modifier | modifier le wikicode]

Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problématique[modifier | modifier le wikicode]

On cherche à implémenter un jeu dont voici les règles :

Règles du jeu :

  • On commence avec un tas de billes, le jeu se joue à deux,
  • Les joueurs jouent l'un après l'autre,
  • Chaque joueur, à son tour, peut retirer une, deux, ou trois billes du tas,
  • Le joueur qui prend la dernière bille a perdu.

En plus d'implémenter le mécanisme du jeu, on veillera à respecter les consignes suivantes :

  • Au lancement, le programme rappelle les règles du jeu énoncées ci-dessus.
  • Le contenu du tas de départ est demandé au lancement. Si le nombre donné est 0 ou moins, on prend un nombre aléatoire entre 10 et 30 et on l'annonce.
  • Les deux joueurs entreront leurs noms en début de partie.
  • À chaque tour, le programme rappelle à qui est le tour, en appelant les joueurs par leurs noms. Pour qu'on voie que le tour à passé, l'affichage est vidé des informations et saisies du tour précédent.
  • À chaque tour, le programme rappelle combien il reste de billes dans le tas et donne une représentation graphique s'il reste moins de 30 billes (afficher sur une seule ligne un '.' par bille restante fera amplement l'affaire).
  • Le programme gère les tentatives de triche et rappelle les règles si nécessaire.
  • À la fin du jeu, le gagnant est désigné par son nom.

Première analyse[modifier | modifier le wikicode]

Analyse approfondie[modifier | modifier le wikicode]

Solution[modifier | modifier le wikicode]

Trouver un algorithme pour ce jeu n'est pas aussi évident qu'il y parait.

Implémentation en Pascal[modifier | modifier le wikicode]

 1 program billes;
 2 
 3 var
 4 	nb_billes :				integer;	(* le nombre de billes dans le tas *)
 5 	coup :					integer;	(* nombre de billes à retirer lors d'un tour*)
 6 	tour :					boolean;	(* vrai si c'est le tour du joueur 1 *)
 7 	joueur1, joueur2 :		string;		(* noms des joueurs *)
 8 	i :						integer;	(* variable de boucle *)
 9 
10 begin
11 	(* Affichage des règles *)
12 	writeln('Règles du jeu :');
13 	writeln('* On commence avec un tas de billes, le jeu se joue à deux.');
14 	writeln('* Les joueurs jouent l''un après l''autre.');
15 	writeln('* Chaque joueur, à son tour, peut retirer une, deux, ou trois billes du tas.');
16 	writeln('* Le joueur qui prend la dernière bille a perdu.');
17 	
18 	(* Recueil des informations nécessaires au jeu *)
19 	writeln('Donner le nom du joueur 1 : ');
20 	readln(joueur1);
21 	writeln('Donner le nom du joueur 2 : ');
22 	readln(joueur2);
23 	writeln('Donner le nombre de billes : ');
24 	readln(nb_billes);
25 
26 	(* gestion du nombre de billes *)
27 	if (nb_billes <= 0) then begin
28 		nb_billes := 10+random(20);	(* random(n) renvoie un nombre entre 0 et n *)
29 		writeln('Un nombre aléatoire est pris : ',nb_billes);
30 	end;
31 
32 	(* on démarre à false, ainsi c'est le joueur 1 qui jouera en premier *)
33 	tour := false;
34 
35 	repeat
36 		(* nettoyer l'écran, un appel de clsrc() peut fonctionner également *)
37 		for i:=1 to 20 do writeln();
38 
39 		(* on change le joueur à qui est le tour *)
40 		tour := not(tour);
41 
42 		(* on indique à qui est le tour *)
43 		write('C''est au tour de ');
44 		if (tour) then writeln(joueur1) else writeln(joueur2);
45 
46 		(* affichage (textuel et graphique) du nombre de billes restant *)
47 		writeln('Il reste ',nb_billes,' billes. ');
48 		if (nb_billes <= 30) then for i:= 1 to nb_billes do write('.');
49 		writeln();
50 
51 		(* demande au joueur son coup , gestion de la triche *)
52 		writeln('Combien retirez-vous de billes ?');
53 		readln(coup);
54 		while ((coup < 1) or (coup > 3) or (coup > nb_billes)) do begin
55 			writeln('Tricheur !');
56 			writeln('* On ne peut retirer qu''entre une et trois billes.');
57 			writeln('* On ne peut plus de billes qu''il n''y en a.');
58 			writeln('Combien retirez-vous de billes ?');
59 			readln(coup)
60 		end;
61 
62 		(* on a le coup voulu, on le joue *)
63 		nb_billes := nb_billes - coup
64 
65 	until (nb_billes = 0);
66 
67 	(* c'est le joueur qui a joué en dernier qui est perdant *)
68 	(* on inverse pour indiquer le gagnant *)
69 	if (not(tour)) then write(joueur1) else write(joueur2);
70 	writeln(' gagne !');
71 
72 end.

Quiz[modifier | modifier le wikicode]

Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problématique[modifier | modifier le wikicode]

On cherche à implémenter un programme qui, étant donnée une base de données de questions et de réponses correspondantes posent les questions et demande la réponse à un joueur. Le programme comptabilise les bonnes réponses et donne le score final. Le nombre de questions à poser est demandé au début de la partie, si le nombre donné est nul ou négatif, on choisit un nombre aléatoire entre un et le nombre de questions dans la base de données.

Les réponses seront soit

  • vrai/faux
  • une réponse en toutes lettres
  • une réponse sous forme de nombre

Il est demandé d'implémenter seulement une de ces trois possibilités.

  • À chaque question, le score actuel et le nombre de questions restantes est affiché
  • On ne demande pas que le programme ne pose pas deux fois la même question au cours d'une même partie, réfléchir tout de même à un moyen de faire cela.

Données[modifier | modifier le wikicode]

questions : tableau de 0 à NBQ de chaine; (* bases de données des questions *)
réponses : tableau de 0 à NBQ de T (* bases de données des réponses *)

On suppose ces tableaux remplis, bien évidement la réponse à la question questions[i] est réponses[i]. T est booléen, integer, ou chaine : à vous de choisir et d'assumer ce choix dans l'algorithme.

Solution[modifier | modifier le wikicode]

Implémentation en Pascal[modifier | modifier le wikicode]

L'auteur vous demande de l'excuser pour la piètre qualité du contenu de la base de données...

 1 program quiz;
 2 
 3 const
 4 	NBQ = 4; (* nombre de questions dans la base de données *)
 5 
 6 var
 7 	questions :       array [1..NBQ] of string; (* bases de données des questions *)
 8 	reponses :        array [1..NBQ] of boolean; (* bases de données des réponses *)
 9 	nb_questions :    integer; (* le nombre de questions à poser *)
10 	numero_question : integer; (* l'indice d'une question dans la BdD *)
11 	i :               integer; (* variable de boucle *)
12 	reponse :         char; (* entrée clavier *)
13 	r :               boolean; (* l'interprétation booléenne de l'entrée au clavier; *)
14         rep_valide :      boolean; (* réponse entrée valide *)
15 	score :           integer; (* le score de joueur *)
16 
17 begin
18 
19 	(* remplissage de la base de données des questions *)
20 	questions[1] := 'La réponse est 42';
21 	questions[2] := 'faux et (vrai et (faux ou vrai))';
22 	questions[3] := 'L''algorithmique impérative c''est cool';
23 	questions[4] := 'si six scies scient six cyprès six-cent scies scient six-cent cyprès';
24 
25 	(* remplissage de la base de données des réponses *)
26 	reponses[1] := true;
27 	reponses[2] := false;
28 	reponses[3] := true;
29 	reponses[4] := true;
30 
31 	(* demande et gestion du nombre de questions *)
32 	Writeln('Donner le nombre de questions voulues pour ce quiz :');
33 	readln(nb_questions);
34 	if nb_questions <= 0 then nb_questions := random(NBQ)+1;
35 
36 	(* initialisations *)
37 	score := 0;
38 
39 	for i:=nb_questions downto 1 do begin
40 
41 		(* Information du joueur : nombre de questions restantes et score *)
42 		Writeln('Il reste ',i, ' questions | SCORE : ', score);
43 
44 		(* on choisit une question au hasard dans le BdD et on l'affiche *)
45 		numero_question := 1+random(NBQ);
46 		writeln(questions[numero_question]);
47 
48 		(* on lit la réponse et on essaie de la comprendre *)
49 		(* si on ne la comprend pas, on passe à la question suivante. Tant pis pour le score *)
50 		readln(reponse);
51 		rep_valide := true;
52 		case reponse of
53 			'o' : r := true;
54 			'O' : r := true;
55 			'v' : r := true;
56 			'V' : r := true;
57 			'n' : r := false;
58 			'N' : r := false;
59 			'f' : r := false;
60 			'F' : r := false;
61 			else rep_valide := false;
62 		end;
63 
64 		if rep_valide then begin
65 		(* on a la réponse du joueur, gestion du score et de l'affichage en fonction de la réponse BdD *)
66 			if r = reponses[numero_question] then begin 
67 				score := score+1;
68 				writeln('Bonne réponse \o/');
69 				end
70 			else begin
71 				writeln('Mauvaise réponse :(');
72 			end;
73 		else begin
74 			writeln('je n''ai pas compris la réponse : entrer o(ui), v(rai), f(aux) ou n(on)');
75 		end;
76 	end;
77 
78 	(* informations finales *)
79 	Writeln('Score final : ', score)
80 end.

Solutions d'un polynômes[modifier | modifier le wikicode]

Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problématique[modifier | modifier le wikicode]

On souhaite réaliser un programme qui donne les solutions d'un polynôme dont les coefficients sont donnés par l'utilisateur. On peut aborder le problème selon des difficultés croissantes :

  1. Résoudre dans ℝ les polynômes du premier degré
  2. Résoudre dans ℝ les polynômes du second degré
  3. Résoudre dans ℂ les polynômes du second degré

Écarts entre les éléments d'un tableau[modifier | modifier le wikicode]

Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problématique[modifier | modifier le wikicode]

Donner un algorithme qui, étant donné un tableau d'entiers, trouve le plus petit écart entre deux éléments.

Exemples :

  • [1|10|4|6] : 6-4 = 2
  • [1|10] : 10-1 = 9
  • [5|5] : 5-5 = 0

Donner un algorithme qui, étant donné un tableau d'entiers, trouve le plus grand écart entre deux éléments.

Solution[modifier | modifier le wikicode]

Une implémentation testable en Pascal[modifier | modifier le wikicode]

 1 program ecarts;
 2 
 3 const
 4 	DEB = 0;
 5 	FIN = 10;
 6 
 7 type
 8 	T_tabint = array [DEB..FIN] of integer;
 9 
10 procedure afficher(var t : T_tabint);
11 (* procédure qui affiche le tableau passé en paramètre *)
12 (* sur une ligne et sous la forme [a|b|c|d...|l|m] *)
13 
14 var
15 	i : integer; (* variable de boucle *)
16 begin
17 	write('[');
18 	for i := DEB to FIN-1 do write(t[i],'|');
19 	write (t[FIN],']');
20 end;
21 
22 procedure remplir(var t : T_tabint);
23 (* procédure qui remplit le tableau passé en paramètre *)
24 (* avec des nombres aléatoires pris entre 0 et 99 *)
25 
26 var
27 	i : integer; (* variable de boucle *)
28 begin
29 	for i := DEB to FIN do t[i] := random(99);
30 end;
31 
32 procedure RechercheEcartMin(t : T_tabint);
33 var
34 	i,j : integer; (* variables de boucle *)
35 	ind1,ind2 : integer; (* indices *)
36 	ecart_min_trouve : integer;
37 	
38 begin
39 	ecart_min_trouve := MAXINT;
40 	for i := DEB to FIN-2 do begin
41 		for j:= i+1 to FIN do begin
42 			if (abs(t[i]-t[j]) <= ecart_min_trouve) then begin
43 				ecart_min_trouve := abs(t[i]-t[j]);
44 				ind1 := i;
45 				ind2 := j;
46 			end;			
47 		end;
48 	end;
49 	writeln('écart minimal trouvé : ',t[ind1],' - ',t[ind2],' = ',ecart_min_trouve)
50 end;
51 
52 procedure RechercheEcartMax(t : T_tabint);
53 var
54 	i : integer; (* variable de boucle *)
55 	min,max : integer; (* indices du plus petit élément et du plus grand élément *)
56 
57 begin
58 	min := DEB;
59 	max := DEB;
60 	for i:= DEB to FIN do begin
61 		if t[i] < t[min] then min := i;
62 		if t[i] > t[max] then max := i;
63 	end;
64 	writeln('écart maximal trouvé : ',t[max],' - ',t[min],' = ',t[max]-t[min])
65 end;
66 
67 var
68 	tab : T_tabint;
69 
70 begin
71 	remplir(tab);
72 	afficher(tab);
73 	writeln(' <- tableau donné');
74 	RechercheEcartMin(tab);
75 	RechercheEcartMax(tab);	
76 end.

Exemple de résultat produit par le programme :

[54|58|70|83|59|84] <- tableau donné
écart minimal trouvé : 83 - 84 = 1
écart maximal trouvé : 84 - 54 = 30