Codewars:一个鸡蛋引发的思考

在codewars上遇到这样一道题:

Eulampy 有一筐鸡蛋, 有一天在一幢摩天大楼下, 他的朋友对他说, 如果你给我n个鸡蛋, 我保证可以告诉你, 在h层楼的范围内, 鸡蛋最多从第几次楼扔下来而不会被摔破. Eulampy说, "没问题, 但是我最多同意你扔m次, 看你扔的次数太多我会难过的.", 请设计一个函数, height(n, m), 求扔鸡蛋实验的总量程, 即 h.

需要说明的是, 我们假设每个鸡蛋的都是完全一样的, 当一个鸡蛋被扔下了而没破, 就可以再次使用.

原题地址:https://www.codewars.com/kata/faberge-easter-eggs-crush-test/train/python

重点来了, 这道题有三组测试, 分别是: 基础的(basic), 进阶的(advanced), 真格的(serious).

test.it('basic tests')  
test.assert_equals(height(0,14),0)  
test.assert_equals(height(2,0),0)  
test.assert_equals(height(2,14),105)  
test.assert_equals(height(7,20),137979)

test.it('advanced tests')  
test.assert_equals(height(7,500),1507386560013475)  
test.assert_equals(height(237,500),431322842186730691997112653891062105065260343258332219390917925258990318721206767477889789852729810256244129132212314387344900067338552484172804802659)  
test.assert_equals(height(477,500),3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127420959866658939578436425342102468327399)

test.it('serious tests')  
test.assert_equals(height(477,10000),600461396604105297697414530102187796624607351959572356167325648574309381899274255809992726647041509608874296502550889633566626669839693460163703754386982346596293491455058459167135769401101845748849154474806919582238098292865002615140455747337045606515913175800206705264197158348258877027342824497813598887212567460615138259041983561196905824547148562128771846272230901329804068790524523450526723439711852711480043539388255029594388405065227411436195811544328549172691557810516507323615400468586962803403389031164507526999175383227883564967859574994520910983381843074859047295120948531800868902878466257920126328541103471268056861774184467685136934882998123768531695075047132113902537018783846627502099156246969377215926174782697180458326177412430190794351610099943109019040476655865297322723014683870220977314898596096355345407775)  
test.assert_equals(height(4477,10000),1322821654800439589583624607836730988904348989635184483838675315989863014466105368917516854788173412697117838413572154358020136361352589223655004309284002331356645126308444045548293566543482035130766876362770186754407172004758665811853489554425555053643908845358225658078400880897420458613361537230692347145029937146468449752350301582966318881236041448346697864308936041807973848575815961020957973841925430394889030910761307668821228255147323012321726504304076902912463702108956669795566661303469766408411346447369441900601416549889768545415835808703102634187636408616862788628220968336302080405978291461615690517333300338026427209023338744576796796711916921553117367799805818262372383440027895158535027538219368128415201884328355249194560412959735085368099726719812587209832125121706467856448219467001478841957398661311948630752866817235891668491371246314423172093241855801986462213764272472077704090737449586014952207200402488115806480036391258788025058712927761809494607747190593544252498024965313654475511753397288550572364193751016698751124385432059855618738610770405495965628076729605040379761490680887446751742893838217109555332410367754941969641188014103364853464553866605149284789373350284278475702952002720219396744665142719739890709306702230989773403063833223142722153866753072260856577382714941017978371516349454986201414282722361391051916542589551016023190730497041390846243435703142324656990673688597131961469432804559244656573403972845547140551161388227163311600434649131672174329566859257640294347413250504689740356122993141714018763824536995756394554473053764885655217850919825484110456823718017936279926312676444075372513295121643005522507990093614688397324087158672285564265461960725048409644632356562813282311892621316990617791305949952474644973231563181802912551788866587392922962344851922680688121341506499860485837386801968860995052055236149946250164753714765692652499211749864280505191012859114807502067989910205943513218116464920029858713308646212996605582239145947185971138791937105763767017369327250323372490209312303407044663140291579276982729680418229917148740734819240902048630120317091983651644063173722960555978628497587823422375493107579742775550922433788067185239451798388809414158837037653589325259023780409914069533039705450496176647169891013697813337588075535112140970187607803915384622627522925822608742766549203712747041753891038754047696049037861483951837513375322742464580059309440669921941688909946789319835787709445925359884114002203388057590959620340874700472926972472437928806956105916022048677333952506175442513146994611155259594220312914080066998804113859428782103809127996851589054428051854854318799508483531803897517007935349549152870011407064621017082135138020750461696192841200272984193298057507960103670538167626863921460268009725329427763452347838828602301814121408102409549978991436252168617142842111215900368726060166926158698664478612916125923479260041837538259289930459928491560009034059912265253387804412611357982786191578331327)  
test.assert_equals(height(9477,10000),19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373453647052103349469928076954249980154345544196049720110441880956939571653303125965015135210943821418326301263747755849915390311849600620405839184806696574011638771223876684308393546154357007879197176278577010897776871509293312271446308325915207411683581162864877565099831828100966285215817182861422299916721214461558309048173509038700144141092935627106729962305873603830938160653941875633254649208486247541063094454500007666144426589865904402944100565434252161641454059574448959059378469034843694065251975339636452128242737679086169540365161261103781301842588718151775952124493692901275351280453566829099730411742607415703660912889996893392281666409912913934377489142688784235343954049469043333120897248862080530937185907276885584072254792345533781517753151320818102507950307194516201547412495983145614252402137833853984659077543542376699008277188650448599930163536123001047126485885945475644)  

