Google面试题，蓝桥杯题目

你拿着N个一模一样的鸡蛋站在M层的大楼上。鸡蛋或许很结实，到从楼顶掉下也不会摔破，或许很易碎，在一楼摔下就破碎。

最少试验多少次可以100%找出（鸡蛋不会被摔碎的最高楼层，全部都会摔碎也能找出，为0）？

N可以是1-100。M可能是1-500。

样例

输入（N，M）：

1 100

输出

100

解法：

对于只有1颗鸡蛋的情况，我们别无选择，只能从1楼开始，逐层向上测试，直到第i层鸡蛋摔碎为止，

对于2颗，选择折半？在50层丢，碎了最坏情况就是50次（不会被摔碎的最高楼层为49），没碎，继续折半

折半是个好办法，但是不是最优，问题出现在折半的碎和不碎差距很大

最优解法：让碎和不碎都是尝试一样的次数

采用dp，自下往上 或者 递归+备忘录

由于时间问题，这里采用python实现递归+备忘录，请读者自行解决c语言dp

import traceback

def f(eggCount,layer):

try:

if array[eggCount][layer] != -1:

return array[eggCount][layer]

if eggCount == 1:

array[eggCount][layer] = layer

return layer

min = layer

for i in range(1,layer+1):

#存储碎和没碎的临时答案

sui_lin = f(eggCount - 1, i - 1) +1

busui_lin = f(eggCount, layer-i) +1

# print("eggCount:"+str(eggCount)+",layer:"+str(layer))

# print("i:"+str(i))

# print("sui_lin:"+str(sui_lin))

# print("busui_lin:" + str(busui_lin))

if busui_lin >= sui_lin: # 不管碎还是不碎，每次选择更差情况，全局就是最差情况

min = busui_lin if busui_lin < min else min

else:

min = sui_lin if sui_lin < min else min

# 存储最优答案

array[eggCount][layer] = min

# print("eggCount:" + str(eggCount) + ",layer:" + str(layer))

# print(min)

return min

except:

print(eggCount)

print(layer)

traceback.print_exc()

exit()

buildingMinLayer=1

buildingMaxLayer=100

eggNum=2

# currentBestCount = buildingMaxLayer

array=[[]] #第0层没有数据

for i in range(eggNum):

array.append([-1 for x in range(buildingMinLayer-1,buildingMaxLayer+1)]) # 第0个没有数据

# for i in array:

# print(i)

result = f(eggNum,buildingMaxLayer)

print(result)

# 缺点，当数据量大：maximum recursion depth exceeded in comparison