關(guān)于智力買(mǎi)電影票的練習題
有2n個(gè)人排隊進(jìn)電影院，票價(jià)是50美分。在這2n個(gè)人當中，其中n個(gè)人只有50美分，另外n個(gè)人有1美元(紙票子)。愚蠢的電影院開(kāi)始賣(mài)票時(shí)1分錢(qián)也沒(méi)有。問(wèn)：有多少種排隊方法使得每當一個(gè)擁有1美元買(mǎi)票時(shí)，電影院都有50美分找錢(qián)
注：1美元=100美分擁有1美元的人，擁有的是紙幣，沒(méi)法破成2個(gè)50美分
【解答】本題可用遞歸算法，但時(shí)間復雜度為2的n次方，也可以用動(dòng)態(tài)規劃法，時(shí)間復雜度為n的平方，實(shí)現起來(lái)相對要簡(jiǎn)單得多，但最方便的就是直接運用公式：排隊的種數=(2n)!/[n!(n+1)!]。
如果不考慮電影院能否找錢(qián)，那么一共有(2n)!/[n!n!]種排隊方法(即從2n個(gè)人中取出n個(gè)人的組合數)，對于每一種排隊方法，如果他會(huì )導致電影院無(wú)法找錢(qián)，則稱(chēng)為不合格的，這種的排隊方法有(2n)!/[(n-1)!(n+1)!](從2n個(gè)人中取出n-1個(gè)人的組合數)種，所以合格的排隊種數就是(2n)!/[n!n!]-(2n)!/[(n-1)!(n+1)!]=(2n)!/[n!(n+1)!]。
【智力買(mǎi)電影票的練習題】相關(guān)文章：
《買(mǎi)文具》同步練習題06-22
《智力測驗》閱讀練習題及答案11-10
《買(mǎi)大象》閱讀練習題及答案11-20
《電影票的秘密》說(shuō)課稿10-15
《電影票的秘密》說(shuō)課稿11-29
《電影票的秘密》說(shuō)課稿范文11-04