我想说, 在一开始拿到这道题的时候, 我完全低估了题目的难度...

首先, 我试着先将问题简化一下,

假设只有 1 个鸡蛋, 10 次尝试机会, 那么, 为了确保我这一个鸡蛋扔下去后, 我能知道鸡蛋在某层楼刚好不被摔破, 唯一的方式是从1楼开始一层一层的往上增加, 一直到第10层, 如果鸡蛋还是没破, 那没办法了, 因为 1 个鸡蛋 10 次机会, 最多只能保证在10层楼的范围内, 测出鸡蛋刚好不破的楼层数.

那让我们再进一步, 假如有 2 个鸡蛋, 还是 10 次机会, 让我们再来思考一下这个问题. 现在问题的关键是, 第一个鸡蛋我们应该从几楼开始往下扔? 需要考虑两种情况, 当我从第 x 层楼将鸡蛋扔下后, 鸡蛋也许碎了, 也许没碎. 假设鸡蛋碎了, 那么, 我必须确保我有办法通过剩下的 1 个鸡蛋和 9 次扔鸡蛋的机会测出鸡蛋在 x-1 层中刚好不破的楼层数. 一个鸡蛋的问题, 我们刚刚已经讨论过了, 1 个鸡蛋 9 次机会, h 为 9, 即 x-1 = 9, 所以 x = 1 + 9 = 10, 也就是说, 第一次扔鸡蛋, 我们应当从 10 楼开始往下扔. 那么继续, 假如鸡蛋没破呢, 那好办了, 我们现在有 2 个鸡蛋 9 次机会, 通过和前面一样的思考, 第二次扔的时候, 我们应该从 10 + 9 = 19 层往下扔. 那如果鸡蛋仍然没破呢, 我们就应该从 10 + 9 + 8 = 27 层往下扔, 以此类推, 我们可以发现, 当我们有 2 个鸡蛋 m 次机会时, 最大楼层 h = m(m-1)/2, 正好是等差数列的求和公式!

我整理了一下思路, 将上面的结论归纳了一下: 有 n 个鸡蛋, m 次尝试机会, 当我从第 x 层楼将鸡蛋扔下后, 鸡蛋也许碎了, 也许没碎. 假设鸡蛋碎了, 那么, 我必须确保我有办法通过剩下的 n-1 个鸡蛋和 m-1 次扔鸡蛋的机会在剩余的 x-1 层楼中测出鸡蛋刚好不破的层数. 假如鸡蛋没碎, 问题便转化成了 n 个鸡蛋 m-1 次机会的问题了. 嗯, 这听上去, 很递归!!!

好, 现在思路有了, 就让我们用递归来搞定这道题吧! 首先, 根据以上的推理, 我们可以很容易的得出递推公式:

height(n, m) = height(n, m-1) + height(n-1, m-1) + 1

具体的实现代码如下(python):

def height(n, m):  
  if n == 0 or m ==0:
    return 0
  return height(n, m - 1) + height(n - 1, m - 1) + 1

代码可以说是相当简洁干净了, basic测试顺利通过!

不过, 如果你真的以为这道题就到此为止的话, 你就和我一样天真了.

advance测试的第一条就挂了 ...

但我并没有放弃, 我开始仔细思考, 问题到底在哪呢 🤔

有了! height(n, m) 被拆分成了 height(n, m-1) 和 height(n-1, m-1), height(n, m-1) 被拆分成 height(n, m-2) 和 height(n-1, m-2), 而 height(n-1, m-1) 也会被差分成 height(n-1, m-2) 和 height(n-2, m-2). 发现问题了吗? height(n-1, m-2) 在两个分支里分别被计算了一次!! 考虑到 height(n-1, m-2) 后面还会衍生出很多的分支, 当 n, m 都比较大时, 这个计算量还是很客观的.

想到这里, 我马上对代码做了修改. 这里使用了python标准库中提供的 @lru_cache 注解, 实现对计算过的函数进行缓存, 同时, 为了避免参数递归层数过深, 还将最大递归深度限制调大.

from functools import lru_cache  
import sys

sys.setrecursionlimit(100000)

@lru_cache(maxsize=1000)
def height(n, m):  
    if n == 0 or m ==0:
        return 0
    return height(n, m - 1) + height(n - 1, m - 1) + 1

