<span>约瑟夫(Josephus)环问题</span>

1、假设有n个小孩坐成一个环，假如从第一- 个小孩开始数，如果数到m个小孩，则该小该离开，问最后留下的小孩是第几个小孩?例如总共有6个小孩，围成一圈，从第一个小孩开始，每次数2个小孩，则游戏情况如下。

小孩序号: 1，2，3，4，5，6
离开小孩序号: 2, 4, 6, 3, 1
最后留下的小孩是：5

分析: 定义一个数组child,每个元素代表一个小孩;元素下标可以作为小孩的序号，如child[0]代表第一个小孩，child[1]代表第 2个小孩，依次类推。小孩坐成一个环，而数组是线性的，要数组能从尾部跳到头部可以采用“加1取模”法。例如有6个小孩，那么下标 i 加 1 对 6 取模，下标 i =5(数组尾部)加 1 对 6 取模恰好为 0 ，即头元素下标。

代码如下：

#include <iostream>
using namespace std;
int Josephus(int child[], int n , int m);
int main() {
    const int num = 6;
    int persons[num] , winner;
    for(int i=0; i<num ;i++){
        persons[i] = i+1;       //孩子号码存在数组中
    }
    winner = Josephus(persons, num, 2);
    cout<<"胜利者："<<winner<<endl;
    return 0;                                                 
}

int Josephus(int child[], int n , int m){
//child为保存孩子的数组，n为小孩总数，m为数小孩的个数
    int i=-1, k=0;             //k为离开的人数
    while(1){                   //一直数，直到break退出
        for(int j=0;j<m; ){      //数m个孩子
           i = (i+1)%n;         //最关键的点，取下标加1的模，当i的值在0~n-1之间循环
           if(child[i] != -1){    //在循环中则继续数有效
             j++;
           }
        }      
        if(k == n-1){           //此时只有一个孩子，退出游戏
            break;
        }
        cout<<child[i]<<"；";
        child[i] = -1;          //离开的人标记为-1
        k= k+1;
   }
    cout<<"以上为离开的人"<<endl;
    return(child[i]);
}

//数组方法

运行结果：

*--->以下方法惊为天人*

emmm..........

#include <iostream>
using namespace std;

const int N = 5;  //小孩总数
const int M = 2;  //数小孩的个数

int main() 
{ 
    int s = 0; 
    for (int i=2; i<=N; i++){
        s = (s+M)%i; 
    } 
    cout<<"胜利者："<<s+1<<endl;
    return 0; 
}

//恐怖

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

　　分析: 由于有n个人，需要动态申请n个整型内存; 而不能使用数组。为了实现围成一圈，可以将链表尾部连到链首(单循环链表)，链表中每个节点代表一个人，凡报到 3 的人退出圈子，即将此节点从链表删除即可，当链表只剩下一个节点，即 p->next 等于本身 p ,说明节点是最后留下的。

代码如下：

#include <iostream>
using namespace std;

const int N = 4;  //小孩总数
const int M = 2;  //数小孩的个数
struct node{
    int info;
    struct node *next;
};
node *creat(int n);          //创建含有n个数据的循环链表 
void visit(node *p, int m);  //报数出圈 
void disp(node *p);          //遍历链表

int main() 
{ 
    node *head;
    head = creat(N);
    disp(head);
    visit(head, M);
    return 0; 
}

node *creat(int n){           
    node *q = NULL, *p, *head = NULL;
    for(int i=1; i<=n; i++){
        p = new node;
        p->info = i;
        if(i == 1){
            head = p;
        }else{
            q->next = p;
        }
        q = p;
    }
    q->next = head;     //头尾相接 
    return head;
}
void visit(node *p, int m){
    int i;
    node *q = p;
    cout<<"离开的人：";
    while(p->next != p){   //当链表不只是剩下一个节点 
        for(i=1; i<m-1; i++){
            p = p->next;
        }
        if(p->next != p){
            q = p->next;
            cout<<q->info<<";";
            p->next = q->next;
            delete q;
        }
        p = p->next;
    }
    cout<<endl<<"胜利者: "<<p->info<<endl;
}
void disp(node *p){
    node *q = p;
    cout<<"总人数："<<q->info<<";";
    q = q->next;
    while(q != p){            //非循环链表
        cout<<q->info<<";";
        q = q->next;
    }
    cout<<endl;
}