nyoj 88 漢諾塔

        漢諾塔就是層疊遞歸調用的典型例子，一直是利用 A—>B  A-->C  B-->C 這樣的單個步驟。

       具體來說，當盤數大于一時，不違背原則下（過程中總是大在下小的在上），A先借助B再放到C上。總是把盤數看成兩個來解決問題。

       比如說，當盤數為二時，顧名思義，這個很簡單隻要三下即可完成。這個時候，可以這樣想，如果是三個，就相當于二個完成，還有一個待完成，（注意要有把問題簡化為兩個盤的思想,這樣是遞歸思想的思想實作），那麼把完成的看成一個，剩下待完成的看成一個（帶完成的還可以把最近要完成的看成一個，剩下的先别管），這樣問題就回到了二個盤數時的第一步完成狀态，然後C上的（二個看成一個）在借助B放到A上，這樣第三個就可以從B放到C上，接下來又是二個了（這個是真正的二個），看基本步驟完成。當盤數是N時，也是利用這種思想，一步一步簡化，遞歸完成。

       接下來談一下N個盤要幾次完成：

        當完成n個時設用M(n)次，那麼，如上說的算法當完成n個（也就是n+1個時了）還有一個，這時需要把在C上的看成一個，借助B移動到A上（這時最後一個已到B上），當然要做M（n）次搬動了，完成後，B上的最後一個（（n+1）個）搬動到C上。這時，問題又回到了n次開始，當然需要M(n)次了。這麼一來就是M（n）*2次，加上最後一個的兩次，總共是M(n)*2+2=M(n+1)次，好了現在是純數學問題了，結果是M（n）=2^n-1.

方法一：

#include<iostream>

using namespace std;

long long g(int a,int b)

{

    int x,y;

    if(b==0)

    return 1;

    if(b==1)

    return 2;

    x=g(a,b/2);

    y=(long long)x*x%1000000;

    if(b%2==1)

    y=y*2%1000000;

    return (int)y;

}

int main()

{

   int n,t;

   long long m;

   cin>>n;

   while(n--)

   {

       cin>>m;

       t=g(2,m);

       cout<<t-1<<endl;

   }

   return 0;

}

方法二：

1. #include<stdio.h> 
2. int main() 
3. { 
4.     int i,j,k,l,m,n,s; 
5.     scanf("%d",&s); 
6.     while(s--) 
7.     { 
8.         int c=1; 
9.         scanf("%d",&n); 
10.         if(n>12500)//對輸入的資料進行處理 
11.         { 
12.             if(n%100000<6) 
13.                 n=n%10+100000; 
14.             else n%=100000; 
15.         } 
16.         while(n--) 
17.         { 
18.             c=2*c; 
19.             c%=1000000; 
20.         } 
21.         printf("%d\n",c-1); 
22.     }return 0; 
23. } 

方法三：

1. #include<stdio.h> 
2. int a[100006]; 
3. int main() 
4. { 
5.     int s,m,i; 
6.     a[1]=1; 
7.     for(i=2;i<100006;i++) 
8.     { 
9.         a[i]=(2*a[i-1]+1)%1000000; 
10.     } 
11.     scanf("%d",&s); 
12.     while(s--) 
13.     { 
14.         scanf("%d",&m); 
15.         if(m>12500) 
16.         { 
17.             if(m%100000<6) 
18.                 m=100000+m%10; 
19.             else 
20.                 m%=100000; 
21.         } 
22.         printf("%d\n",a[m]); 
23.     } 
24.     return 0; 
25. }