约瑟夫环|丢手绢问题

oyangningtao

丢手绢游戏规则： 有N(N<=1000)个小朋友玩丢手绢游戏，坐成一圈，从第一个小朋友开始数数，从1开始数，数到指定数字M的小朋友要出列，然后下一个小朋友继续从1开始数，依次类推，算出最后一个留下来的小朋友是谁？丢手绢问题又称为约瑟夫环，是一个计算机科学和数学中的问题。

模拟法       

（1）由于对于每个小朋友只有出列和在列两种状态，因此可以用布尔型数组标记每个小朋友的状态，可用true表示出列，false表示在列。

        （2）开始时每个小朋友都在列，所以数组初值全部赋为false。

        （3）模拟整个丢手绢过程，直到只剩一个小朋友为止。

        模拟丢手绢过程

#include <iostream>

using namespace std;

int main()

{

   bool a[1001] = {0};

   int n, m, i, f = 0, t = 0, s = 0;

   cin >> n >> m;

   while(f<n)

   {

       ++t;        //逐个枚举圈中的所有位置

       if (t > n)

           t = 1;  //数组模拟环状，最后一个与第一个相连

       if (!a[t])

           s++;    //第t个位置上有人则报数

       if (s == m) //当前报的数是m

       {

           s = 0;             //计数器清零

           a[t] = true;     //此处已出列，设置为true

           //cout<<t<<’\n’; //输出依次出列的序号

           f++;               //已出列人数+1

       }

   }

   cout<<t;//最后一个出列

   return 0;

}

时间复杂度：O(n*m)，当n、m非常大时候，一定会超时。

空间复杂度：O(N)，N为人数的最大值，本示例为1000。

         

递推算法

问题描述：n个人（编号0~(n-1）），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数，求胜利者的编号。（为便于讨论，定义编号为0～n-1）

        第一个人（编号为（m-1）mod n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号k=m mod n开始）：

        k k+1 k+2 ... n-2,n-1,0,1,2,... k-2

        并且从k开始报0，把编号做转换：

        k --> 0

        k+1 --> 1

        k+2 --> 2

        ...

        k-2 --> n-2

        变换后就完完全全成为了（n-1）个人报数的子问题，假如此子问题的解为x，那么根据上面这个表把这个x还原就是n个人情况的解：x'=(x+k) mod n

        令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果为f[n]

        递推公式

        f[1]=0;

        f=(f[i-1]+m) mod i; (i>1）

        实际生活中编号从1开始，输出f[n]+1

#include <iostream>

using namespace std;

int main()

{

   int n, m, s = 0;

   cin >> n >> m;

   for (int i = 2; i <= n; i++)

       s = (s + m) % i;

   cout << s + 1;

   return 0;

}

时间复杂度：O(n)。

空间复杂度：O(1)。