当前位置:网站首页>Problème de hanota récursif / récursif (Hanoi)

Problème de hanota récursif / récursif (Hanoi)

2021-10-14 04:06:02 Au nord d'ether

【Questions posées】

HanoiLa tour estnDisques de différentes tailles et trois colonnes en boisa,b,cComposition.Au début,Voilà.nLes disques sont enveloppés de grands à petits dansaColonne,Comme le montre la figure. 

Voici la description de l'image

DemandeaColonnenLes disques sont déplacés verscColonne: 
  (1)Un seul disque peut être déplacé à la fois; 
  (2)Les disques ne peuvent être stockés que sur trois colonnes; 
  (3)Pendant le déplacement,Il n'est pas permis de presser de grandes plaques sur de petites plaques. 
Demande - lui denUne assiette deaColonne déplacée verscColonne,Nombre total de disques à déplacer? 

【Réponses aux questions】

Solution:Mise en placeHnPournUne assiette deaColonne déplacée verscNombre de fois que la colonne doit être déplacée.

    Apparemment.,Quandn=1Heure,Il suffit de mettrea L'assiette sur la colonne se déplace directement verscLa colonne serait,Donc...:H1=1.

    Quandn=2Heure,D'abord.aLa petite assiette au - dessus de la colonne se déplace versbSur la colonne,Et ensuite retirer la grande assiette deaColonne déplacée verscColonne,Enfin,Oui.bLa petite assiette sur la colonne se déplace verscColonne,Un total de3Un tour,Donc...:H2=3.

    Et ainsi de suite.,QuandaSur la colonnen(n>=2)Quand il y a une assiette,Toujours commencer parcLa colonne est au - dessus den-1Les assiettes se déplacent versbColonne,Et mettreaLa plaque la plus basse de la colonne se déplace verscColonne,Avec l'aide deaLa poignée.bSur la colonnen-1Les assiettes se déplacent verscColonne,Mouvement totalH(n-1)+1+H(n-1)Un tour. 

    ∴Hn=2H(n-1)+1,Conditions limites:H1=1

【 Réalisation récursive 】

#include<stdio.h>
int ct=1;//Enregistrer le nombre d'étapes, Sortie par étapes 
void move(int n,char from,char to)
{
    
    printf("No %2d Pas:Mettre %d Une assiette.: %c >>>>>>> %c\n",ct++,n,from,to);
}
int hanoi(int n)// Étapes de sortie :
{
    
    int cnt = 2,ans = 1;
    if(n == 1)
        return 1;
    else
        return 2* hanoi(n-1) +1;
}
void hanoi_tower(int n,char x,char y, char z) // Étapes de sortie 
{
    
    if(n==1)
        move(1,x,z);
    else{
    
        hanoi_tower(n-1,x,z,y);
        move(n,x,z);
        hanoi_tower(n-1,y,x,z);
    }
}
int main()
{
    
    int n;// Nombre d'assiettes 
    printf(" Entrez le nombre d'assiettes :\n");
    scanf("%d",&n);
    char x = 'A',y = 'B',z = 'C';
    int t = hanoi(n);
    printf("C'est tout.%2dPas.\n",t);
    hanoi_tower(n,x,y,z);
    return 0;
}

【Mise en œuvre récursive】

#include<stdio.h>
void move(int n, char x, char y, char z)//Oui.n Disques de x Avec l'aide de y La colonne se déplace vers zSur le poteau
{
    
     if(n == 1)
     	printf(" Numéro du disque  %d :De %c Déplacer vers %c\n",n,x,z);
     else
     {
    
         move(n-1,x,y,z);
         printf(" Numéro du disque  %d:De %c Déplacer vers %c\n",n,x,z);
         move(n-1,y,x,z);
      }
 }
int main()
{
    
    int n;//n Représente le nombre de disques 
    /*A,B,C Trois colonnes représentant chacune */
    char ch1 = 'A';
    char ch2 = 'B';
    char ch3 = 'C';
 
     printf(" Veuillez saisir le nombre de disques :");
     scanf("%d",&n);
     move(n,ch1,ch2,ch3);
     return 0;
}

版权声明
本文为[Au nord d'ether]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/10/20211013212046330u.html

随机推荐