算法
, ,

约瑟夫环问题

Catalogue
  1. 1. 问题
  2. 2. 回答

问题

有 n 个人围成一圈，顺序排号。从第一个人开始报数（从 1 到 3 报数），凡报到 3 的人退出圈子，问最后留下的是原来第几号的那位。

跟群名似乎无关，但是感觉挺好玩 🤪

回答

C 语言模拟 @capwill2

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
31
32
#include <iostream>
using namespace std;
#define MAX 100000

int num[MAX];

int main()
{
    int n,p;
    cin>>n>>p;
    int i=1,current_step=1,killed=0;

    while(killed!=n-1){
        if(current_step==p){
            num[i]=1;
            killed++;
            cout<<"kill "<<i<<endl;
            current_step=0;
        }
        i++;
        if(i>n)
            i=1;
        if(num[i]==0)
            current_step++;
    }

    for(int i=1;i<=n;i++)
        if(num[i]==0) cout<<"survivor: "<<i;


    return 0;
}

思路是用数组模拟循环链表。