5.5　吕洞宾不能坐首位

5.5　吕洞宾不能坐首位

循环排列位置是数学中一个有趣的问题，也是一个经典问题，可通过求余运算找出规律。下面我们从一个民间传说故事来研究这个问题。

5.5.1　座位安排

传说铁拐李、汉钟离、张果老、蓝采和、何仙姑、吕洞宾、韩湘子、曹国舅等8人称为八仙（如图5-15所示）。这天，八仙到天宫拜会王母娘娘。王母娘娘很高兴地地接待他们，正要让他们在一张八仙桌旁坐下时，有一件事让王母十分为难。按礼节她应该让八仙之首先入席，坐首位。可是八仙之首究竟该是谁呢？好像没有排出谁是老大。

图5-15

这时王母的香案使（王母身边的工作人员）想出了一个主意，他对八仙说：“我对各位一视同仁，毫无偏见。就由我来安排你们的座位吧，你们先排成一个圆圈，我请王母来掷两粒骰子，看看共掷出几点，就按这个点数，从第一个人开始数起，依次数到这个点数时，这个人就排除在外。这样周而复始，最后留下谁，谁就是八仙之首，让他先入席坐首位。”

八仙一听这办法有趣，也很公平，立即赞成，王母娘娘也觉得这个主意不错，也点头同意。

就在这时，观音菩萨也来了。观音看不惯吕洞宾的一些行为，不想让他成为八仙之首，便在王母耳边嘀咕了一番。

王母笑道：“菩萨放心，骰子掷出的点数纯属偶然，他只有八分之一的机会，未必能当上八仙之首。”

观音摇头说：“不行，我一定要排除他！”

王母听了此言，甚觉为难。观音说：“我有一个补救的方法，反正位置由香案使安排，我告诉他，把吕洞宾安排在某一位置上，然后从这个位置按顺时针方向计数，他就无法做八仙之首了。”

王母大喜，叫过香案使，观音对其耳语几句。然后，香案使按观音的指点，请八仙依次排成一圈，开始掷骰子数点数。后来，吕洞宾果真未当上八仙之首。

那么，香案使究竟把吕洞宾安排在哪个位置，才能确保将他排除出去呢？

5.5.2　试排座位找规律

接下来，我们来进行一下试排座位。

再来看一下香案使说的规则：按掷出骰子的点数，从第一个人开始数起，依次数到这个点数时，这个人就排除在外。这样周而复始，最后留下谁，谁就是八仙之首，让他先入席坐首位。

可以看出，需要解决两个问题：

首先要确定第一个人是谁，是从哪一个位置开始数起。

还需要确定掷出骰子的点数。由于是两粒骰子，点数最小为2（两粒都为1点时），最大为12（两粒都为6点时）。

其实，第一个人是谁不是大问题，排在第一位也可能会被排除。因此，只要将八仙进行编号，然后围成一个圈就可以，假如分别编号为X1、X2、X3、……、X7、X8，如图5-16所示。

图5-16

如果骰子点数为2，根据图5-16所示排列序号，被排除的顺序依次为：

最后只剩下一个序号X1，表示排在第一个位置的最后被保留，未被排除，则排在第一个位置的为八仙之首。因此，吕洞宾不能安排在第一个位置。

那么，如果骰子点数为3，被排除的顺序又是什么样的呢？

最后剩下的序号是X7，因此，吕洞宾也不能排在第7个位置上，否则也可能成为八仙之首。

按上面的方法，继续分析当骰子点数为4～12时的情况。最后得出骰子点数从2～12点时，各位置被排除的先后顺序如下（最后一个序号就是剩下的）：

对最后的序号进行总结，在11种骰子点数情况下，各位置被保留下来的次数如下：

可以看出，第4个位置被保留下来的次数为3次，概率最大，而第2个位置一次都没有被保留下来。

因此，观音对香案使的指点就是：将吕洞宾排在第2个位置，这样就可以确保他被排除。

5.5.3　西方的约瑟夫环

其实，对于循环排座位的问题，西方也有一个类似的故事。

