NYISTハノータ(一)(三)問題及びハノータの経路実現

まず、ハノタとは何ですか?インドでは、世界の中心であるベナレス(インド北部)の聖廟に、黄銅板に宝石の針が3本差し込まれているという古い伝説がある.ヒンドゥー教の主神梵天が世界を創造した時、その中の1本の針に下から上まで大きな64枚の金片を着ていた.これがいわゆるハノータだ.昼も夜も、僧侶が次の法則に従ってこれらの金片を移動しています.一度に1枚だけ移動し、どの針においても、小片は大きな上になければなりません.僧侶たちは、すべての金片が梵天が着た針から別の針に移ると、世界は霹靂の中で消滅し、梵塔、廟宇、衆生も一緒に終わると予言した.
1、ハノータの経路コード実現:
ハノータのパスがどのように移動したのか分からない場合は、次のコードを実行してシミュレーションできます.

#include
void hanoi(int n,char A,char B,char C)
{
        if(n==1)
       {
          printf("%c---->%c
",A,C);
       }
       else
       {
          hanoi(n-1,A,C,B);
          printf("%c---->%c
",A,C);
          hanoi(n-1,B,A,C);
       }
}
int main()
{
       int n;
       scanf ("%d",&n);  
       hanoi(n,'A','B','C');
       return 0;
}

、ハノータ(一)
ハノータの最小ステップ数:
この問題は繰返しの問題に属し,n個の円盤に必要なステップ数f(n)の繰返し式:f(n)=2*f(n−1)+1,.f(n)の値を小さいものから大きいものに列挙すると、1、2、7、15、31、63、127、255......f(n)=2^n-1という簡単な表現があります.この推論は数学的帰納法で証明できるが,ここでは証明しない.
コードは次のとおりです.

 
#include
int b_mod(int a,int n,int m)
{
   if(n==0)  return 1;
   int x=b_mod(a,n/2,m);
   long long ans=(long long)x*x%m;
   if(n%2==1)
      ans=ans*a%m;
   return (int)ans;
}
int main()
{
        int cas,n,answer;
        scanf("%d",&cas);
        while(cas--)
        {
                 scanf("%d",&n);
                 answer=b_mod(2,n,1000000);
                 answer-=1;
                 printf("%d
",answer);
        }
return 0;
}
        

2、ハノータ(三)
スタック容器を用いて、問題の判断条件はすでに与えられた.
1、ある針にはもう金片がないが、指令は依然としてそこから他の針に移動することを要求している.
2、大きな金片を小さな金片に移した.
コードは次のとおりです.

#include
#include
#include
using namespace std;
int main()
{       int cas,floor,step,from,to,flag;
        scanf("%d",&cas);
        while(cas--)
        {  flag=1;
           stacka[4];
           while(!a[1].empty())
             a[1].pop();
           while(!a[2].empty())
             a[2].pop();
           while(!a[3].empty())
              a[3].pop();
              scanf("%d%d",&floor,&step);
           int i,j;
           for(i=floor;i>=1;i--)
               a[1].push(i);
           while(step--)
           {
               scanf("%d%d",&from,&to);
               if(a[from].empty()||(!a[to].empty()&&a[from].top()>a[to].top()))
                    {
                            flag=0;
                            break;
                    }
                else
                {
                        a[to].push(a[from].top());
                        a[from].pop();
                }
           }
           if(flag)
              printf("legal
");
           else
              printf("illegal
");
        }
        return 0;
}