Tri par fusion

Comme nous l'avons vu en cours, le tri par fusion (ou interclassement) repose sur la division du problème de tri en 2 sous-problèmes (demi-tableaux à trier), que l'on traite récursivement, puis que l'on fusionne dans un tableau auxiliaire.

L'objectif de cet exercice est de mettre en oeuvre le tri par fusion. Il s'agit donc de trier les entiers passes en argument sur la ligne de connande. Votre programme va stocker ces entiers dans un tableau nomme tab, et utilisera un tableau aux (de meme taille) pour effectuer les interclassements.

Une astuce pour realiser les interclassements est de stocker les deux sous-tableaux a interclasser "dos a dos" dans aux.


Problème des 8 reines

  Le problème consiste à déterminer de combien de façons n reines peuvent être placées sur un échiquier nxn de sorte qu'il n'y ait qu'une reine par ligne, colonne, et diagonale. La question a d'abord été posée pour l'échiquier 8x8 en 1848. Gauss a conjecturé qu'il y avait 72 solutions au problème, mais peu après 92 solutions ont été publiéees, ce qui convainquit Gauss qu'il s'était trompé. La preuve que 92 est la bonne réponse n'a été donnée qu'en 1874 par Glaisher.
7
6
5
4
3
2
1
0
0 1 2 3 4 5 6 7

Ce problème fournit une belle illustration de l'usage de la récursivité pour explorer un espace de configurations. (Il existe des approches plus subtiles pour compter rapidement le nombre de solutions sur un échiquer nxn, ce qui est utile en particulier pour élucider le comportement asymptotique du nombre de solutions lorsque n tend vers l'infini, qui reste à ce jour irrésolu.)

La solution (image) ci-dessus a été prise sur une page canadienne dédiée à ce problème, mais qui ne contient pas beaucoup d'informations récentes.

Le but de l'exercice est l'écriture d'un programme qui calcule le nombre de solutions pour n allant de 1 à 13.

Le principe consiste à maintenir à jour trois tableaux de booléens : un tableau indiquant pour chaque ligne si elle est interdite (déjà prise), un autre pour les diagonales montantes et le dernier pour les diagonales descendantes. Pour la mise au point du programme, il peut être utile d'ajouter un tableau pour stocker la solution en cours de construction. Pour chaque colonne, il indique dans quelle ligne se trouve une reine.

Il n'y a qu'une fonction à écrire en plus de la methode main). Elle prend en argument un entier col correspondant à la nouvelle colonne à visiter, la dimension dim de l'echiquier,  ainsi que les trois tableaux. Elle renvoie le nombre de solutions possibles avec les reines placées telles qu'elles le sont dans les colonnes d'indice 0 à col-1.

L'ensemble du programme avec affichage du nombre de solutions pour chaque valeur de n tient en moins d'une cinquantaine de lignes.