# 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 :

## 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 :
* À 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.

## Solution finale
# 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 :
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
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

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

Voici un exemple d'exécution :

# Rechercher un élément dans un tableau
## Problèmatique

Supposons que nous avons déclaré un tableau tab d'entiers comme suit :
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é.
L'algorithme suivant fonctionne mais à le défaut de continuer à parcourir le tableau même quand l'élément a été trouvé.

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

#### Traduction en Pascal

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

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

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

# 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 :
* 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é

# É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

Exemple de résultat produit par le programme :