【數論】[NOIP2007]Hanoi雙塔問題

前幾天Z老師給我們把曆年noip普及組的數論題都找了出來 說真的 目前對于高精度還一竅不通的我 有些題真心不會 但是最後看看代碼才發現 我基本上都沒用到高精..

例如這個題 正解确實要用高精 但是我還是沒有..我的做法已經在洛谷OJ釋出了題解

題目

Hanoi雙塔問題【Noip普及組】2007T4 [難度]普及組題目不評級 [标簽]<高精><遞推><遞歸><數論數學> (洛谷搜尋P1096 1s128MB)

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 ②2

輸出樣例:① 2 ②6

說明

【限制】

對于50%的資料，1<=n<=25

對于100%的資料，1<=n<=200 //這麼小 暴力就是了[滑稽

我們可以用一個num[]數組來存儲答案且num[1]代表個位 往後類推

#include<iostream>
using namespace std;
#define SIZE 100001
int num[SIZE];
int n,len=;
//COYG
           

n是我們要輸入的數字 len代表輸出答案的長度 首先要初始化

num[1]=1;

一定要注意 不要把num[1]初始為2 往後看你就會明白

然後就是記錄移動

for(int i=1;i<=n;i++){Record()；}

這裡我們需要弄一個函數record來記錄

void Record()
{
    int carry_bit=;//我們應當考慮到進位的情況 是以建立一個變量記錄進位 下面有用法
    for(int i=;i<=len;i++){
        num[i]=num[i]*;//雙塔
        num[i]+=carry_bit;//如果有前一位進上來的數肯定要加上
        if(num[i]<){
            carry_bit=;//小于10肯定不會進位
        }
        else{//大于10有進位
            carry_bit=num[i]/;//計算進上去的數
            num[i]=num[i]%;//這一位%10儲存 很好了解
            if(i==len){
                len=i+;//之前說過len的意義 如果i已經和目前的len相等可是又進了一位 就必須要增加長度
            }
        }
    }
}
//COYG
           

調用了n次之後 我們好像已經計算出了n個塔移動的次數 但是如果我們此時輸入 3 輸出的答案應該是7 可卻是8

原因是之前我們個位多加了一次 于是

num[1]-=1;

然後再執行一遍record獲得2n的數量

最後倒叙輸出

全代碼如下

#include<iostream>
using namespace std;
#define SIZE 100001
int num[SIZE];
int n,len=;
void Record()
{
    int carry_bit=;
    for(int i=;i<=len;i++){
        num[i]=num[i]*;
        num[i]+=carry_bit;
        if(num[i]<){
            carry_bit=;
        }
        else{
            carry_bit=num[i]/;
            num[i]=num[i]%;
            if(i==len){
                len=i+;
            }
        }
    }
}
int main()
{ 
    cin>>n;
    num[]=;
    for(int i=;i<=n;i++){
        Record();
    }
    for(int i=len;i>=;i--){
        cout<<num[i];
    }
    cout<<endl; 
    num[]-=;
    Record();
    for(int i=len;i>=;i--){
        cout<<num[i];
    }
    cout<<endl;
    return ;
    //COYG
}
           

差不多就這樣 當然普及組的題很簡單 如果是提高組的數論那麼就要…

好好看書學數學！

一起共勉