约瑟夫环问题

n个人(编号为0,1,...,n-1)围成一个圈子，从0号开始依次报数，每数到第m个人，这个人就得自杀，之后从下个人开始继续报数，直到所有人都死亡为止。问最后一个死的人的编号(其实看到别人都死了之后最后剩下的人可以选择不自杀……)。

约瑟夫环.jpg

---

问题主要有两种问法

• 问具体的自杀流程
• 问最后留下的那个人的编号

下面分别针对两种问法来说明：

1、自杀的流程

可以利用循环链表模拟整个流程
c++实现循环链表实现

#include <iostream>
/*
 * 约瑟夫问题利用循环链表进行模拟
 */
typedef  struct  node{
    int data;
    struct  node*  next;
} node;
//初始化循环链表
node* create(int n) {
    node *head, *p,*s;
    head = (node *) malloc(sizeof(node));  // 空头节点，仅提供一个链表初始化的入口
    p = head;
    if (0 != n) {
        for (int i = 1; i <= n; i++) {
            s = (node *) malloc(sizeof(node));
            s->data = i;
            p->next = s;
            p = s;
        }
        s->next = head->next;         //尾节点指向第一个存有数据的节点
    }
    free(head);
    return s->next;
}

void Josephus_Process(int n, int m, node* p){
    node* temp;
    while ( p->next != p ){
        for(int i = 1; i < m-1 ; i++){
            p = p->next;
        }
        std::cout<<p->next->data<<"->";
        temp = p->next;
        p->next = temp->next;
        free(temp);
        p = p->next;
    }
    std::cout<<p->data<<std::endl;
}
int main() {
     int n = 10;
     int m = 4;
     node* p = create(n);
    Josephus_Process(n,m,p);
     return 0;
}

2、最后留下存活的人

这时可以利用递归方法和数学推导得到最后留下的人

#include <iostream>
#include <list>
using std::cout;
using std::endl;
using std::cin;
using std::list;
 
int main()
{
    int total  = 0;
    cout << "Please input total number of people : ";
    cin >> total;
 
    int number = 0;
    cout << "Please input selected number : ";
    cin >> number;
 
    /* If number = 3
     * f(1) = 0
     * f(2) = 1 = (f(1) + 3) % 2
     * f(3) = 1 = (f(2) + 3) % 3
     * f(4) = 0 = (f(3) + 3) % 4
     * f(5) = 3 = (f(4) + 3) % 5
     * ...
     * f(n) = x = (f(n-1) + 3) % n
     * */
 
    int last = 0; // f(1) = 0
    for(int i = 2; i <= total; ++i)
    {
        last = (last + number) % i;
    }
    cout << "The last one is : " << last + 1 << endl;
 
    return 0;
}