2007-05-05

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

关键字: 算法

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

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

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

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

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

java 代码
  1. /**  
  2.  原题: 有一个100层高的大厦,你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界层面。  
  3.  算法(递归):  
  4.      记为n层楼时最少要测试的次数为f(n),则:  
  5.      1. f(1) =0;  
  6.      2. 考虑n+1时,若第一个棋子从第k层扔下,此时分两种情况  
  7.          a. 碎了. 则临界值不大于k,由于只剩一颗棋,只能从第1层开始往上测试,最多需再测试k-1次(此种情形共测试了k次)  
  8.          b. 没碎. 则临界值在k之上,此时还剩2颗棋,可归结到f(n+1-k)的情形(此种情况共测试了1+f(n+1-k)次)  
  9.        f(n+1) = min{ max{k,1+f(n+1-k)}: 1<=k<=n+1}  
  10.  @author Eastsun  
  11.  @version 1.0 2007/5/5  
  12. */  
  13. import java.util.*;   
  14. public class Best{   
  15.     private static Map map =new HashMap();   
  16.     //求n层楼时最少用的次数   
  17.     public static int min(int n){   
  18.         if(n<0) throw new IllegalArgumentException();   
  19.         if(n<=1) return 0;              //n<=1时,为了方便起见,这里记min(0) =0   
  20.         Integer s =map.get(n);   
  21.         if(s!=null) return s;   
  22.         int min =n;                     //一个上界(这是i取n次的情形): n   
  23.         for(int i=1;i
  24.             int t1 =1 + min(n-i);       //没碎,递归求解   
  25.             int t2 =t1>i?t1:i;          //两种情况的最坏情形   
  26.             if(min>t2) min =t2;   
  27.         }   
  28.         map.put(n,min);   
  29.         return min;   
  30.     }   
  31.     private static List list =new LinkedList();  //用于保存求解路径   
  32.     /**  
  33.       打印出测试路径  
  34.     */  
  35.     public static void solve(int n){   
  36.         if(n<0) throw new IllegalArgumentException();   
  37.         if(n<=1){   
  38.             ListIterator iter =list.listIterator();   
  39.             if(!iter.hasNext()) return;   
  40.             System.out.print(iter.next());   
  41.             while(iter.hasNext()) System.out.print(" -> "+iter.next());   
  42.             System.out.println();   
  43.             return;   
  44.         }   
  45.         int min =min(n);   
  46.         for(int i=1;i<=n;i++){   
  47.             int t1 =1+min(n-i);   
  48.             int t2 =i>t1?i:t1;   
  49.             if(t2==min){   
  50.                 list.add(i);   
  51.                 solve(n-i);   
  52.                 list.remove(list.size()-1);   
  53.             }   
  54.         }   
  55.     }   
  56.     public static void main(String[] args){   
  57.         System.out.println("Min :"+min(100));   //注意:有很多组结果   
  58.         solve(100);   
  59.     }   
  60. }  

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

 

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

  • Best.rar (1.2 KB)
  • 描述: 本文中的源代码
  • 下载次数: 73
评论
longrm 2007-06-14
caocao 写道
要是面试题，面试官嘿嘿冷笑到，玻璃围棋子3-4楼砸下来就已经挂了，这是常识，所以两次就够了。那就郁闷了

哈哈，这个答案最好的啦，任何事情还是得联系实际滴，其实用数学方法可以很快的算出来啊，编个程序的时间够偶踢一场足球啦
huangpengxiao 2007-05-21
多来点算法帖 这方面需要恶补
xxxcccvvv 2007-05-20
coolwangyu 写道
我觉得这个是一个典型的概率计算。


我觉得也是
caocao 2007-05-13
Eastsun 写道
楼上牛,3楼怎么一次测出来?洗耳恭听~


是啊，同问，俺一向就是不懂装懂，哈哈
blu3leaf 2007-05-12
嗯嗯~~楼主的思想简单的来说就是一颗找大范围，剩下一颗找精确的楼层
找大范围的可以一次走10层，20层，然后从最后一次不碎的地方开始用剩下的那颗遍历。
Eastsun 2007-05-11
楼上牛,3楼怎么一次测出来?洗耳恭听~
ahau205109 2007-05-11
算法明显错误:
按你那么算: 3楼高的 也要测试2次?
最多 1次就够了吧


不懂不要装懂
eboge 2007-05-11
开始没有仔细看楼主的说明， 只是感觉说的有点麻烦， 好像复杂化了， 原来是我没有注意到，楼主是得出很多的不同策略来实现最优解。这样是很好， 不过如果只是想解决问题， 直接求k!=n中的最接近的k值好像很方便，不用那么麻烦咯， ^_^
Eastsun 2007-05-11
.........
楼上没看我写的代码把?
代码打印出来的是最优策略,最优解(最小测试次数)只有一个,但达到这个解的策略不止一个.
eboge 2007-05-11
我说的就是既然14！已经是最优的解了， 楼主怎么会来那么多的最优解？对于每一层楼来说概率都是相同的啊
caocao 2007-05-11
要是面试题，面试官嘿嘿冷笑到，玻璃围棋子3-4楼砸下来就已经挂了，这是常识，所以两次就够了。那就郁闷了
Eastsun 2007-05-11
皑皑...
楼上大概没用过JDK1.5了.
johnderlin 2007-05-11
map.get, 不是要object 做para 吗？怎么给了个int?

还有， if(s!=null) return s; 这个方法不是要求返回int?
bonny 2007-05-09
14!等于14+13.。。。+1
每次步长+1是为了抵消上一次投掷浪费的那一次
是为了求得答案的稳定性

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

明白了么？
eboge 2007-05-09
我看了一段时间， 发现这个问题可以这样说： 因为对于每一层楼来说，是临界点的几率都一样，所以，开始选择的k，应该尽量保证k+(k-1)+…+1=n，这样不管临界点在哪里，最多次数就是k。
而对于n=100时， k约等于14。和楼主的答案不谋而合，但是楼主答案的后半部的意图我不是很了解。
hexstar 2007-05-09
刚好在手边就有这一期.
文章中好像并没有写这是一个算法,仅仅是一种推理.
就是其中的14!=105>100 这个不太明白是什么意思.
哪位大侠解释一下?
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层楼的时候),按你的公式应该是几次?
dovecat 2007-05-09
哦!反正就是玩到那个棋子碎了为止是吧?
Eastsun 2007-05-09
过儿oO 写道
Eastsun 写道
呵呵,按楼上说的"，第一把放50层，碎了向下走一半"
那么如果再碎了呢?怎么确定临界层?

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


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


如果是14层碎了,那么只能用剩下的一颗棋子从第一层逐次往上测,最多共测14次
bonny 2007-05-09
我那个公式的确有错误
应该是100%n+n-2

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

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

这样
我第一次从14楼丢（步长为13），第2次从27楼丢（步长为12）。。。。。
答案就稳定在14了
Eastsun
搜索本博客
我的相册
1b680e5a-efae-3ec3-8ccd-970a4a72a056-thumb
6.5beta.PNG
共 61 张
最近加入圈子
存档
最新评论