魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: yang_bigarm

两个鸡蛋和楼房高度问题 [复制链接]

Rank: 3Rank: 3

积分
881
帖子
219
精华
0
UID
68713
性别
保密
发表于 2009-3-25 11:38:39 |显示全部楼层
这不是去年某期程序员杂志的题目么?

使用道具 举报

Rank: 2

积分
274
帖子
164
精华
2
UID
63527
性别
发表于 2009-3-26 17:48:03 |显示全部楼层
这个是我一个同学去EMC参加面试的时候遇到的问题。

楼上 lulijie 的答案是正确的,分析的求和公式也很正确,但是这个问题跟数学归纳法没有什么关系,这个问题的主要实质是决策树的平衡,如果 lulijie 能把决策树也贴出来就很好了。

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-3-26 18:19:20 |显示全部楼层
决策树这个概念我可不懂,我该描述的都描述了,只差 程序的代码( VB6.0)没公布,若大家对 其 感兴趣,我马上可以公布。

使用道具 举报

红魔

All Blue

Rank: 4

积分
1196
帖子
999
精华
2
UID
38845
性别
发表于 2009-3-26 18:21:59 |显示全部楼层
LULIJIE是暴力解題的,不過要用樹的話,要嘗試好些時間才猜得出來

使用道具 举报

红魔

All Blue

Rank: 4

积分
1196
帖子
999
精华
2
UID
38845
性别
发表于 2009-3-26 18:45:41 |显示全部楼层
如果第一次破了,那麼便要由頭試起,最少步>=第一次撞那個數
主要是讓右邊的態樹(第一次不破之後的動作)不要高過左邊

[ 本帖最后由 骰迷 于 2009-3-26 18:47 编辑 ]

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-3-26 18:56:32 |显示全部楼层
也不能说暴力。
应该说用递推方法求解,只不过把比较大小的过程交过了电脑而已。
先从S(1),推导出S(2),
再从S(1)、S(2)推导出S(3),
再从S(1)、S(2)、S(3)推导出S(4),
以此类推,直至推出S(100)。
跟暴力解法那是天壤之别。

使用道具 举报

红魔

All Blue

Rank: 4

积分
1196
帖子
999
精华
2
UID
38845
性别
发表于 2009-3-26 22:47:28 |显示全部楼层
算我電腦知識差罷,本人是不太了解程序碼解題的

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-3-27 00:31:24 |显示全部楼层
我们把n层楼的最佳数列的第一项值,即最先扔鸡蛋的楼层  为 k
观察上述n=1-100  的k值,发现一个明显的规律:
以下把只有一个k值的列举如下,
n:k;
1:1;
2:1;
4:2;
7:3;
11:4;
16:5;
22:6;
29:7;
37:8;
46:9;
56:10;
67:11;
79:12;
92:13;
106:14;     这是我的推测
--------------------------
其他n,如70,从上表查它介于67和79之间,所以它的k值可取11或12。
所以只要记住上述表的值就可。
上述表有个很明显的规律。
第二行的n比第一行的多1,
第三行的n比第二行的多2,
第m行的n比上一行多m-1。
用通项表示  n(m)=1+m(m-1)/2       n(m)表示m行的n值。而k值等于m-1,(第一行除外)
所以不用记忆:只要记住
          n=1,                      k=1
          n=1+m(m-1)/2         k=m-1                          m>1
         介于两者之间的        k可以取两端的值。

解题过程:
    n=100
   因为    1+14*(14-1)/2=92           k=13
              1+15*(15-1)/2=106        k=14
  因为100介于上述两者之间,所以k可取13或14
不妨取14,    100-14=86                    即第一次楼层   14
              1+13*(13-1)/2=79      k=12
              1+14*(14-1)/2=92      k=13
      86介于上述两者之间,所以k可取12或13      
不妨取12,    86-12=74                        即第二次楼层  14+12=26
       。。。。。。。
       。。。。。。。
最后可得到金眼睛得出的数列:
   14、26、37、47、56、64、72、79、85、90、94、97、99、100
    知道了最佳数列,那么最少步数就举手可得。
---------------------------------------------------------
关键是我得出的上述蓝字部分的结论是不是对于所有的n都成立了?  n不仅仅限于100以内。

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-3-27 18:30:05 |显示全部楼层
S(n)的值也有明显的规律
1,
1+2,
1+2+3,1+2+3+3,
1+2+3+3+4,1+2+3+3+4+4,1+2+3+3+4+4+4,
1+2+3+3+4+4+4+5,。。。。。。

若m(m+1)/2 +2 <= n<= (m+1)(m+2)/2 +1,        那么  S(n)=S(n-1)+m+2。         
或者表示成以下递推公式:
      S(n)=S(n-1)+  int( sqr(2n-3.75)-0.5 ) +2              int是取整函数  ,sqr 是开根号。
      S(1)=1

使用道具 举报

Rank: 2

积分
333
帖子
276
精华
1
UID
40058
性别
保密
发表于 2009-3-28 18:20:54 |显示全部楼层
原帖由 东莞的8 于 2009-3-23 15:15 发表
随便试试:先从10楼开始试,每次隔10层,到摔坏的时候再退到未摔坏的10层先开始每次上一层试,这样的话最不幸的情况是要19次。


这个比较有道理,不过我觉得是18次,因为第100层是不用扔的。

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2019-6-19 11:21

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部