*Chapitre 1 - Bataille navale, taxes, fractions

Bataille navale :

Taxes :

Taux quelconque :

Fraction :

Second degré :

Poste :

*Chapitre 2 - Température, calendrier, recherche de mot

Température, d’abord l’algorithme en pseudo-code :

puis le programme en Scheme :

Calendrier :

Logarithme :

Oui ?

Second degré :

*Chapitre 3 - Newton, factorielle, répertoire, polynôme

Mesure principale :

Racine de 2 par la méthode de Newton :

Factorielle :

Répertoire :

Calcul formel :

Initiales :

*Chapitre 4 - Horaire, comptage, division, aléa, pseudonyme, répertoire

Horaire :

Horaire encore :

Nombre de a :

Division décimale :

Réinitialisation :

Globale :

Générateur de nombres pseudo-aléatoires :

Un pseudonyme convenable :

et en Scheme :

Portée :

Répertoire avec des procédures :

Échange (là les méthodes normales de Scheme avec des procédures butent sur le passage des arguments par valeur ; il faut soit, comme ici, définir une forme spéciale avec define-syntax, soit comme nous le verrons plus loin « envelopper » les valeurs à échanger dans un vecteur) :

Par valeur :

Échange en enveloppant les valeurs dans un vecteur d’une case :

*Chapitre 5 - Horaire, puissance, quotient

Encore les horaires :

Élever à la puissance :

Le quotient :

*Chapitre 11 - Répertoire

Nous nous proposons d’informatiser la consultation de notre répertoire téléphonique, enregistré comme suit dans un fichier :

Voici la procédure principale. Elle commence par compter les lignes du fichier pour en déduire la taille du répertoire : en effet, les vecteurs qui vont nous servir à enregistrer les noms et les numéros de téléphone sont de type rigide, comme exposé ci-dessus, il nous faut donc connaître leur taille à l’avance pour les créer, il ne sera plus possible de les agrandir ensuite. Puis elle invoque la procédure de construction de l’annuaire proprement dit dans deux vecteurs noms et tels, et enfin appelle la procédure qui demande à l’utilisateur d’entrer le nom recherché, soumis à la procédure de recherche dans l’annuaire :

Voici la procédure pour compter les lignes du fichier qui contient le répertoire (ici nous avons deux lignes par entrée dans le répertoire) :

Il nous faut d’abord charger le fichier en mémoire sous une forme propre à faciliter sa consultation ultérieure :

La procédure de recherche d’un nom dans le répertoire :

Pour faire de ces programmes un module compilable il faut ajouter le fichier suivant :

On compilera et on exécutera ce programme par les commandes suivantes :

*Chapitre 12 - Des lettres au hasard

Des lettres au hasard :

*Chapitre 18 - Additioneur binaire

Additioneur binaire :

*Chapitre 20 - Recherche dans un répertoire

**Recherche dichotomique dans un répertoire

Nous nous proposons d’informatiser la consultation de notre répertoire téléphonique, enregistré comme ci-dessus (pour le chapitre 11) dans un fichier.

Le répertoire, avec recherche dichotomique :

Voici la procédure pour compter les lignes du fichier qui contient le répertoire (ici nous avons deux lignes par entrée dans le répertoire) :

Il nous faut d’abord charger le fichier en mémoire sous une forme propre à faciliter sa consultation ultérieure :

Voici un programme de recherche dichotomique, plus efficace que celui du chapitre 11 :

Pour faire de ces programmes un module compilable il faut ajouter le fichier suivant :

On compilera et on exécutera ce programme par les commandes suivantes :

**Recherche dans un répertoire, avec adressage associatif

Le programme de répertoire, compilé, avec adressage associatif (hash table). Voici le fichier principal repertoire-hash-main.scm :

Voici la procédure pour compter les lignes du fichier qui contient le répertoire (ici nous avons deux lignes par entrée dans le répertoire) :

La fonction d’association :

**Zéro d’une fonction

*Chapitre 21 - Tri par sélection et par fusion

**Tri par sélection

Le principe du tri par sélection est le suivant : on met en bonne position l’élément numéro 1, c’est-à-dire le plus petit. Puis en met en bonne position l’élément suivant. Et ainsi de suite jusqu’au dernier. Par exemple, si l’on part d’un tableau dans l’état suivant :

On commence par rechercher, parmi les 12 valeurs, quel est le plus petit élément, et où il se trouve. On l’identifie en quatrième position (c’est le nombre 3), et on l’échange alors avec le premier élément (le nombre 45). Le tableau devient ainsi :

On recommence à chercher le plus petit élément, mais cette fois, seulement à partir du deuxième (puisque le premier est maintenant correct, on n’y touche plus). On le trouve en troisième position (c’est le nombre 12). On échange donc le deuxième avec le troisième :

On recommence à chercher le plus petit élément à partir du troisième (puisque les deux premiers sont maintenant bien placés), et on le place correctement, en l’échangeant, ce qui donnera in fine :

Nous aurons besoin d’un algorithme pour déterminer l’indice du plus petit élément d’un vecteur, à partir d’un certain indice i :

Voici l’algorithme de tri par sélection :

Soit en Scheme :

**Tri par fusion

Tri par fusion, récursif :