约瑟夫问题之公式解法（迭代公式）

delete_007

    前几天在QQ群里看到一个有趣的问题——约瑟夫环问题，经过几天思索，有一些感悟，现在拿出来与大家分享，如有不当之处，请大家指正。    在此先感谢将此问题带进QQ群的朋友cleverzhzhf、wangg913，下面进入正题。

    本帖主要包含以下几个内容：
      一、什么是约瑟夫问题？
      二、隔一杀一问题
      三、普遍问题求解

delete_007

一、什么是约瑟夫问题？


    约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）
1.1 问题来历
    据说著名犹太历史学家 Josephus（约瑟夫）有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。这个自杀过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了总人数，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
1.2 约瑟夫问题的数学描述
    假设n个竞赛者排成一个环形，依次顺序编号1，2，…，n。从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。这个过程一直进行到所有的人都出列为止。最后出列者为优胜者。问题是：在给定n和m之后，优胜者的编号是多少？

delete_007

二、隔一杀一问题

    隔一杀一问题即每隔一个人就淘汰一个人，这实际上是约瑟夫问题的一个特例，相当于m=2的约瑟夫问题，这个问题的解也有一定的特殊性。
    这个问题早在2010年就已讨论过，参见http://club.excelhome.net/thread-596393-1-1.html
        当n正好是m=2的整数次方时（即n=2^p,p是大于等于1的正整数），经过一轮循环之后，所有偶数被杀，编号2^p的人被淘汰；下一轮编号为1的人计数仍然是1，而且剩下的人数是2^(p-1)仍然是2的整数倍（偶数），那么第二轮循环之后，编号2^(p-1)的人被淘汰，下一轮编号为1的人计数还是1，如此循环下去……容易知道胜利者就是编号1.
        当n=2^p+q（q<2^p的非负整数）时，我们只需要先淘汰q个人，将这个问题还原为2^p个人的情形就可以得出正确答案。
        从编号为1，2，……，n的序列中淘汰的第q<n/2个人的编号是多少呢？由于是隔一杀一，淘汰的都是偶数，第q个偶数就是2q.
        淘汰q个人之后，剩下的2^p个人重新编号，2q+1号就是新编号为1的人，根据前面的结果，这就是胜利者的编号。
    但是当时的思路主要是从淘汰过程的角度入手，这次我主要从数学的角度给予解释证明。


