当前位置:阳光沙滩 >C/C++ > 查看文章
阿里云优惠码

好久没写,生疏了好多

在每天有意义却不知道其意义的生活放在一边吧

今天就聊聊汉诺塔问题吧

现在有三根相邻的柱子,标号为A,B,C,A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,现在把所有盘子一个一个移动到柱子

B上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方,请问至少需要多少次移动?

C++实现的代码如下:

#include <iostream>//汉诺塔问题
using namespace std;

void move(char c1, char c2)
{
	cout << c1 << "-->" << c2 << endl;//从c1一点到c2
}

void hanoi(int n, int A, int B, int C)
{
	if (n == 1)//n==1,只剩下最后一个,从A移动到B
		move(A, C);
	else
	{
		hanoi(n - 1, A, C, B);//将n-1个盘子从A借助C移动到B
		move(A, C);//将A剩下的一个盘子移动到C
		hanoi(n - 1, B, A, C);//将n-1个盘子从B借助A移动到C
	}
}

int main()
{
	int m;
	cout << "Enter the number of diskes:" << endl;
	cin >> m;
	cout << "the steps to moving " << m << "diskes:" << endl;
	hanoi(m, 'A', 'B', 'C');
	system("pause");
	return 0;
}

1

得益于算法的实现,要不用需要递归的方法。假设有m片,移动次数是f(m).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难

证明f(m)=2^m-1。当m=64时,假如每秒钟一次移动一次,一个平年365天有31536000 秒,闰年366天有31622400秒,平均每年31

556952秒,计算一下:18446744073709551615秒,这表明移完这些金片需要5845.54亿年以上。

本文链接:http://blog.sunofbeaches.com/archives/191 转载请注明出处.
如果喜欢:点此订阅本站
7K
相关文章
为您推荐
各种观点

报歉!评论已关闭.