Algorithmique impérative/Problèmes

Inverser deux variables

Problèmatique

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

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

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

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

Problématique

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

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

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

Gérer le choix de l'utilisateur

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

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

1. À 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

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

Problématique

É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

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

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

En fait notre fonction calcule pour n : $\sum _{i=0}^{n}i$. L'étude des séries nous apprend que

$\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}$.

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

Problématique

É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

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

Solution

Algorithme pgcd

Fonction euclide( u : entier
                   v : entier ) : entier
Variables
  r : entier (* le reste d'une division entière *)
Début
  Tant que v <> 0 faire
    r := u mod v
    u := v
    v := r
  FTQ
  retourner u
Fin

Variables
  u,v : entier (* les deux entiers donnés par l'utilisateur *)
Début
  Écrire("Donner les deux nombres : ")
  Lire(u,v)
  (* Début question subsidiaire *)
  si u=0 et v=0 alors Écrire("Le PGCD n'existe pas")
  sinon début
    si u < 0 alors u := -u
    si v < 0 alors v := -v
    (* Fin Question subsidiaire *)
    Écrire(euclide(u,v))
  fin
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

Problématique

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

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"

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

program tris;

const
	DEB = 0;
	FIN = 5;

type
	T_tabint = array [DEB..FIN] of integer;

procedure permuter(var i : integer; var j : integer);
(* à la fin, i vaut le j donné et j vaut le i donné *)
var
	tmp : integer; (* un tampon pour stocker l'élément que va remplacer l'élément minimum pendant l'inversion *)
begin
	tmp := i;
	i := j;
	j := tmp
end;

procedure afficher(var t : T_tabint);
(* procédure qui affiche le tableau passé en paramètre *)
(* sur une ligne et sous la forme [a|b|c|d...|l|m] *)

var
	i : integer; (* variable de boucle *)
begin
	write('[');
	for i := DEB to FIN-1 do write(t[i],'|');
	write (t[FIN],']');
end;

procedure remplir(var t : T_tabint);
(* procédure qui remplit le tableau passé en paramètre *)
(* avec des nombres aléatoires pris entre 0 et 99 *)

var
	i : integer; (* variable de boucle *)
begin
	for i := DEB to FIN do t[i] := random(99);
end;


procedure TriSelection(var t : T_tabint);
var
	i, j	: integer;	(* variables de boucle *)
	min		: integer;	(* indice du plus petit élément parmi ceux qui reste à trier *)
	
begin
   for i:=DEB to FIN-1 do begin
      min := i;
      for j:=i+1 to FIN do
         if (t[j] < t[min]) then min:=j;

      if (i <> min) then permuter(t[i],t[min]);
   end; 
end;

procedure TriBulle(var t: T_tabint);
var
	i, j	: integer;	(* variables de boucle *)
 
begin
  for i:=DEB to FIN-1 do begin
    j := i+1;
    for j := FIN-1 downto i do
    	if t[j+1]<t[j] then permuter(t[j],t[j+1]);
  end;
end;

var
	tab : T_tabint;

begin

	(* pour chaque tri on recrée un tableau aléatoire, on l'affiche *)
	(* puis on le trie et on l'affiche à nouveau *)

	(* Tri sélection *)
	writeln('TRI SELECTION');
	remplir(tab);
	afficher(tab);
	writeln(' <- tableau donné');
	TriSelection(tab);
	afficher(tab);
	writeln(' <- tableau trié');
		
	(* Tri bulle *)
	writeln('TRI BULLE');
	remplir(tab);
	afficher(tab);
	writeln(' <- tableau donné');
	TriBulle(tab);
	afficher(tab);
	writeln(' <- tableau trié');
	
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

Problèmatique

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

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

Solutions moyennes

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

Algorithme recherche
Variables
  q : entier (* l'entier recherché *)
  i : entier (* ce sera l'indice de parcours *)
Début
  Afficher("Donner l'entier à trouver")
  Lire(q)
  i ← MIN
  tantque tab[i] != q
    i ← i+1
  ftq
  Afficher("L'indice où se trouve ", q ," est ", i)
Fin

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

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

Solution attendue

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

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

Traduction en Pascal

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

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

Jeu du Tas de billes

Problématique

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.

Solution

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

Implémentation en Pascal

program billes;

var
	nb_billes :				integer;	(* le nombre de billes dans le tas *)
	coup :					integer;	(* nombre de billes à retirer lors d'un tour*)
	tour :					boolean;	(* vrai si c'est le tour du joueur 1 *)
	joueur1, joueur2 :		string;		(* noms des joueurs *)
	i :						integer;	(* variable de boucle *)

begin
	(* Affichage des règles *)
	writeln('Règles du jeu :');
	writeln('* On commence avec un tas de billes, le jeu se joue à deux.');
	writeln('* Les joueurs jouent l''un après l''autre.');
	writeln('* Chaque joueur, à son tour, peut retirer une, deux, ou trois billes du tas.');
	writeln('* Le joueur qui prend la dernière bille a perdu.');
	
	(* Recueil des informations nécessaires au jeu *)
	writeln('Donner le nom du joueur 1 : ');
	readln(joueur1);
	writeln('Donner le nom du joueur 2 : ');
	readln(joueur2);
	writeln('Donner le nombre de billes : ');
	readln(nb_billes);

	(* gestion du nombre de billes *)
	if (nb_billes <= 0) then begin
		nb_billes := 10+random(20);	(* random(n) renvoie un nombre entre 0 et n *)
		writeln('Un nombre aléatoire est pris : ',nb_billes);
	end;

	(* on démarre à false, ainsi c'est le joueur 1 qui jouera en premier *)
	tour := false;

	repeat
		(* nettoyer l'écran, un appel de clsrc() peut fonctionner également *)
		for i:=1 to 20 do writeln();

		(* on change le joueur à qui est le tour *)
		tour := not(tour);

		(* on indique à qui est le tour *)
		write('C''est au tour de ');
		if (tour) then writeln(joueur1) else writeln(joueur2);

		(* affichage (textuel et graphique) du nombre de billes restant *)
		writeln('Il reste ',nb_billes,' billes. ');
		if (nb_billes <= 30) then for i:= 1 to nb_billes do write('.');
		writeln();

		(* demande au joueur son coup , gestion de la triche *)
		writeln('Combien retirez-vous de billes ?');
		readln(coup);
		while ((coup < 1) or (coup > 3) or (coup > nb_billes)) do begin
			writeln('Tricheur !');
			writeln('* On ne peut retirer qu''entre une et trois billes.');
			writeln('* On ne peut plus de billes qu''il n''y en a.');
			writeln('Combien retirez-vous de billes ?');
			readln(coup)
		end;

		(* on a le coup voulu, on le joue *)
		nb_billes := nb_billes - coup

	until (nb_billes = 0);

	(* c'est le joueur qui a joué en dernier qui est perdant *)
	(* on inverse pour indiquer le gagnant *)
	if (not(tour)) then write(joueur1) else write(joueur2);
	writeln(' gagne !');

end.

Quiz

Problématique

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

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

Implémentation en Pascal

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

program quiz;

const
	NBQ = 4; (* nombre de questions dans la base de données *)

var
	questions :       array [1..NBQ] of string; (* bases de données des questions *)
	reponses :        array [1..NBQ] of boolean; (* bases de données des réponses *)
	nb_questions :    integer; (* le nombre de questions à poser *)
	numero_question : integer; (* l'indice d'une question dans la BdD *)
	i :               integer; (* variable de boucle *)
	reponse :         char; (* entrée clavier *)
	r :               boolean; (* l'interprétation booléenne de l'entrée au clavier; *)
        rep_valide :      boolean; (* réponse entrée valide *)
	score :           integer; (* le score de joueur *)

begin

	(* remplissage de la base de données des questions *)
	questions[1] := 'La réponse est 42';
	questions[2] := 'faux et (vrai et (faux ou vrai))';
	questions[3] := 'L''algorithmique impérative c''est cool';
	questions[4] := 'si six scies scient six cyprès six-cent scies scient six-cent cyprès';

	(* remplissage de la base de données des réponses *)
	reponses[1] := true;
	reponses[2] := false;
	reponses[3] := true;
	reponses[4] := true;

	(* demande et gestion du nombre de questions *)
	Writeln('Donner le nombre de questions voulues pour ce quiz :');
	readln(nb_questions);
	if nb_questions <= 0 then nb_questions := random(NBQ)+1;

	(* initialisations *)
	score := 0;

	for i:=nb_questions downto 1 do begin

		(* Information du joueur : nombre de questions restantes et score *)
		Writeln('Il reste ',i, ' questions | SCORE : ', score);

		(* on choisit une question au hasard dans le BdD et on l'affiche *)
		numero_question := 1+random(NBQ);
		writeln(questions[numero_question]);

		(* on lit la réponse et on essaie de la comprendre *)
		(* si on ne la comprend pas, on passe à la question suivante. Tant pis pour le score *)
		readln(reponse);
		rep_valide := true;
		case reponse of
			'o' : r := true;
			'O' : r := true;
			'v' : r := true;
			'V' : r := true;
			'n' : r := false;
			'N' : r := false;
			'f' : r := false;
			'F' : r := false;
			else rep_valide := false;
		end;

		if rep_valide then begin
		(* on a la réponse du joueur, gestion du score et de l'affichage en fonction de la réponse BdD *)
			if r = reponses[numero_question] then begin 
				score := score+1;
				writeln('Bonne réponse \o/');
				end
			else begin
				writeln('Mauvaise réponse :(');
			end;
		else begin
			writeln('je n''ai pas compris la réponse : entrer o(ui), v(rai), f(aux) ou n(on)');
		end;
	end;

	(* informations finales *)
	Writeln('Score final : ', score)
end.

Solutions d'un polynômes

Problématique

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

Problématique

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

Une implémentation testable en Pascal

program ecarts;

const
	DEB = 0;
	FIN = 10;

type
	T_tabint = array [DEB..FIN] of integer;

procedure afficher(var t : T_tabint);
(* procédure qui affiche le tableau passé en paramètre *)
(* sur une ligne et sous la forme [a|b|c|d...|l|m] *)

var
	i : integer; (* variable de boucle *)
begin
	write('[');
	for i := DEB to FIN-1 do write(t[i],'|');
	write (t[FIN],']');
end;

procedure remplir(var t : T_tabint);
(* procédure qui remplit le tableau passé en paramètre *)
(* avec des nombres aléatoires pris entre 0 et 99 *)

var
	i : integer; (* variable de boucle *)
begin
	for i := DEB to FIN do t[i] := random(99);
end;

procedure RechercheEcartMin(t : T_tabint);
var
	i,j : integer; (* variables de boucle *)
	ind1,ind2 : integer; (* indices *)
	ecart_min_trouve : integer;
	
begin
	ecart_min_trouve := MAXINT;
	for i := DEB to FIN-2 do begin
		for j:= i+1 to FIN do begin
			if (abs(t[i]-t[j]) <= ecart_min_trouve) then begin
				ecart_min_trouve := abs(t[i]-t[j]);
				ind1 := i;
				ind2 := j;
			end;			
		end;
	end;
	writeln('écart minimal trouvé : ',t[ind1],' - ',t[ind2],' = ',ecart_min_trouve)
end;

procedure RechercheEcartMax(t : T_tabint);
var
	i : integer; (* variable de boucle *)
	min,max : integer; (* indices du plus petit élément et du plus grand élément *)

begin
	min := DEB;
	max := DEB;
	for i:= DEB to FIN do begin
		if t[i] < t[min] then min := i;
		if t[i] > t[max] then max := i;
	end;
	writeln('écart maximal trouvé : ',t[max],' - ',t[min],' = ',t[max]-t[min])
end;

var
	tab : T_tabint;

begin
	remplir(tab);
	afficher(tab);
	writeln(' <- tableau donné');
	RechercheEcartMin(tab);
	RechercheEcartMax(tab);	
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