algorithm - Josephus p‌r‌o‌b‌l‌e‌m 中的消除顺序

Question

约瑟夫斯问题(或约瑟夫斯排列)是与某种数数游戏相关的理论问题。

People are standing in a circle waiting to be executed. Counting begins at the first point in the circle and proceeds around the circle in a clockwise direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed. For example if n=10 then the order of elimination is 2, 4, 6, 8, 10, 3, 7, 1, 9 and 5

The problem is, without simulation of the above game, try to find out the order of 
elimination through means of mathematical formula or a mathematical pattern.

最初我们得到 n，即开始时圈子中的人数。记住上述条件和限制，给出消除顺序。

简单来说，打印死亡模式而不使用任何数据结构，如数组和链表。

Answer 1

学习后准备了解决方案http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf .这个递归在上面的pdf中有提到。

int last_man(int n,int x)
{
    if(n==1 && x==1)
        return 1;
    else if(n>1 && x==1)
        return 2;
    else if(last_man(n-1,x-1)==n-1)
        return 1;
    else
        return last_man(n-1,x-1)+2;
}

X 表示第 x 个死亡的人，n 是最初的总人数。对从 1 到 n 的所有 x 值循环此函数，即可得出消除顺序。