龙空技术网

趣味数学——伯努利-欧拉装错信封问题

壹零社爱科学 298

前言:

而今朋友们对“欧拉法编程”大体比较注意,咱们都需要剖析一些“欧拉法编程”的相关知识。那么小编也在网摘上网罗了一些有关“欧拉法编程””的相关知识,希望你们能喜欢,我们快快来学习一下吧!

文/辽源市第十九中学校 马世胜 王德贵

伯努利-欧拉装错信封问题,是数学史上著名的数论问题,其实是排列组合问题,今天我们用Python来进行分析和求解。

1.伯努利-欧拉装错信封问题

某人想邀请朋友来家中聚会,写好了5封请柬,需要装入5个信封,结果因为粗心把请柬全部装错了信封。请问:装错的可能会有多少种呢(图1)?

这个问题是由当时有名的数学家约翰·伯努利(Johann Bernoulli,1667-1748)的儿子丹尼尔·伯努利(Danid Bernoulli,17OO-1782)提出来的,瑞士著名数学家欧拉(Leonhard Euler,1707-1783)按一般情况给出解答。

这个问题可以描述为一个排列组合问题:n个元素的序列,要求在排列中没有一个元素处于它原有的位置。

2.算法分析

用编程解决排列组合问题,我们常常利用枚举法,对于这道不确定的排列组合问题,枚举法很可能不是最佳方法,不过在我们不知道具体分析思路之前,可以先试试看。

3.枚举法程序实现

先假设只有3封信的情况(图2)。

运行结果如下,有2种方法(图3)。

那么4个、5个信封应该是类似的,下面是5封信的程序,只是增加了2重循环,其它完全一样(图4)。

运行结果是44种。如果是更多的信封,这样做就很麻烦了。那么有没有规律呢(图5)?

4.递推公式法程序实现

瑞士著名数学家欧拉按一般情况给出了一个递推公式,分析如下。

用A、B、C……表示写着n位友人名字的信封,a、b、c……表示n份相应的写好的信纸。把错装的总数为记作D(n)。假设把a错装进B里了,包含着这个错误的一切错装法分两类:

(1)b装入A里,这时每种错装的其余部分都与A、B、a、b无关,应有D(n-2)种错装法。    

(2)b装入A、B之外的一个信封,这时的装信工作实际是把(除a之外的)n-1份信纸b、c……装入(除B以外的)n-1个信封A、C……,显然这时装错的方法有D(n-1)种。

总之在a装入B的错误之下,共有错装法D(n-2)+D(n-1)种。

a装入C,装入D……的n-2种错误之下,同样都有D(n-1)+D(n-2)种错装法,因此D(n)=(n-1)[D(n-1)+D(n-2)]

这是递推公式。令n=1、2、3、4、5逐个推算就能求出多个装错信封的解。

D(1)=0,D(2)=1,D(3)=2,D(4)=9,D(5)=44

程序如下,这样我们就有了一个通用程序,可以求出任意一项的值(图6)。

利用递推公式,也可以求出前n项的值(图7)。

5.递归公式法程序实现

这个问题也可以用递归公式求出任意一项的值(图8)。

输入任意信封个数后可以获得满意的结果(图9)。

稍微修改一下,也可以求出前n项的值(图10)。

6.结论

伯努利-欧拉装错信封问题,涉及到的是高中数学的排列组合问题,这是难点也是重点,也称为条件限制类排列问题。

用Python求解,枚举法很难实现,即使实现效率也很低,而递推和递归的方法更为有效。当然在各种算法中,枚举法虽然效率有时低一点,但对某些问题还很奏效。

递推和递归是等级考试4级内容,希望大家在学习Python过程中,循序渐进,做好基础知识的理解和掌握。

标签: #欧拉法编程