果然, 这次我顺利通过了 advanced 级别的测试, 执行单条 advanced 级别测试大概需要花费 800ms 左右.

不过, 如果你真的以为这道题就到此为止的话, 你就和我一样天真了.

或许是因为层层嵌套的递归结构消耗了太多的资源, serious 级别的测试依然无法通过.

我不得不开始认真的思考, 问题的关键到底在哪里 🤔

经过了各种Google学习, 我学习到了另一种解决这种递推式问题的方法, 那就是: 动态规划! 和递归一样, 动态规划的关键还是在于找出问题的递推公式, 即:

height(n, m) = height(n, m-1) + height(n-1, m-1) + 1

通过自底向上的方式得出问题的解, 在求解的过程中, 我们可以将前一步得出的计算结果保存下来, 避免重复计算.

def key(i,j):  
    return "%s-%s" % (i,j)

def height(n, m):  
    n = n if n < m else m
    save = {}
    for j in range(0, m+1):
        for i in range(0, n+1):
            if j == 0 or i == 0:
                save[key(i,j)] = 0
                continue
            save[key(i,j)] = save[key(i, j-1)] + 1 + save[key(i-1, j-1)]
    return save[key(n,m)]

和之前递归的代码相比, 算出一条 advanced 测试所需要的时间从 800ms 下降到了 600ms, 甚至, 还通过了 serious 级别的第一条测试(虽然耗费了惊人的11000ms左右).

到这一步, 我投降了. 第一次, 我选择看答案. 第一次, 我甚至连答案都看不懂. 代码如下:

def height(n, m):  
    h, t = 0, 1
    for i in range(1, n + 1): 
        t = t * (m - i + 1) // i
        h += t
    return h

WTF ??????????????????????????????????????????????????????

我大概花了3天时间, 来搞懂这段短短的代码.

还是回到最初的思路上来:

1 个鸡蛋 m 次机会 --> h 可以表示为 m

2 个鸡蛋 m 次机会 --> h 可以表示为

1+(m-1) + 1+(m-2) + 1+(m-3) ...  
= m + m(m-1)/2

3 个鸡蛋 m 次机会 --> h 可以表示为

1+(m-1)+(m-1)(m-2)/2 + 1+(m-2)+(m-2)(m-3)/2 + 1+(m-3)+(m-3)(m-4)/2 ...  

重点来了! f(m) = m(m-1)/2 + (m-1)(m-2)/2 + (m-2)(m-3)/2 ... 可表示为 (m+2)(m+1)m/(3*2), 具体证明如下:

当有3个蛋时, 假设推论成立, 那么

f(m) - f(m-1)  
= (m+2)(m+1)m/(3*2) - (m+1)m(m-1)/(3*2)
= 3(m+1)m/6
= (m+1)m/2

可知, 推论成立.

证明的过程是不是感觉很亲切? 对! 数学归纳法! (中学数学都白学了)

所以, 3 个鸡蛋 m 次机会 --> h 可以表示为

1+(m-1)+(m-1)(m-2)/2 + 1+(m-2)+(m-2)(m-3)/2 + 1+(m-3)+(m-3)(m-4)/2 ...  
= m + m(m-1)/2 + m(m-1)(m-2)/(3*2)

所以, 4 个鸡蛋 m 次机会 --> h 可以表示为 m + m(m-1)/2 + m(m-1)(m-2)/(3*2) + m(m-1)(m-2)(m-3)/(4*3*2) (不再证明)

当有n个鸡蛋时, h 可表示为 m + m(m-1)/2 + ... + m!/((m-n)!n!)

也就是答案中的代码了.

甚至还有大神发现(或者他们知道什么更高级的定理), 问题的解可以理解为对 (1+1)^m-1 做泰勒展开的前 n 项:

  • 二项式的泰勒展开公式 : (1+x)^k = 1 + kx + k(k-1)/2!*x^2 + ... + k(k-1)...(k-n+1)/n!x^k + ...

后记

在尝试解这道题的过程中, 还尝试过一些其他的思路, 最后都以失败告终, 例如用矩阵快速幂优化动态规划的思路, 最后也以失败告终.

可得仅包含 m 的递推公式:

具体可有如下代码. 不过最后也仅能通过 advanced, 而且并不快.

import numpy as np

def height(n, m):  
    if n ==0 or m ==0:
        return 0
    matrix = np.zeros((n, n), dtype=object)
    for i in range(n):
        matrix[i][i] = 1
        if i < n-1:
            matrix[i][i+1] = 1
    res = np.ones((n, 1), dtype=object)
    for i in range(m-1):
        res = matrix.dot(res) + np.ones((n, 1), dtype=object)
    return res[0]

关于用矩阵快速幂优化动态规划的细节, 可参看这篇博客.

虽然最后并没有靠自己的独立思考找到问题的答案, 但在解题的过程中也有不小的收获, 看来在学习算法的路上还有很长的路要走啊! 共勉!

Show Comments