题目地址：
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; } |
我刚刚用你的代码试了，通不过，很可惜了
我刚又去提交了，AC。
不知道是你用的是第一个错误的代码？还是你的编译器选择错了？
@人生如梦
[s:33]
好文章
[s:4]