2.1 原理分析
    设f(n)为一开始有n个人时，胜利者的编号(注意：胜利者只有一个，n和f(n)是一一对应的函数关系)。第一轮循环之后，所有偶数被淘汰，第二轮循环之前，剩下的人重新编号以填补被淘汰人员的位置。
    如果总人数是偶数，设为2n（n为正整数)，经过第一轮循环之后，编号为2n的人被淘汰，编号为1的人在第二轮中的编号仍然为1。第二轮循环之前重新编号，那么在第一轮中编号为2x-1（1<=x<=n，这是奇数，因为偶数在第二轮已不存在）的人，在第二轮的编号为x(即去除2x-1之前的x-1个偶数），第二轮循环时共有n个人，其胜利者编号为f(n)，他在第一轮时的编号就是2f(n)-1，这就是总人数为2n的胜利者编号。于是得递推公式：
          f(2n)=2f(n)-1
    如果总人数是奇数，设为2n+1，经过第一轮循环，编号为2n的人被淘汰，接着被淘汰的人是1号；总淘汰n+1人，把剩下的n人重新编号，在第二轮中编号为x的人，原来编号是2x+1（因为1号已经被淘汰），于是得递推公式：
         f(2n+1)=2f(n)+1
    根据上述递推公式，可以得出n与f(n)的对应关系：
          n  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16
       f(n)  1  1  3  1  3  5  7  1  3   5   7    9   11  13  15   1
    从中可以看出，f(n)是一个递增的奇数数列，每当n是2的幂时，便重新从f(n)=1开始。因此，如果我们选择p和q，使得且n=2^p+q且0<=q<2^p，那么f(n)=2q+1。显然，表格中的值满足这个方程。我们用数学归纳法给出一个证明。
    定理：如果n=2^p+q且0<=q<2^p（p、q是非负整数），那么f(n)=2q+1
    证明：对n应用数学归纳法。
        当n=1=2^0+0时，p=0,q=0，f(n)=1=2*0+1显然成立。
        如果n是偶数，选择p和q，使n=2^p+q，那么n/2=2^(p-1)+q/2且0<=q/2<2^(p-1)，则
            f(n)=2f(n/2)-1=2(2*q/2+1)-1=2q+1，等式成立。
        如果n是奇数，令n=2t+1(t>=1的正整数）。选择y和z，使t=2^y+z且0<=z<2^y，则
            n=2t+1=2*(2^y+z)+1=2^(y+1)+(2z+1)令p=y+1，q=2z+1
            f(n)=2f(t)+1=2(2z+1)+1=2q+1，等式成立。 证毕。

delete_007

2.2 隔一杀一的公式求解
    根据上述定理，只要求出小于等于n的最大2^p，然后得出q=n-2^p，胜利者编号即为2q+1。
    主要有两种比较简单的思路：
      
    第一种方法，用Log函数来求最大的p值。直观简便，不再详述。
    第二种方法，将n用二进制数表示，那么它的最高位就表示2^p，用MID函数去掉最高位就得到q。2q+1对于2进制数来说，相当于每个数字向左移一位，即在最右端补一个0；而+1，则是把末位的0改为1，这就是胜利者编号的二进制结果，然后再转化成10进制数即可。
    当然也还有其他解法，欢迎大家添砖加瓦。

delete_007

三、普遍问题求解

    看完上述隔一杀一问题之后，大家肯定都有一个想法：对于更一般的约瑟夫问题，是否也能得出相似的结论呢？答案是否定的，当m>2时，没有相似的规律。下面来探讨一般的约瑟夫问题。
    可以用程序来求解约瑟夫问题，但要模拟整个游戏过程，程序也是比较繁杂，而且相当费时。为了追求效率，就要打破常规，实施一点数学策略。

3.1 约瑟夫问题的普适思路
   
    我们知道第一个被淘汰的人（编号为MOD(m-1,n)+1）出列之后，剩下的n-1个人组成新的约瑟夫环，以编号为k=MOD(m,n)+1的人开始。（此处使用MOD是应对m>=n的情况）
    1,2,3,4,……,m-2,m-1,m,m+1,m+2,……,n
    m被淘汰之后：
    k,k+1,k+2,k+3,……,n-1（其中k对应m+1，并且从1开始计数，这就是总人数为n-1的约瑟夫问题）
    假设我们知道n-1人的约瑟夫问题的胜利者编号为f(n-1),那么还原为n人约瑟夫问题，其胜利者就是MOD(f(n-1)+m-1,n)+1。
    这是一个递推公式，要求f(n),则需先求f(n-1)，要求f(n-1)，则需先求f(n-2),所以只要知道f(1)就可以求得任意f(n).
    显然f(1)=1
          f(n)=MOD(f(n-1)+m-1,n)+1, (n>1)

    可以从正向来理解上述公式，假设已知n，m的约瑟夫问题的胜利者编号为f(n)，那么如何求f(n+1)呢？
    对于n+1人的约瑟夫问题，只需要淘汰一人，就可以变成n人的情形。淘汰的第一个是谁呢？当然是第一个报到m的人，然后m+1又从1开始报数。由于已知f(n)，那么还原回最初编号即为f(n)+m，又f(n)+m可能已大于n+1,原来序列中无此编号，由于报数是按环形进行，大于n+1的号，也就是MOD(f(n)+m-1,n+1）+1。

3.2 迭代公式求解
    由于普适公式是递推公式，并不像隔一杀问题有最终公式表达式，所以启用迭代计算，才能得出正确结果。
    下面来看如何在EXCEL中使用迭代计算求解约瑟夫问题：
    首先分别在单元格中录入n，m的值，另外还需要设置一个控制迭代的辅助单元格。
        
    如上图，需要在C4,C5中设置公式：
    C4迭代参数用于产生1，2，……，100的参数序列，且F9自动重算不影响结果。于是有：
        =MOD(IF(C2="",,C4+1)-1,100)+1
    C5则是根据3.1节递推公式写成：
        =IF(C2="","",IF(C4=1,1,IF(C4>C2,C5,MOD(C5+C3-1,C4)+1)))
           即当C4=1时，C5=1，相当于f(1)=1
           而当2<=C4<=n=C2时，C5=MOD(C5+C3-1,C4)+1，这是递推公式f(n)=MOD(f(n-1)+m-1,n)+1的体现
           当C4>n=C2时，保持C5值不变即可。
    详情见附件： 约瑟夫问题之迭代解法.rar (9.23 KB, 下载次数: 36)

2014-8-4 13:49 上传

点击文件名下载附件

    从公式可以看出，无论计算n是多少的情况，都需要迭代100次。这实际上还可以进一步提升效率，通过VBA代码设置迭代次数为n，这样就不会有多余的计算。
    公式有优化：C4  =IF(C2="","",MOD(N(C4),C2)+1)
                                产生1，2，……，n的自然数序列。
                       C5  =IF(C2="","",IF(C4=1,1,MOD(C5+C3-1,C4)+1))
                                因为此时C4已不可能大于C2,所以迭代公式可以少一层判断。

    设置迭代次数的代码见附件： 约瑟夫问题之迭代解法（优化）.rar (10.08 KB, 下载次数: 50)

2014-8-4 14:35 上传

点击文件名下载附件

        （注意：如打开附件弹出循环引用提示框，请直接关闭对话框或点击“取消”以继续。）

delete_007

再占一楼，待补充。

13732120571

有点绕，慢慢看吧，先攒个位子

hehex

delete_007 发表于 2014-8-4 14:38
再占一楼，待补充。

看不懂哎，函数公式太深奥。理解不能。膜拜中...

cleverzhzhf

补充些关于迭代的讲解内容，辅助理解：

如果没有用过迭代，可先看以下第一个帖子的内容，好好理解一番，然后在第二个帖子进行练习。

1、用迭代实现无限制数组文本合并,和反接文本
地址：http://club.excelhome.net/thread-382167-1-1.html

2、【已结束】挑战题第4期——迭代按摩操 难度：★★ 分值：2分
地址：http://t.excelhome.net/thread-9317-1-1.html

人事难料

早上看到权限200就知道有好东西看，可是看了已经半个多小时了，实在没领会多少。继续啃。