Joseph problem

Posted on | In

本文主要是来回顾下约瑟夫问题

什么是约瑟夫问题

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 n 个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。

在算法题里面主要是有两种，第一是是直接输出剩余的最后一个胜利者，第二是按顺序输出出圈人的index.

首先，典型的约瑟夫问题如下

  • 题目描述：n 个人围成一圈，从第一个人开始报数,数到 mm 的人出列，再由下一个人重新从 11 开始报数，数到 mm 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号
  • 输入：输入两个整数 n,mn,m
  • 输出： 输出一行 nn 个整数，按顺序输出每个出圈人的编号
  • 样例: 输入： 10 3 输出：3 6 9 2 7 1 8 5 10 4

代码如下

暴力解法- 直接模拟的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
using namespace std;
const int N=100;
bool st[N];
//Simulate this process n
int main(){
    int n,m;
    cin>>n>>m;
    int p=1;
    int k;
    for(int i=0,r=n;i<=n;i++,r--) // 每次循环一圈。循环一圈，总的数量减一
    {
        k=m;//每次循环删除m的人，同时这个地方可以存在存在变种
        while (true) {
            if (!st[p]) {
                k--;
                if (!k) {
                    st[p] = true;// 每一次设置剔除的标号为m的人
                    cout<<p<<" ";
                    break;
                }
            }
            p++;
            if (p > n) p = 1;// 如果p大于最大数，则重新从头开始查找
        }
    }
//#cout<<p<<endl;
    return 0;

}

上式子中，while的条件地方可以直接有for来优化，可以写成下面这样

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;
int main()
{
    int n,m,s=0;scanf("%d%d",&n,&m);//入读
    bool visit[200]={0};//visit赋初始值
    for(int k=0;k<n;k++){//总共要出队n次
        for(int i=0;i<m;i++){if(++s>n)s=1;if(visit[s])i--;}//类似取模，而因为序列是从1开始的，所以不取模，加判断；若visit过，则i--，使其继续循环
        printf("%d ",s);visit[s]=true;//输出，记录已出队
    }
    return 0;
}

此外如果只是需要输出最后的胜利者，则这个地方其实是可以用dp来解的，代码如下，主要的解释在代码中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//N个人坐成一个圆环（编号为1 - N），从第1个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。
//例如：N = 3，K = 2。2号先出列，然后是1号，最后剩下的是3号。
//这种情况下不需要考虑谁先死，故可以转化为递归问题，f(n)=(f(n-1)+k)%i,其中k，代表着每次都是从k的地方开始，同时n，代表遍历几次，故把问题转化为n-1，n-2,...1阶的问题
#include <iostream>
using namespace std;
int n,k;
int main()
{
	scanf("%d %d",&n,&k);
	int ans=0;
	for(int i=1;i<=n;i++)
	ans=(ans+k)%i;
	printf("%d",ans+1);
}

输出最后一个胜利者的题目，变种题目，是paypal的一道笔试题目，描述如下

幸存者游戏

  • 有n个同学围成一圈，其id依次为1~n（n号挨着1号）。
    现在从1号开始报数，第一回合报到m的人就出局，第二回合从出局的下一个人开始报数，报到m2的同学出局。
    以此类推，直到最后一个回合报到mn−1的人出局，剩下最后一个同学。
    输出这个同学的编号。

  • 输入格式
    共一行，包含两个整数n和m。

  • 输出格式
    输出最后剩下的同学的编号。

  • 数据范围
    n≤15,m≤5

  • 输入样例：
    5 2

  • 输出样例：
    5

该题其实就是约瑟夫问题的一个变种，只是修改了m的条件，设置了什么时候才将第i个人扔掉，故代码可以直接修改上方的暴力破解的方法(因为数据范围n<=15>),故代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
using namespace std;
const int N=16;
bool st[N];
int main(){
    int n,m;
    cin>>n>>m;
    int p=1;
    for(int i=1,r=n;i<=n;i++,r--){
        int k=1;
        for(int j=0;j<i;j++) k=k*m%r;
        if(k==0)k=r;
        while(true){
            if(!st[p])
            {
                k--;
                if(!k){
                      st[p]=true;
                      break;
                }
            }
                p++;
                if(p>n)p=1;
        }
    }
    cout<<p<<endl;
    return 0;
}