數(shù)學(xué)邏輯推理題8（買電影票）

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

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

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

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

　　 歡迎使用手機(jī)、平板等移動設(shè)備訪問中考網(wǎng)，2023中考一路陪伴同行！>>點(diǎn)擊查看