#include <iostream>
using namespace std;
void josephus(int len, int k)
{
if(k < 1 || len < 1){
cout << "len and k cannont less than 1" << endl;
return;
}
bool *jose = new bool[len];
for(int i = 0; i < len; i ++){
jose[i] = true;
}
int remain = len;
int idx = 0;
int num = 0;
while(remain > 1){
while(jose[idx] != true){
idx ++;
if(idx == len){
idx = 0;
}
}
if(num == k - 1){
jose[idx] = false;
cout.width(4);
cout << idx << endl;
remain --;
}
num ++;
if(num == k){
num = 0;
}
idx ++;
if(idx == len){
idx = 0;
}
}
for(int i = 0; i < len; i++)
{
if(jose[i] == true){
cout.width(4);
cout << i ;
cout << " is the winner! " << endl;
}
}
delete[] jose;
}
int josephus2(int n, int m)
{
int i,r=0;
for (i=2;i<=n;i++)
r=(r+m)%i;
return r+1;
}
int josephus(int n, int k){ if (n == 1) return 1; else /* The position returned by josephus(n - 1, k) is adjusted because the recursive call josephus(n - 1, k) considers the original position k%n + 1 as position 1 */ return (josephus(n - 1, k) + k-1) % n + 1;}
int main(int argc, char* argv[])
{
josephus(11, 5);
return 0;
}
Output
4
9
3
10
6
2
1
5
8
0
7 is the winner!
Solution
Problem
There are people standing in a circle waiting to be executed. After the first person is executed, a certain number of people are skipped and one person is executed. Then, again, people are skipped and a person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.