NOIP2007普及組 hanoi雙塔問題

【問題描述】

給定A、B、C三根足夠長的細柱，在A柱上放有2n箇中間有孔的圓盤，共有n個不同的尺

寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤足不加區分的(下圖爲n=3的情形)。現要將

這些圓盤移到C柱上，在移動過程中可放在B柱上暫存。要求：

(1)每次只能移動一個圓盤；

(2)A、B、C三根細柱上的圓盤都要保持上小下大的順序；

任務：設An爲2n個圓盤完成上述任務所需的最少移動次數，對於輸入的n，輸出An。

【輸入】

輸入文件hanoi.in爲一個正整數n，表示在A柱上放有2n個圓盤。

【輸出】

輸出文件hanoi.out僅一行，包含一個正整數，爲完成上述任務所需的最少移動次數An。

【輸入輸出樣例1】

hanoi.in

1

hanoi.out

2

【輸入輸出樣例2】

hanoi.in

2

hanoi.out

6

【限制】

對於50％的數據，1<=n<=25

對於100％的數據，l<=n<=200

【提示】

設法建立An與An-1的遞推關係式。

【分析】

設F(x)表示移動2x個圓盤的最小步數。

很容易推出F(x)=2*X^2-2

或者這樣寫：F(x)=F(x-1)*2 最後的F(n)再減2即可，這樣寫可以把高精度乘法換成高精度加法。

【滿分代碼】

//hanoi雙塔問題
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
using namespace std;

char result[1000]; 
void Highj(char a[],char b[]) 
{ 
    int x[1000],y[1000]; 
    int i,l,la,lb; 
    char temp[1000]; 
    for (i=0;i<999;i++){x[i]=0;y[i]=0;} //初始化 
    la=strlen(a); 
    lb=strlen(b); 
     
    //把char型數組 按正倒序  變成整型數組 
    if (la<=lb) 
    { 
        for (i=la-1;i>=0;i--) 
            y[i]=a[la-1-i]-'0'; 
        for (i=lb-1;i>=0;i--) 
            x[i]=b[lb-1-i]-'0'; 
        l=la; 
    } 
    else  
    { 
        for (i=la-1;i>=0;i--) 
            x[i]=a[la-1-i]-'0'; 
        for (i=lb-1;i>=0;i--) 
            y[i]=b[lb-1-i]-'0';     
        l=lb;         
    } 
     
    //執行加法運算 
    for (i=0;i<l;i++) 
    { 
        x[i]=x[i]+y[i]; 
        if (x[i]>=10)  
        { 
            x[i]-=10; 
            x[i+1]+=1; 
        } 
    } 
     
    //再把整型數組按照倒序轉換成char型數組 
    for (i=999;i>=0;i--) 
        temp[999-i]=x[i]+'0'; 
     
    //從不是0的一位開始輸出結果 
    for (i=0;i<=999;i++) 
    { 
        if (temp[i]>'0') 
        { 
            for(int j=i;j<=999;j++) 
                result[j-i]=temp[j]; 
            return; 
        } 
    } 
    //如果沒有一位大於0 
    result[0]='0'; 
    return; 
}  

int main()
{
 freopen("hanoi.in","r",stdin);
 freopen("hanoi.out","w",stdout);
 long long num=1;
 int n;
 cin>>n;
 if (n<90)
 {
  for (int i=1;i<=n;i++)
   num=num*2;
  num=num*2-2;
  cout<<num<<endl;
  return 0;
 }
 if (n>=90)
 {
  char two[1];
  two[0]='2';
  memset(result,'\0',sizeof(result));
  result[0]='1';
  for (int i=1;i<=n+1;i++) 
  {
   Highj(result,result);
  }
  int len=strlen(result);
  if (result[len-1]-'0'>=2)
   result[len-1]=result[len-1]-2;
  else 
  {
   result[len-1]=result[len-1]-2+10;
   result[len-1]=result[len-2]-2;
  }
  cout<<result<<endl;
 }
 return 0;
}

---