据说著名历史学家Josephus（约瑟夫）经历过以下故事：在罗马人占领乔塔帕特后，40个犹太人和Josephus躲在一个山洞中。40个犹太人决定宁死也不被敌人抓到，于是决定集体自杀。大家经过讨论决定了一个自杀方式，41个人围成一个圆圈，由第1个人开始报数，每报数到3的人就必须自杀，然由再由下一个人重新开始报数，直到所有人都自杀身亡为止。

然而Josephus并不想遵从这个规则，不想自杀。于是，Josephus先假装同意该方案，然后坐到大家围成圆圈的第31个位置，最后逃过了这场死亡游戏。

那么，为什么Josephus坐在第31位置就可逃过该死亡游戏呢？

首先将41个人排成一个圆圈，并编好序号，如图5-17中圆内的编号（圆圈内的编号是座位序号，圆圈外的数字是每个人报到3的顺序）。然后从编号1的人开始报数，报到3就表示该人是第1个该自杀的人，序号为3的人首先数到3（将序号为3的人排除到圆圈之外），接下来序号为4的人又从1开始报数，……，这样不停地循环，序号为31的人将是最后剩下的一个人。由于前面的人都已自杀，没法监督到最后这个人是否遵守游戏规则了。

在这个故事中，用41个序号来表示这些人，不再是八仙中的8个序号，如果手工推算，需要很长的时间。因此，我们可以考虑借助计算机程序来进行推算。

在设计程序时，我们还可以考虑参与循环点数的人数N是一个可变的值，可将该数任意扩大或缩小，并假设有M个朋友不幸要参加这个游戏，又该如何保护自己和朋友，使这M个朋友都留在最后。

在计算机程序中，可以使用一种叫循环链表的数据结构来模拟约瑟夫环的结构，不过，这需要编写操作循环链表相关的代码，程序的代码比较多。为了简化程序，我们可以考虑用数组来保存约瑟夫环中应该出列的顺序序号数据，而数组的下标作为参与人员的编号，并将数组看作为环形来处理。

图5-17

具体的程序如下：

在上面的程序中，每行主要代码右侧都写有注释。

程序的算法也很简单：

（1）用一个数组保存约瑟夫环，其中数组元素的序号为参与人员的初始位置号，每个数组元素的值，就是对应序号人员出列的顺序。例如，若man[0]＝14，表示排在第1个位置的人将是第14个出列的人（数组元素是从0开始的，所以man[0]中的0表示第1个人）。

（2）不断循环，模拟报数的过程，将报到M（这里为3）的序号pos处的数组元素记上其出列的序号count（即设置man[pos]＝count），这样，man[n]的值若为0，表示还未出列。直到出列序号count达到总参与人数N为止。

（3）在man数组中已将出列序号标出来了，接下来就是找到最后出列的人，再找出其对应的原始位置序号。只要最初坐在这个序号对应的位置，就能确保其在最后才出列。

编译执行以上程序，程序首先显示出约瑟夫环的数列结果（前一个数据是最初的编号，后一个数据是约瑟夫环中的编号）。接着提示初始号为31的位置最后出列，最后出列的序号为N（41），即排在第31号位置的人在第41次出列，执行过程如图5-18所示。

图5-18

5.5.4　用数学方法解约瑟夫环

上面编写的解约瑟夫环的程序模拟了整个报数的过程，程序运行时间还可以接受，很快就可以出计算结果。可是，当参与的总人数N及出列值M非常大时，其运算速度就慢下来。例如，当N的值有上百万，M的值为几万时，到最后虽然只剩2个人，也需要循环几万次（M的数量）才能确定2个人中下一个出列的序号。显然，在这个程序的执行过程中，很多步骤都是进行重复无用的循环。

那么，能不能设计出更有效率的程序呢？

办法当然有。其中，在约瑟夫环中，只是需要求出最后的一个出列者最初的序号，而不必要去模拟整个报数的过程。因此，为了追求效率，可以考虑从数学角度进行推算，找出规律然后再编写程序即可。

为了讨论方便，先根据原意将问题用数学语言进行描述。

问题：将编号为0～（N－1）这N个人进行圆形排列，按顺时针从0开始报数，报到M－1的人退出圆形队列，剩下的人继续从0开始报数，不断重复。求最后出列者最初在圆形队列中的编号。

下面首先列出0～（N－1）这N个人的原始编号如下：