本文出自 http://blog.csdn.net/shuangde800
题目点击打开链接
题意:
汉诺塔游戏请看
百度百科
正常的汉诺塔游戏是只有3个柱子,并且如果有n个圆盘,至少需要2^n-1步才能达到目标。
但是在这题中,有4根柱子,并且按照下面规则来玩:
1. 先把圆盘顶部前k个盘子全部搬到第四根柱子上,
2. 然后把剩下的n-k个盘子在前3根柱子中按照经典的规则搬到某个柱子上(假设是a柱),
3. 最后再把那k个盘子搬到目标a柱上。
问按照这样的规则,最少需要几步?
思路:
我们先设g[n]表示按照经典的游戏规则(3根柱子),n个盘子最少需要g[n]步,可以知道g[n] = 2^n-1
然后我们再设f[n]表示按照4根柱子的规则来,n个盘子最少需要f[n]步。
那么按照上面步骤可以推出:
1.把圆盘顶部前k个盘子全部搬到第四根柱子 上 ==》 需要f[k]步
2.把剩下的n-k个盘子在前3根柱子中按照经典的规则搬到某个柱子上 (假设是a柱) ==》需要g[n-k]步
3.最后再把那k个盘子搬到目标a柱上 ==》需要f[k]步
所以,f[n] = f[k]*2+g[n-k]
因为f[n]要最小,且k不确定,所以枚举一下k,取最小值即可:
f[n] = min{ f[k]*2+g[n-k] , 1<=k<=n }
由于n过大,所以要用到大数。
由于本题的n为10000,上面的算法复杂度为O(n^2),所以不能用上面方法。
那么就打表找规律一下,并不难找
观察下面前20个,不难找出规律:
f[1] = 1
----------------
f[2] = 3, f[2] = f[1] + 2^1
f[3] = 5, f[3] = f[2] + 2^1
共 2 个 2^1
----------------
f[4] = 9, f[4] = f[3] + 2^2
f[5] = 13, f[5] = f[4] + 2^2
f[6] = 17, f[6] = f[5] + 2^2
共 3 个 2^2
----------------
f[7] = 25, f[7] = f[6] + 2^3
f[8] = 33, f[8] = f[7] + 2^3
f[9] = 41, f[9] = f[8] + 2^3
f[10] = 49, f[10] = f[9] + 2^3
共 4 个 2^3
----------------
f[11] = 65, f[11] = f[10] + 2^4
f[12] = 81, f[12] = f[11] + 2^4
f[13] = 97, f[13] = f[12] + 2^4
f[14] = 113, f[14] = f[13] + 2^4
f[15] = 129, f[15] = f[14] + 2^4
共 5 个 2^4
----------------
f[16] = 161, f[16] = f[15] + 2^5
f[17] = 193, f[17] = f[16] + 2^5
f[18] = 225, f[18] = f[17] + 2^5
f[19] = 257, f[19] = f[18] + 2^5
f[20] = 289, f[20] = f[19] + 2^5
共 6 个 2^5
----------------
代码:
/**===========================================
* This is a solution for ACM/ICPC problem.
*
* @author: shuangde
* @blog: http://blog.csdn.net/shuangde800
* @email: zengshuangde@gmail.com
*============================================*/
import java.math.*;
import java.util.Scanner;
public class Main {
public static void main(String args[]){
BigInteger f[] = new BigInteger[10010];
f[0] = BigInteger.valueOf(0);
f[1] = BigInteger.valueOf(1);
int i = 2;
int k=1;
while(i <= 10000){
BigInteger add = BigInteger.valueOf(1).shiftLeft(k);
for(int j=0; j<k+1 && i<=10000; ++j){
f[i] = f[i-1].add(add);
++i;
}
++k;
}
Scanner cin = new Scanner(System.in);
while(cin.hasNext()){
int n = cin.nextInt();
System.out.println(f[n]);
}
}
}
分享到:
相关推荐
Taoist-priest Taoist-priest by nqmy 这些是贫道闲暇时间的做的一些感兴趣的小玩意,以及收集的一些js小插件,其实我更喜欢玩原生的。 1、 这是一个利用canvas,来进行图片切割并上传的工具,对IE的支持不太优秀...
马修·普里斯特·萨缪尔
高级java工程师笔试题 詹姆斯·普里斯特 加利福尼亚州洛杉矶 概括 具有 20 年构建 Web 应用程序经验的高级前端/全栈 Web 开发人员。 技能 开发技能 完整的响应式网页设计 网络可访问性和 ...Bootstrap、jQuery、
PJBlog3 Priest模板
这个地方是一片混乱,几乎无法导航,但是他们会发现一个非常有趣的发现:古老的Dragon Priest面具,可以让他们随意在过去和现在之间切换。 目前,那里的废墟除了几处腐烂的法尔默(Falmer)之外几乎是一片荒芜,但...
sprite_character_priest_effect_divineagent.NPK:sprite_character_priest_effect_divineagent.NPK
用Python编写的高级增量构建系统,引入了对自动依赖性和配方发现的支持。 它支持单线程和多线程构建。 它需要Python v2.6和pybfc,并且本机支持所有POSIX系统。
sprite_character_priest_effect_atbrionac.NPK:sprite_character_priest_effect_atbrionac.NPK
结果表明:Priest-Zhang算法估算的直径期望是截短值的线性递增函数,修正算法估算的直径期望是截短值的水平线性函数;截短值较小时,2种算法接近,采用前者已能够获得较高精度,纠正截短偏差意义不大;截短值较大时...
Native American Warrior Female 01, Native American Warrior Male 01, Native American Warrior Male 02, Native American Warrior Male 03, Priest Male 01, Salesman Male 01, Soldier Male 01, Thug Male 01, ...
sprite_character_priest_effect_avengerawakening_dash.NPK:sprite_character_priest_effect_avengerawakening_dash.NPK
斯特拉皮牧师 在mongo db上运行牧师CMS % yarn develop
LocalExchangeUK是Calvin Priest最初为UK LETS团体量身定制的原始Local Exchange源代码的分支。 该软件使用PHP / MySQL编写,为LETS(本地交易系统)组提供了一个交互式网站。 ************************************...
尼康优化标准下载。尼康优化标准曲线,相当于游戏刷mod,可用不同机型的曲线,也就是可得不同机型的色彩效果
指数计划的游戏属性,级别和类别计划的游戏镇 Welcome to Text Adventures You are now on the town of Nee'Peh Here you can: go Tavern - small talk, some Ale and Potions go Aluriel's Priest - here you can ...
尼康常用曲线,人像风景原片 直出神器。
-Priest:您可以选择另一个玩家并查看他们的卡。 有两张这样的牌,而且它们的价值为 2。 -男爵:你可以选择另一个玩家,然后你再买牌。 谁的价值最低,谁就出局。 在平局的情况下。 两名球员都留下了。 有两张
此仓库还使用James Priest的格式( )格式化此日志,请按照以下说明进行操作如果您要使用此格式,请阅读他的自述文件。待办事项{本轮|| 2021年3月8日至6月21日} 使自述文件外观更好,信息量更大。 对整个日志实施...
游戏角色设计课题 练习课题:游戏角色设计课题。 角色 名称name 攻击力iattacklevel(100) 生命值ilife(100) 防御% ...4魔法师(Priest) 召唤界的女巫 20 100 15% 5圣骑士(paladin ) 用斧头的王者 26 100 25%
实用指南的实际内容由Lili David,James Priest和Bernhard Bockelbrink在此资料库之外开发。 如果您想为《实用指南》的改进做出贡献,我们已经建立了[专用页面]( ,其中解释了如何通知我们有关错别字和更正,如何...