Un livre de Wikibooks.

Sections

1 Inverser deux variables
2 Un menu de sélection simple
3 Somme des n premiers entiers
4 PGCD de deux nombres
5 Trier un tableau
- 5.1 Problématique
- 5.2 Solution
  - 5.2.1 Une solution "simple"
    - 5.2.1.1 Une implémentation testable en Pascal
6 Rechercher un élément dans un tableau
7 Jeu du Tas de billes
8 Quiz
- 8.1 Problématique
  - 8.1.1 Données
- 8.2 Solution
  - 8.2.1 Implémentation en Pascal
9 Solutions d'un polynômes
- 9.1 Problèmatique
10 Écarts entre les éléments d'un tableau
- 10.1 Problèmatique
- 10.2 Solution
  - 10.2.1 Une implémentation testable en Pascal

[modifier] Inverser deux variables

[modifier] 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.

[modifier] 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

[modifier] 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'un 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 algorithme 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 que 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.
que peut-être que ce programme doit pouvoir être exécuté simultanément des milliers des fois sur la même machine.
que peut-être que 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...

[modifier] 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).

[modifier] 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.

[modifier] 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.

[modifier] Analyse approfondie

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

[modifier] 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...).

[modifier] 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 :

A priori, on ne sait pas combien de fois l'utilisateur va exécuter une procédure. Cela exclut le POUR.
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.

[modifier] 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 parmis
      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

[modifier] Somme des n premiers entiers

[modifier] Problèmatique

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

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

[modifier] 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).

[modifier] Remarque

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

En fait notre fonction calcule pour n : $\sum_{i=1}^{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...)

[modifier] PGCD de deux nombres

[modifier] 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.

[modifier] Aide

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

[modifier] 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.

[modifier] Trier un tableau

[modifier] 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 ?

[modifier] 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.

[modifier] 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).

[modifier] 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é

[modifier] Rechercher un élément dans un tableau

[modifier] 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.

[modifier] 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...

[modifier] Solutions

[modifier] 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 *)

  resultat : 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 resultat ← i (* si on a trouvé on mémorise l'indice *)

  ftq

  Afficher("L'indice où se trouve ", q ," est ", résultat)

Fin

[modifier] 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

[modifier] 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.

[modifier] Jeu du Tas de billes

[modifier] 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.

[modifier] Première analyse

[modifier] Analyse approfondie

[modifier] Solution

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

[modifier] 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.

[modifier] Quiz

[modifier] 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.

[modifier] 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.

[modifier] Solution

[modifier] 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.

[modifier] Solutions d'un polynômes

[modifier] 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 :

Résoudre dans ℝ les polynômes du premier degré
Résoudre dans ℝ les polynômes du second degré
Résoudre dans ℂ les polynômes du second degré

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

[modifier] 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.

[modifier] Solution

[modifier] 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

Algorithmique impérative/Problèmes

Un livre de Wikibooks.

Sections

[modifier] Inverser deux variables

[modifier] Problèmatique

[modifier] Solutions

[modifier] Remarque

[modifier] Un menu de sélection simple

[modifier] Problèmatique

[modifier] Première analyse

[modifier] Analyse approfondie

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

[modifier] L'utilisateur retrouve le menu

[modifier] Solution finale

[modifier] Somme des n premiers entiers

[modifier] Problèmatique

[modifier] Solution

[modifier] Remarque

[modifier] PGCD de deux nombres

[modifier] Problèmatique

[modifier] Aide

[modifier] Solution

[modifier] Trier un tableau

[modifier] Problématique

[modifier] Solution

[modifier] Une solution "simple"

[modifier] Une implémentation testable en Pascal

[modifier] Rechercher un élément dans un tableau

[modifier] Problèmatique

[modifier] Aide

[modifier] Solutions

[modifier] Solutions moyennes

[modifier] Solution attendue

[modifier] Traduction en Pascal

[modifier] Jeu du Tas de billes

[modifier] Problématique

[modifier] Première analyse

[modifier] Analyse approfondie

[modifier] Solution

[modifier] Implémentation en Pascal

[modifier] Quiz

[modifier] Problématique

[modifier] Données

[modifier] Solution

[modifier] Implémentation en Pascal

[modifier] Solutions d'un polynômes

[modifier] Problèmatique

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

[modifier] Problèmatique

[modifier] Solution

[modifier] Une implémentation testable en Pascal

Affichages

Outils personnels

Rechercher

Bibliothèque

Navigation

Aide

Imprimer / exporter

Boîte à outils