HDOJ 2064 汉诺塔III

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=2064

感觉这题算不错吧。
(在ambition大牛的指点下才发现哪错了,orz)
考虑了几点。

一个是找规律,另外一个就是大数的处理。

大家看看这个图。

怎么找规律。

假设f[n]表示把n层从1移到3的次数,则f[n] = f[n-1]*3+2

考虑为何,因为f[n-1]表示把n-1层从1移到3的次数,这时在底部再添一层时,首先1~n-1层要从1移到3,这就是f[n-1]次了,然后最后一层n从1移到2,为1次,1~n层肯定还得从3移到1(这样最后一层n才能在第3环的最后),这又是f[n-1]次了,最后第n层由2移到3,为1次,1~n-1层由1再到3是f[n-1]次。所以总共就是f[n] = f[n-1]*3+2次

另外,网上好多人写了这个代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 注意这是错误的版本
#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
	int n;
	while(scanf("%d", &n) != EOF)
	{
		printf("%I64d\n", __int64(pow(3.0, n)) -1);
	}
	return 0;
}

大家测试就会发现在n=34和n=35时会和标准答案有出入,这是因为pow和double型都会精度丢失。
他们应该是很早做的。杭电的数据肯定很弱,发现BUG后改过来了。

正确的方法,用数组保存即可,注意用64为整型__int64保存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 // Tanky Woo
// HDOJ 2064
 
 
#include <iostream>
#include <cmath>
using namespace std;
 
__int64 num[36];
int main()
{
	int n;
	num[0] = 1;
	num[1] = 2;
	for(int i=2; i<36; ++i)
		num[i] = num[i-1]*3+2;
	while(scanf("%d", &n) != EOF)
		printf("%I64d\n", num[n]);
	return 0;
}

当然,你测试就会发现只当n=34和35时会有标准有出入,所以你也可以这么写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Tanky Woo
#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
	int n;
	while(scanf("%d", &n) != EOF)
	{
		if(n == 34)
			printf("16677181699666568\n");
		else if(n == 35)
			printf("50031545098999706\n");
		else
			printf("%I64d\n", __int64(pow(3.0, n)) -__int64(1));
	}
	return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 2064 汉诺塔III》有6个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注