程序员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:贴上去的代码有点走样,请下载附件

评论

15 楼 Eastsun 2007-05-09  

过儿oO 写道

Eastsun 写道

呵呵,按楼上说的"，第一把放50层，碎了向下走一半"
那么如果再碎了呢?怎么确定临界层?

注意:这里只有两颗棋子,用完就没有了.而不是无限颗.

啊，是这样
但是我没明白那个是根据什么算地，我感觉每一层都有碎的可能，那么答案应该是放在第几层？
你那个算的是14层？还是什么
没明白啊
如果是14层，14层碎了咋办，往下放还是任意一层都有碎的可能啊

如果是14层碎了,那么只能用剩下的一颗棋子从第一层逐次往上测,最多共测14次

14 楼 bonny 2007-05-09  

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

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

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

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

13 楼 qqsan 2007-05-09  

其实还是个折半查找吧，只不过需要根据有几个棋子来确定可以折几次，剩最后一个棋子时，开始遍历。

12 楼 过儿oO 2007-05-09  

还没回答我啊。。

11 楼 Eastsun 2007-05-08  

to:上上楼:
嗯,题目没有给出"最优策略"的定义,如果从数学期望来考虑,也是一种思路.不过这样的话解决方法就比较简单了.

不过我的算法不是从数学期望角度来考虑的.
根据原文的描述,我考虑的"最优策略"是这样的:
    给出一种策略,使得在最坏的情况下,测试的次数最少

to:上楼
     呵呵,看法不一致.

10 楼 bonny 2007-05-08  

我自己看了你的思路 是你推理就有问题。

9 楼 coolwangyu 2007-05-08  

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

8 楼 Eastsun 2007-05-08  

bonny 写道

没有仔细看你的算法。我喜欢看数学公式。

我列出的公式是
|100%n|+n-1求最小值时n

嘿嘿,我看到网上有也有人用你这个公式来解决这个问题.
不过,就个人看来,这个公式是错的.

7 楼 过儿oO 2007-05-08  

Eastsun 写道

呵呵,按楼上说的"，第一把放50层，碎了向下走一半"
那么如果再碎了呢?怎么确定临界层?

注意:这里只有两颗棋子,用完就没有了.而不是无限颗.

啊，是这样
但是我没明白那个是根据什么算地，我感觉每一层都有碎的可能，那么答案应该是放在第几层？
你那个算的是14层？还是什么
没明白啊
如果是14层，14层碎了咋办，往下放还是任意一层都有碎的可能啊

6 楼 bonny 2007-05-08  

没有仔细看你的算法。我喜欢看数学公式。

我列出的公式是
|100%n|+n-1求最小值时n

5 楼 Eastsun 2007-05-08  

呵呵,按楼上说的"，第一把放50层，碎了向下走一半"
那么如果再碎了呢?怎么确定临界层?

注意:这里只有两颗棋子,用完就没有了.而不是无限颗.

4 楼 过儿oO 2007-05-08  

看半天没明白为啥要一层一层走
为啥不直接一半一半走
2个条件啊，第一把放50层，碎了向下走一半，没碎向上走一半
用不了多少次就会固定了啊
还是我没理解这题呢？

3 楼 Eastsun 2007-05-08  

那个,就是说:
第一次从14楼扔下去测试,如果没破,归结到86(100-14)楼的情形
->下一次从上面86层的第13层开始测试(也就是100层中的第27层(13+14)),如果没破,归结到73层的情形->...->...

如果第一次(14层)破了,这是只能从用剩下的一颗棋子从第一层一直往上测试,这时总共最多会测试14次
其余类推.

可能讲的不是很清楚,直接看我代码上的算法说明应该更容易理解.

2 楼 jasongreen 2007-05-08  

引用

14 -> 13 -> 12 -> 11 -> 10 -> 7 -> 7 -> 7 -> 4 -> 5 -> 4 -> 2 -> 2 -> 1
14 -> 13 -> 12 -> 11 -> 10 -> 7 -> 7 -> 7 -> 4 -> 5 -> 4 -> 3 -> 1 -> 1
14 -> 13 -> 12 -> 11 -> 10 -> 7 -> 7 -> 7 -> 4 -> 5 -> 4 -> 3 -> 2
14 -> 13 -> 12 -> 11 -> 10 -> 7 -> 7 -> 7 -> 5 -> 3 -> 4 -> 3 -> 2 -> 1
14 -> 13 -> 12 -> 11 -> 10 -> 7 -> 7 -> 7 -> 5 -> 4 -> 3 -> 3 -> 2 -> 1
14 -> 13 -> 12 -> 11 -> 10 -> 7 -> 7 -> 7 -> 5 -> 4 -> 4 -> 2 -> 2 -> 1
14 -> 13 -> 12 -> 11 -> 10 -> 7 -> 7 -> 7 -> 5 -> 4 -> 4 -> 3 -> 1 -> 1
14 -> 13 -> 12 -> 11 -> 10 -> 7 -> 7 -> 7 -> 5 -> 4 -> 4 -> 3 -> 2
14 -> 13 -> 12 -> 11 -> 10 -> 7 -> 7 -> 7 -> 5 -> 5 -> 2 -> 3 -> 2 -> 1
14 -> 13 -> 12 -> 11 -> 10 -> 7 -> 7 -> 7 -> 5 -> 5 -> 3 -> 2 -> 2 -> 1
14 -> 13 -> 12 -> 11 -> 10 -> 7 -> 7 -> 7 -> 5 -> 5 -> 3 -> 3 -> 1 -> 1
...

这个结果有点看不懂阿

1 楼 Eastsun 2007-05-06  

这个递归算法也可以很方便的推广到m个棋子,n层楼的情况去.

   另外,个人认为<程序员>上的这篇文章写的不太好.文中用所谓的"数学事实"来解释问题的答案,但我认为这个问题作为一个算法题来讲,应该从递归,动态规划这些常用的算法角度来入手,更有意义一些.
   当然,这个题确实可以从数学推理上来给出简洁的结果(可惜文中给的推理既不完整也不严谨).但其推理并不是那么明显的.还是用代码来解决更爽快一些.