Evo. G Tech Team Forum
Welcome to Evo. G Tech Team Forum. We have moved to a new website : www.evogtechteam.com

Thanks you.

by Evo. G Tech Team Management.

用c++编写hanoi汉诺塔

View previous topic View next topic Go down

用c++编写hanoi汉诺塔

Post by too wei on July 7th 2015, 20:02

汉诺塔(港台:河內塔)是根据一个传说形成的數學问题
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
-每次只能移动一个圆盘
-大的盘不能叠在小的盘上面


最早發明這個問題的人是法國數學家愛德華·盧卡斯。
傳說印度某間寺院有三根柱子,上串64个金盤。寺院裡的僧侶依照一個古老的預言,以上述規則移動這些盤子;預言說當這些盤子移動完毕,世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。但不知道是盧卡斯自創的這個傳說,還是他受他人啟發。
若傳說屬實,僧侶們需要264 − 1步才能完成這個任務;若他們每秒可完成一個盤子的移動,就需要5849億年才能完成。整個宇宙現在也不過137億年。
這個傳說有若干變體:寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜,其中一說是位于越南的河內,所以被命名為「河內塔」。另外亦有「金盤是創世時所造」、「僧侶們每天移動一盤」之類的背景設定。
佛教中確實有「浮屠」(塔)這種建築;有些浮屠亦遵守上述規則而建。「河內塔」一名可能是由中南半島在殖民時期傳入歐洲的
如取N=64,最少需移动264-1次。即如果一秒钟能移动一块圆盘,仍将需5849.42亿年。目前按照宇宙大爆炸理论的推测,宇宙的年龄仅为137亿年。




基本概念是使用递归。首先,把A顶部的N-1块盘移动到B塔,再把A剩下的大盘移到C,最后把B的N-1块盘移到C。
每次移动多于一块盘时,则再次使用上述算法来移动。
Code:
void hannoi (const int & n,const char & a,const char & b,const char & c)
{
    if (n == 1)
    {
        cout << "Move disk " << n << " from " << a << " to " << c << endl;

    }
    else
    {
        hannoi (n-1, a, c, b);
        cout << "Move disk " << n << " from " << a << " to " << c << endl;
        hannoi (n-1, b, a, c);
    }
}

int main()
{
    int n = 0;
    cout<<"Enter the n : ";
    cin >> n;
    hannoi (n, 'A', 'B', 'C');
    return 0;
}

too wei
Sponsor
Sponsor

Posts : 31
Points : 17731
Reputation : 0
Join date : 2015-04-21
Age : 19
Location : Johor

View user profile

Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum