Skip to content

L2inf – Solutions du contrôle du S2

28 mai 2014
Source : Wikipédia

Jeu des Tours de Hanoi en bois avec 8 disques.

Et voici l’énoncé et la solution du contrôle d’Algorithmique de la 2e année de Licence Informatique:

Voici la version complète du programme « Tours de Hanoi » :

/* Tours de Hanoi */
#include <stdio.h>
#include <stdlib.h>


int * construire_tour(int nbdisques)
{
    int * tour = malloc((nbdisques+1) * sizeof(int));
    /* alloue dynamiquement un 'tableau' de nbdisques+1 entiers :
     * chacune des 3 tours est implémentée comme une pile
     * faite d'un tableau dont la 1re case contient le 
     * nombre d'éléments présents dans la pile
     * (le + petit disque = 1, le + grand = nbdisques)
     */

    if (tour==NULL){ // toujours prévoir l'échec d'allocation
        perror("problème d'allocation mémoire"); //affiche l'erreur
        exit(EXIT_FAILURE);
    }    
    void vider(int tour[]);
    vider(tour);
    return tour;
}

void detruire_tour(int *tour)
{
    free(tour); //libère la mémoire occupée par la pile
}

/* nbre_disques - donne le nombre de disques présents dans une tour
 * param : tour : pile de la tour
 *         disque : Nbre de disques
 */
int nbre_disques(int tour[])
{
    return tour[0];
}

/* est_vide - retourne 1 si la tour est vide, 0 sinon */
int est_vide(int tour[])
{
    return tour[0]==0;
}

/* vider - vide la pile donnée en paramètre */
void vider(int tour[])
{
    tour[0]=0;
}

/* empiler - empile un disque sur une tour
 * param : tour : pile de la tour
 *         disque : N° du disque
 */
void empiler(int tour[], int disque)
{
    tour[++tour[0]]=disque;
}

/* sommet - donne le N° du disque en haut de la pile
 * param : tour : pile de la tour
 * retourne : N° du disque au sommet ou 0 si la tour est vide
 */  
int sommet(int tour[])
{
    return tour[tour[0]];
}

/* depiler - dépile un disque de la tour
 * param : tour : pile de la tour
 * retourne : N° du disque dépilé ou 0 si tour vide
 */         
int depiler(int tour[])
{
    if (tour[0])  // ne décrémenter que si pile non vide
        return tour[tour[0]--];
    else
        return 0;
}

/* deplacer - déplace un disque d'une tour à une autre
 * param : source, dest : tours source et destination
 * retourne : N° du disque déplacé ou 0 si pas de disque
 */
int deplacer(int source[], int dest[])
{
    if (est_vide(source))
        return 0;
    int disque=depiler(source);
    empiler(dest,disque);
    return disque;
}

/* affiche le contenu des trois tours
 * (horizontalement, en mode texte et 
 *  sans couleurs pour l'instant :-)
 */
void afficher(int **tour)
{
    for (int i=0;i<3;++i) {
        for (int j=0;j<nbre_disques(tour[i]);++j) 
            printf("%d",tour[i][j+1]);
        puts("");
    }
}

int main(void)
{
    puts("Jeu des Tours de Hanoi\n-------------\n");
    int nbdisques;
    printf("Combien de disques ? ");
    scanf("%d",&nbdisques);
    int *tour[3];
    for (int i=0;i<3;++i)
        tour[i]=construire_tour(nbdisques);
    for (int i=nbdisques;i>0;--i)
        empiler(tour[0],i);
    printf("Donnez les étapes pour déplacer les disques");
    puts(" de la tour 1 à la tour 3 :");
    int coup=0;
    do {
        afficher(tour);
        ++coup;
        printf("Déplacement N°%d :\n",coup);
        printf("-> de la tour N°");
        int src;
        scanf("%d",&src);
        src--;
        printf("<- à la tour N°");
        int dest;
        scanf("%d",&dest);
        dest--;
        if (!est_vide(tour[dest]) &&
             sommet(tour[src])>sommet(tour[dest])){
            puts("Interdit de placer un grand disque sur un petit ");
            coup--;
            continue;
        }
        int disque = deplacer(tour[src],tour[dest]);
        if (!disque){
            printf("Erreur: tour N°%d vide !\n",src+1);
            coup--;
        } else
            printf("Disque N°%d : de %d à %d\n",disque,src+1,dest+1);    
    } while(nbre_disques(tour[2])<nbdisques);
    
    printf("BRAVO ! Jeu terminé en %d coups.\n",coup);
/*
    for (int i=0;i<3;++i)
        detruire_tour(tour[i]);
*/
    int **p=tour;
    while (p-tour<3){
        detruire_tour(*p) ;
        ++p ;
    }
    /* ne pas oublier de faire le ménage et débarrasser la mémoire */
    
}
Source: Wikipédia

Solution pour 4 disques

Publicités

From → 2e année, C

Laisser un commentaire

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :