程序员2007年3月刊上的一道算法题

       晚上无聊的时候把以前的<程序员>杂志拿出来see see,于是就看到了这个算法题.这文章之前也看过,但当时稍微想了一下就溜过去了.今天看的时候突然产生了一些疑问,于是动手写了几行代码测试了下,结果发现文章中的说法并不完全対.

      哦,讲了这么久,忘了说这个题在杂志的第65页的第二题.

     注意: 原文并没有给出最优策略 的定义,我这儿根据原文的意思考虑的是这样一种策略:

                  给出一种策略,使得在最坏的情况下,测试的次数最少

      下面是我写的代码:(动态规划算法,时间复杂度O(N^2))

java 代码

/**
 原题: 有一个100层高的大厦,你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界层面。
 算法(递归):
     记为n层楼时最少要测试的次数为f(n),则:
     1. f(1) =0;
     2. 考虑n+1时,若第一个棋子从第k层扔下,此时分两种情况
         a. 碎了. 则临界值不大于k,由于只剩一颗棋,只能从第1层开始往上测试,最多需再测试k-1次(此种情形共测试了k次)
         b. 没碎. 则临界值在k之上,此时还剩2颗棋,可归结到f(n+1-k)的情形(此种情况共测试了1+f(n+1-k)次)
       f(n+1) = min{ max{k,1+f(n+1-k)}: 1<=k<=n+1}
 @author Eastsun
 @version 1.0 2007/5/5
*/
import
 java.util.*;
public
 
class
 Best{
    
private
 
static
 Map map =
new
 HashMap();
    
//求n层楼时最少用的次数
    
public
 
static
 
int
 min(
int
 n){
        
if
(n<
0
) 
throw
 
new
 IllegalArgumentException();
        
if
(n<=
1
) 
return
 
0
;              
//n<=1时,为了方便起见,这里记min(0) =0
        Integer s =map.get(n);
        
if
(s!=
null
) 
return
 s;
        
int
 min =n;                     
//一个上界(这是i取n次的情形): n
        
for
(
int
 i=
1
;i
            
int
 t1 =
1
 + min(n-i);       
//没碎,递归求解
            
int
 t2 =t1>i?t1:i;          
//两种情况的最坏情形
            
if
(min>t2) min =t2;
        }
        map.put(n,min);
        
return
 min;
    }
    
private
 
static
 List list =
new
 LinkedList();  
//用于保存求解路径
    
/**
      打印出测试路径
    */
    
public
 
static
 
void
 solve(
int
 n){
        
if
(n<
0
) 
throw
 
new
 IllegalArgumentException();
        
if
(n<=
1
){
            ListIterator iter =list.listIterator();
            
if
(!iter.hasNext()) 
return
;
            System.out.print(iter.next());
            
while
(iter.hasNext()) System.out.print(
" -> "
+iter.next());
            System.out.println();
            
return
;
        }
        
int
 min =min(n);
        
for
(
int
 i=
1
;i<=n;i++){
            
int
 t1 =
1
+min(n-i);
            
int
 t2 =i>t1?i:t1;
            
if
(t2==min){
                list.add(i);
                solve(n-i);
                list.remove(list.size()-
1
);
            }
        }
    }
    
public
 
static
 
void
 main(String[] args){
        System.out.println(
"Min :"
+min(
100
));   
//注意:有很多组结果
        solve(
100
);
    }
}

运行程序可以看出,对于n=100的情形,存在很多种最优策略,第一次测试选择的楼层可以是从8到14的任意一层.

 

ps:贴上去的代码有点走样,请下载附件

评论

35 楼 longrm 2007-06-14  

caocao 写道

要是面试题，面试官嘿嘿冷笑到，玻璃围棋子3-4楼砸下来就已经挂了，这是常识，所以两次就够了。那就郁闷了 

哈哈，这个答案最好的啦，任何事情还是得联系实际滴，其实用数学方法可以很快的算出来啊，编个程序的时间够偶踢一场足球啦

34 楼 huangpengxiao 2007-05-21  

多来点算法帖 这方面需要恶补

33 楼 xxxcccvvv 2007-05-20  

coolwangyu 写道

我觉得这个是一个典型的概率计算。

我觉得也是

32 楼 caocao 2007-05-13  

Eastsun 写道

楼上牛,3楼怎么一次测出来?洗耳恭听~

是啊，同问，俺一向就是不懂装懂，哈哈

31 楼 blu3leaf 2007-05-12  

嗯嗯~~楼主的思想简单的来说就是一颗找大范围，剩下一颗找精确的楼层
找大范围的可以一次走10层，20层，然后从最后一次不碎的地方开始用剩下的那颗遍历。

30 楼 Eastsun 2007-05-11  

楼上牛,3楼怎么一次测出来?洗耳恭听~

29 楼 ahau205109 2007-05-11  

算法明显错误:
   按你那么算: 3楼高的 也要测试2次?
   最多 1次就够了吧       


不懂不要装懂

28 楼 eboge 2007-05-11  

开始没有仔细看楼主的说明， 只是感觉说的有点麻烦， 好像复杂化了， 原来是我没有注意到，楼主是得出很多的不同策略来实现最优解。这样是很好， 不过如果只是想解决问题， 直接求k!=n中的最接近的k值好像很方便，不用那么麻烦咯， ^_^

27 楼 Eastsun 2007-05-11  

.........
楼上没看我写的代码把?
代码打印出来的是最优策略,最优解(最小测试次数)只有一个,但达到这个解的策略不止一个.

26 楼 eboge 2007-05-11  

我说的就是既然14！已经是最优的解了， 楼主怎么会来那么多的最优解？对于每一层楼来说概率都是相同的啊

25 楼 caocao 2007-05-11  

要是面试题，面试官嘿嘿冷笑到，玻璃围棋子3-4楼砸下来就已经挂了，这是常识，所以两次就够了。那就郁闷了 

24 楼 Eastsun 2007-05-11  

皑皑...
楼上大概没用过JDK1.5了.

23 楼 johnderlin 2007-05-11  

map.get, 不是要object 做para 吗？怎么给了个int?

还有， if(s!=null) return s; 这个方法不是要求返回int?

22 楼 a_nuo 2007-05-10  

先拿来研究一下

21 楼 jesse 2007-05-09  

error

20 楼 bonny 2007-05-09  

14!等于14+13.。。。+1
每次步长+1是为了抵消上一次投掷浪费的那一次
是为了求得答案的稳定性

100%n+n-2在步长一致的情况下，答案是18-10的区间
利用步长可以把答案稳定在14附近

明白了么？

19 楼 eboge 2007-05-09  

我看了一段时间， 发现这个问题可以这样说： 因为对于每一层楼来说，是临界点的几率都一样，所以，开始选择的k，应该尽量保证k+(k-1)+…+1=n，这样不管临界点在哪里，最多次数就是k。
而对于n=100时， k约等于14。和楼主的答案不谋而合，但是楼主答案的后半部的意图我不是很了解。

18 楼 hexstar 2007-05-09  

刚好在手边就有这一期.
文章中好像并没有写这是一个算法,仅仅是一种推理.
就是其中的14!=105>100 这个不太明白是什么意思.
哪位大侠解释一下?

17 楼 Eastsun 2007-05-09  

bonny 写道

我那个公式的确有错误
应该是100%n+n-2

不过得到的答案是从10到18，不够稳定（考虑到平均是14）

原因是每个区间的大小都一样，我把它们的步长设为1

这样
我第一次从14楼丢（步长为13），第2次从27楼丢（步长为12）。。。。。
答案就稳定在14了

确认一下,这儿是 100%n+n-2,还是100/n+n-2?
|100%n|+n-1取最小值的n与100%n+n-2取最小值时的n有不同么?

另外,当n=9(9层楼的时候),按你的公式应该是几次?

16 楼 dovecat 2007-05-09  

哦!反正就是玩到那个棋子碎了为止是吧?