小试递归与动态规划算法——Scratch编程解全错排问题

大家好，欢迎来到IT知识分享网。

（一）伯努利-欧拉装错信封问题

小明给他的n个同学写信，但他把所有的信都装错了信封（全错），问共有多少种全错的方式？这个问题实质上就是数学史上的一个著名的数论问题——错排问题。

因为最早研究这个问题的是当时著名数学家约翰·伯努利(Johann Bernoulli，1667-1748)的儿子丹尼尔·伯努利(Danid Bernoulli，17OO-1782)，后来瑞士大数学家欧拉(Leonhard Euler，1707-1783)也对此产生了兴趣，独立解决了这个难题，并称它为“组合理论的一个妙题”。故而史称伯努利-欧拉错装信封问题。

这个问题可以抽象成为一个排列组合问题：n个元素的序列，要求在排列中没有一个元素处于它原有的位置。

（二）算法分析

（1）枚举

用编程解决排列组合问题，我们最容易想到的是枚举法，究竟行不行呢？在不知道具体分析思路之前，可以先从1开始试试看，设n个信封错排数为f（n）。

当n = 1时，只有一个数字，不可能出现错排，所以f(1) = 0；

当n = 2时，全排列只有两种，分别是12和21，21是错排，所以f(2) = 1；

当n = 3时，全排列有6种，分别是123、132、213、231、312、321，其中231和312是错排，所以f(3) = 2；

当n = 4时，全排列有24种，其中错排有9种，分别是2143、2341、 2413、3142、 3412、3421、 4123、4312、 4321，所以f(4) = 9；

n=5, ……

我们知道，枚举算法的编程实现通常需要使用循环的，并且还是嵌套循环，嵌套的层数取决于n， n越大，循环的层数越来越多，而且n的值需要具体确定。对于这道不确定的排列组合问题，枚举法很可能不是最佳方法，在个数n很大甚至不确定的情况下，希望用多层循环嵌套几乎不可能实现。那就另辟蹊径，尝试使用别的方法。

（2）用动态规划思想推导递推公式

欧拉按一般情况给出了一个递推公式，分析如下。

用A1、A2、A3，……，An表示写着ｎ位友人名字的信封，B1、B2、B3,……,Bn表示ｎ份相应的写好的信纸。把错装的总数为记作F(n)。以信纸B1为基准，要装错，B1不能装入A1，先看假设把B1错装进A2里了是什么情况。包含着这个错误的一切全错装法分为两类：

第一类：B2装入Ａ1里，这时每种错装的其余部分都与A1、A2、B1、B2无关，只与除此之外的n-2个信封和信纸的错装有关，应有F(n－2)种错装法。　　　　

第二类：B1装入A1，A2之外的某一个信封，这时的装信工作实际是把除B1之外的n－1份信纸B2、B3,……,Bn装入除A2以外的n－1个信封A1、A3，……，An，显然这时装错的方法有F(n－1)种。总之在把B1错装进A2的错误之下，共有错装法F(n－2)＋F(n－1)种。

同样，此外，分别错把B1装进A3，A4，……,An，这n-2种情况之下，每种都有F(n－2)＋F(n－1)种全错装法。

因此F(n)＝(n－1)（F(n－1)＋F(n－2)）。

这是递推公式。令ｎ＝1、2、3、4、5逐个推算就能求出多个装错信封的解。是不是与著名的斐波拉契问题神似？

F(1)＝0，F (2)＝1，F (3)＝2，F (4)＝9，F (5)＝44，……

欧拉这个推导过程，把一个问题分解成若干个类似的子问题，实际上体现了动态规划算法的分治思想，。

（三）编程实现

有了算法分析，我们就可以用Scratch编程了：

（1）递归公式法程序实现

这个问题可以用递归公式求出任意一项的值，由于递推式中涉及到n – 1和n – 2，所以n = 1和n = 2应作为递推的结束条件，此时对个数赋初值a=0,b=1,并放入列表。后面就用递推公式将后面的项(n－1)（F(n－1)＋F(n－2)）加入列表，并依次轮换中间转换变量a和b的值，即把旧b赋给新的a，列表中的倒数第一项赋给新的b。

（2）递推循环方法

由于F（1）和F(2)是不能使用推导公式，所以循环需要在从n = 3开始，直到第n个元素结束，包括第n个元素。

接下来，获取用户输入，使用循环子程序即可，代码如下：

（四）拓展：错装问题可以各种不同的具体形式呈现，例如礼物与盒子，每个礼物都有一个精美的盒子。如果所有的礼物都不小心装错了盒子，求所有礼物都装错盒子共有多少种不同情况。观众与座位，影院里有编号为1~10的10个座位，10位观众分别坐在一个不同的位置上(1 ~ 10)，现要求打乱所有观众的位置，要求所有观众都不能出现在原来的位置上，问有多少种打乱的方法？

像伯努利-欧拉装错信封这类条件限制类排列问题，有一定难度，编程求解，枚举法很难实现，即使实现效率也很低，而使用动态规划和递归的算法更为有效。

你可以用递归的思想和动态规划的算法编程解决其它问题吗？比如斐波拉契数列问题、上楼梯问题等等。