赞
踩
鸡蛋掉落问题是一道动态规划题,也就是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
事实上,具体就是这么扔的:
- 14 1 次
- 碎/ \
- / \
- [1, 13] 27 2 次
- 碎/ \
- / \
- [15, 26] 39 3 次
- 碎/ \
- / \
- [28, 38] 50 4 次
- 碎/ \
- / \
- [40, 49] 60 5 次
- 碎/ \
- / \
- [51, 59] 69 6 次
- 碎/ \
- / \
- [61, 68] 77 7 次
- 碎/ \
- / \
- [70, 76] 84 8 次
- 碎/ \
- / \
- [78, 83] 90 9 次
- 碎/ \
- / \
- [85, 89] 95 10次
- 碎/ \
- / \
- [91, 94] 99 11次
- 碎/ \
- / \
- [96, 98] 100 12次
OK,码农时间到:
给定K个蛋,N层楼(假定:1 <= K <= 100,1 <= N <= 10000),求:“扔鸡蛋最少的次数”是多少。使用这些次数,无论F是哪一层,通过扔鸡蛋,总是可以确定F的
public int superEggDrop(int K, int N){...}
说明:
1. 不用求出来扔的方式,只要求出来 “扔鸡蛋最少的次数” 即可
2. 当然,能输出 具体扔的方式就更好了)
好了,题意应该解释清楚了
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。