關于智力買電影票的練習題

　　有2n個人排隊進電影院，票價是50美分。在這2n個人當中，其中n個人只有50美分，另外n個人有1美元(紙票子)。愚蠢的電影院開始賣票時1分錢也沒有。問：有多少種排隊方法使得每當一個擁有1美元買票時，電影院都有50美分找錢

　　注：1美元=100美分擁有1美元的人，擁有的是紙幣，沒法破成2個50美分

　　【解答】本題可用遞歸算法，但時間復雜度為2的n次方，也可以用動態規劃法，時間復雜度為n的平方，實現起來相對要簡單得多，但最方便的就是直接運用公式：排隊的種數=(2n)!/[n!(n+1)!]。

　　如果不考慮電影院能否找錢，那么一共有(2n)!/[n!n!]種排隊方法(即從2n個人中取出n個人的組合數)，對于每一種排隊方法，如果他會導致電影院無法找錢，則稱為不合格的，這種的排隊方法有(2n)!/[(n-1)!(n+1)!](從2n個人中取出n-1個人的組合數)種，所以合格的排隊種數就是(2n)!/[n!n!]-(2n)!/[(n-1)!(n+1)!]=(2n)!/[n!(n+1)!]。

【智力買電影票的練習題】相關文章：

《買文具》同步練習題06-22

小學數學10道智力練習題精選06-22

《智力測驗》閱讀練習題及答案11-10

《買大象》閱讀練習題及答案11-20

《電影票的秘密》說課稿10-15

《電影票的秘密》說課稿11-29

《電影票的秘密》說課稿范文11-04

三只小兔子買裙子數學智力測試題06-19

假期電影票銷售實習總結04-14