论坛首页 → Java企业应用论坛 →

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

浏览 14208 次
锁定老帖子 主题：程序员2007年3月刊上的一道算法题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • Eastsun
  • 等级: 二钻会员
  • 性别:
  • 文章: 790
  • 积分: 1329
  • 来自: 天津
   发表时间：2007-05-05  

       晚上无聊的时候把以前的<程序员>杂志拿出来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)
  • 描述: 本文中的源代码
  • 下载次数: 97
返回顶楼
         
  • Eastsun
  • 等级: 二钻会员
  • 性别:
  • 文章: 790
  • 积分: 1329
  • 来自: 天津
   发表时间：2007-05-06  
这个递归算法也可以很方便的推广到m个棋子,n层楼的情况去.

   另外,个人认为<程序员>上的这篇文章写的不太好.文中用所谓的"数学事实"来解释问题的答案,但我认为这个问题作为一个算法题来讲,应该从递归,动态规划这些常用的算法角度来入手,更有意义一些.
   当然,这个题确实可以从数学推理上来给出简洁的结果(可惜文中给的推理既不完整也不严谨).但其推理并不是那么明显的.还是用代码来解决更爽快一些.
返回顶楼
          回帖地址
0 请登录后投票
  • jasongreen
  • 等级: 二星会员
  • 性别:
  • 文章: 922
  • 积分: 280
  • 来自: 安徽
   发表时间：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
...


这个结果有点看不懂阿
返回顶楼
          回帖地址
0 请登录后投票
  • Eastsun
  • 等级: 二钻会员
  • 性别:
  • 文章: 790
  • 积分: 1329
  • 来自: 天津
   发表时间：2007-05-08  
那个,就是说:
第一次从14楼扔下去测试,如果没破,归结到86(100-14)楼的情形
->下一次从上面86层的第13层开始测试(也就是100层中的第27层(13+14)),如果没破,归结到73层的情形->...->...

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

可能讲的不是很清楚,直接看我代码上的算法说明应该更容易理解.
返回顶楼
          回帖地址
0 请登录后投票
  • 过儿oO
  • 等级: 初级会员
  • 性别:
  • 文章: 161
  • 积分: 66
  • 来自: 大连
   发表时间：2007-05-08  
看半天没明白为啥要一层一层走
为啥不直接一半一半走
2个条件啊，第一把放50层，碎了向下走一半，没碎向上走一半
用不了多少次就会固定了啊
还是我没理解这题呢？
返回顶楼
          回帖地址
0 请登录后投票
  • Eastsun
  • 等级: 二钻会员
  • 性别:
  • 文章: 790
  • 积分: 1329
  • 来自: 天津
   发表时间：2007-05-08  
呵呵,按楼上说的"，第一把放50层，碎了向下走一半"
那么如果再碎了呢?怎么确定临界层?

注意:这里只有两颗棋子,用完就没有了.而不是无限颗.
返回顶楼
          回帖地址
0 请登录后投票
  • bonny
  • 等级: 二星会员
  • 性别:
  • 文章: 1892
  • 积分: 215
  • 来自: SH
   发表时间：2007-05-08  
没有仔细看你的算法。我喜欢看数学公式。

我列出的公式是
|100%n|+n-1求最小值时n
返回顶楼
          回帖地址
0 请登录后投票
  • 过儿oO
  • 等级: 初级会员
  • 性别:
  • 文章: 161
  • 积分: 66
  • 来自: 大连
   发表时间：2007-05-08  
Eastsun 写道
呵呵,按楼上说的"，第一把放50层，碎了向下走一半"
那么如果再碎了呢?怎么确定临界层?

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


啊，是这样
但是我没明白那个是根据什么算地，我感觉每一层都有碎的可能，那么答案应该是放在第几层？
你那个算的是14层？还是什么
没明白啊
如果是14层，14层碎了咋办，往下放还是任意一层都有碎的可能啊
返回顶楼
          回帖地址
0 请登录后投票
  • Eastsun
  • 等级: 二钻会员
  • 性别:
  • 文章: 790
  • 积分: 1329
  • 来自: 天津
   发表时间：2007-05-08  
bonny 写道
没有仔细看你的算法。我喜欢看数学公式。

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


嘿嘿,我看到网上有也有人用你这个公式来解决这个问题.
不过,就个人看来,这个公式是错的.
返回顶楼
          回帖地址
0 请登录后投票
  • coolwangyu
  • 等级: 一星会员
  • 文章: 41
  • 积分: 161
  • 来自: 北京
   发表时间：2007-05-08  
我觉得这个是一个典型的概率计算。
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics