两个超经典超难应用题1、有一幢100楼的大厦,两部手机,让你设计一种算法确切地知道这部手机在第几楼摔下会坏,算法要尽量优

两个超经典超难应用题
1、有一幢100楼的大厦,两部手机,让你设计一种算法确切地知道这部手机在第几楼摔下会坏,算法要尽量优化.
2、有三根棍子,第一根上面套着n个环,最大的一个在底下,其余一个比一个小的依次叠上去,把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面,请问怎么搬?需要搬多少次?要有推导过程.
谢绝复制粘贴流.
sevenoutman那你的具体做法是什么？

真汗,好多复制我曾经在http://zhidao.baidu.com/question/56519153.html这道题里面的答案的,难道作弊的时候稍微把一些个性话的语言都改掉不会吗?难道不能比较一下我用来提问的ID,和我这个ID的差别么?我这么做不是搞恶作剧,实际上是百度逼的,我曾经用这个ID回答过一个高分题,但是答案发出去以后不显示在题目下面,再发的时候系统提示我已经回答过了,这不把人往死里逼么,不得以才重新注册一个ID去回答一下,拿到分后想转到这个ID上,但又不想放过这机会,于是就把记忆中比较经典的题目拿出来玩一下,其实一开始就是个圈套,各位莫怪,如有得罪还请海涵.嘿嘿……
只是没想到抛砖引玉,果然有更高明的答案.
第一题,我现在发现我曾经的那个作答是错的,38楼的“矩阵Metrix”的回答才是最优,不超过14次,比我多考虑了一点就是楼层越高手机越可能摔坏,佩服佩服,如果能写出推理过程就更好了.不过佩服归佩服,分不能给你,嘿嘿……sevenoutman的态度我很欣赏,和我自己很象,但答案有点让人遗憾,过程很详细,但具体做法写的太含糊,没看懂.
第二题,其实是我高中玩文曲星的时候,发现的这个游戏,当时想了整整一个下午,才总结出来的答案,当时真的觉得自己跟神一样,本来我想把自己的发现告诉数学老师的,可怕被人说是炫耀,所以遗憾至今.
其实原理很简单,只有一个环时,我可以一下放到目标棒上,那么增加一个环时,我可以按照移动一个环的方法,将第一个环移动到中转棒上,然后把增加的第二个环放到目标棒上,再按照移动一个环的方法将第一个环放到目标棒上,那么再增加一个环,还是按照这个道理.即,由于n-1个环可以移动,所以n个环的处理方法是将n-1个环移动到中转棒上,再将第n个环移动到目标棒上,再将n-1个环移动到目标棒上.还有一个十分重要的条件就是,增加一个大环的好处是,所以的环都可以放在它的上面,可以视为一个桌子.
同时还有个规律,当环数为偶数时,第一个环必须移动到中转棒上；为奇数时,第一个环必须移动到目标棒上.这个很简单,不证了.
现在来证明移动次数和盘子数量的关系.
令盘子数为n时,移动数为An
则
A1=1 式1
A2=2*A1 + 1 式2
A3=2*A2 + 1 式3
.
.
.
An-1=2*An-2 + 1 式n-1
An=2*An-1 + 1 式n
式1乘以2^(n-1),式2乘以2^(n-2),式3乘以2^(n-3)……式n-1乘以2^[n-(n-1)]
然后将得到的所有式子两边相加,可以消去A1——An-1所有项,最后是一个等比数列,公差为2,这就不罗嗦了,整理出来是An=2^n-1.
可惜没人给出一个让我满意的答案,否则我还真改变主意把跟给他了.我个人比较反感用一个计算机程序做这题,太没技术含量了.
个人比较喜欢第一题,实用度很高.第二题技巧性比较强,启发意义比较好.