馬世勝　王德貴

伯努利-歐拉裝錯(cuò)信封問(wèn)題，是數(shù)學(xué)史上著名的數(shù)論問(wèn)題，其實(shí)是排列組合問(wèn)題，今天我們用Python來(lái)進(jìn)行分析和求解。

1.伯努利-歐拉裝錯(cuò)信封問(wèn)題

某人想邀請(qǐng)朋友來(lái)家中聚會(huì)，寫(xiě)好了5封請(qǐng)柬，需要裝入5個(gè)信封，結(jié)果因?yàn)榇中陌颜?qǐng)柬全部裝錯(cuò)了信封。請(qǐng)問(wèn)：裝錯(cuò)的可能會(huì)有多少種呢（圖1）？

這個(gè)問(wèn)題是由當(dāng)時(shí)有名的數(shù)學(xué)家約翰·伯努利（Johann Bernoulli，1667-1748年）的兒子丹尼爾·伯努利（Danid Bernoulli，1700-1782年）提出來(lái)的，瑞士著名數(shù)學(xué)家歐拉（Leonhard Euler，1707-1783年）按一般情況給出解答。

這個(gè)問(wèn)題可以描述為一個(gè)排列組合問(wèn)題：n個(gè)元素的序列，要求在排列中沒(méi)有一個(gè)元素處于它原有的位置。

2.算法分析

用編程解決排列組合問(wèn)題，我們常常利用枚舉法，對(duì)于這道不確定的排列組合問(wèn)題，枚舉法很可能不是最佳方法，不過(guò)在我們知道具體分析思路之前，可以先試試看。

3.枚舉法程序?qū)崿F(xiàn)

先假設(shè)只有3封信的情況（圖2）。

運(yùn)行結(jié)果如下，有2種方法（圖3）。

那么4個(gè)、5個(gè)信封應(yīng)該是類(lèi)似的，下面是5封信的程序，只是增加了2重循環(huán)，其他完全一樣（圖4）。

運(yùn)行結(jié)果是44種。如果是更多的信封，這樣做就很麻煩了。那么有沒(méi)有規(guī)律呢（圖5）？

4.遞推公式法程序?qū)崿F(xiàn)

瑞士著名數(shù)學(xué)家歐拉按一般情況給出了一個(gè)遞推公式，分析如下：

用A、B、C……表示寫(xiě)著n位友人名字的信封，a、b、c……表示n份相應(yīng)的寫(xiě)好的信紙。把錯(cuò)裝的總數(shù)記作D（n）。假設(shè)把a(bǔ)錯(cuò)裝進(jìn)B里了，包含著這個(gè)錯(cuò)誤的一切錯(cuò)裝法分兩類(lèi)：

（1）b裝入A里，這時(shí)每種錯(cuò)裝的其余部分都與A、B、a、b無(wú)關(guān)，應(yīng)有D（n-2）種錯(cuò)裝法。

（2）b裝入A、B之外的一個(gè)信封，這時(shí)的裝信工作實(shí)際是把（除a之外的）n-1份信紙b、c……裝入（除B以外的）n-1個(gè)信封A、C……顯然這時(shí)裝錯(cuò)的方法有D（n-1）種。

總之在a裝入B的錯(cuò)誤之下，共有錯(cuò)裝法D（n-2）+D（n-1）種。

a裝入C、裝入D……的n-2種錯(cuò)誤之下，同樣都有D（n-1）+D（n-2）種錯(cuò)裝法，因此D（n）=（n-1）[D（n-1）+D（n-2）]

這是遞推公式。令n=1、2、3、4、5逐個(gè)推算就能求出多個(gè)裝錯(cuò)信封的解。

D（1）=0，D（2）=1，D（3）=2，D（4）=9，D（5）=44

程序如下，這樣我們就有了一個(gè)通用程序，可以求出任意一項(xiàng)的值（圖6）。

利用遞推公式，也可以求出前n項(xiàng)的值（圖7）。

5.遞歸公式法程序?qū)崿F(xiàn)

這個(gè)問(wèn)題也可以用遞歸公式求出任意一項(xiàng)的值（圖8）。

輸入任意信封個(gè)數(shù)后可以獲得滿意的結(jié)果（圖9）。

稍微修改一下，也可以求出前n項(xiàng)的值（圖10）。

6.結(jié)論

伯努利-歐拉裝錯(cuò)信封問(wèn)題，涉及到的是高中數(shù)學(xué)的排列組合問(wèn)題，這是難點(diǎn)也是重點(diǎn)，也稱(chēng)為條件限制類(lèi)排列問(wèn)題。

用Python求解，枚舉法很難實(shí)現(xiàn)，即使實(shí)現(xiàn)效率也很低，而遞推和遞歸的方法更為有效。當(dāng)然在各種算法中，枚舉法雖然效率有時(shí)低一點(diǎn)，但對(duì)某些問(wèn)題還很奏效。

遞推和遞歸是等級(jí)考試4級(jí)內(nèi)容，希望大家在學(xué)習(xí)Python的過(guò)程中，循序漸進(jìn)，做好基礎(chǔ)知識(shí)的理解和掌握。