当前位置:   article > 正文

解释“鸡蛋掉落问题”的题意_扔鸡蛋最少仍几次会摔碎

扔鸡蛋最少仍几次会摔碎

鸡蛋掉落问题是一道动态规划题,也就是leetcode的 https://leetcode-cn.com/problems/super-egg-drop/

我发现不止我一人搞不懂该题的题意,本文不讨论如何解决该问题,仅仅用大白话解释下题意
问题:
2个蛋,100层楼
给定如下三个条件:
    a. 楼层F必定存在,且,0 =< F <= 100
    b. 站在楼上扔鸡蛋,楼层<=F时,鸡蛋摔不碎。摔不碎的蛋总是可以用来扔
    c. 站在楼上扔鸡蛋,楼层   >F时,鸡蛋摔碎

F可以是任意一个楼层(0 =< F <= 100),而,无论F是哪一层,通过扔鸡蛋,总是可以确定F的

求:扔鸡蛋最少的次数。使用这些次数,无论F是哪一层,通过扔鸡蛋,总是可以确定F的

答案:“2个蛋,100层楼”时,扔鸡蛋最少次数是14。即:14次之内,无论F在哪一层,总是可以找到楼层F

事实上,具体就是这么扔的:

  1.           14                                        1
  2.       碎/    \                                      
  3.        /      \                                     
  4.   [1, 13]      27                                   2
  5.              碎/ \                                  
  6.               /   \                                 
  7.         [15, 26]   39                               3
  8.                 碎/ \                               
  9.                  /   \                              
  10.           [28, 38]    50                            4
  11.                    碎/ \                              
  12.                     /   \                             
  13.              [40, 49]    60                         5
  14.                       碎/ \                           
  15.                        /   \                          
  16.                 [51, 59]    69                      6
  17.                          碎/ \                        
  18.                           /   \                       
  19.                    [61, 68]    77                   7
  20.                             碎/ \                     
  21.                              /   \                    
  22.                       [70, 76]    84                8
  23.                                碎/ \                  
  24.                                 /   \                 
  25.                          [78, 83]    90             9
  26.                                   碎/ \               
  27.                                    /   \              
  28.                             [85, 89]    95          10
  29.                                      碎/ \            
  30.                                       /   \           
  31.                                [91, 94]   99        11
  32.                                         碎/ \         
  33.                                          /   \        
  34.                                   [96, 98]   100    12


OK,码农时间到:
给定K个蛋,N层楼(假定:1 <= K <= 100,1 <= N <= 10000),求:“扔鸡蛋最少的次数”是多少。使用这些次数,无论F是哪一层,通过扔鸡蛋,总是可以确定F的
public int superEggDrop(int K, int N){...}

说明:
1. 不用求出来扔的方式,只要求出来 “扔鸡蛋最少的次数” 即可
2. 当然,能输出 具体扔的方式就更好了)

好了,题意应该解释清楚了

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/709842
推荐阅读
相关标签
  

闽ICP备14008679号