Question

C++单链表做约瑟夫环

有M个人围坐成一圈，编号依次从1开始递增，现从编号为1的人开始报数，报到N的人出列，然后再从下一个人开始重新报数，报到N的人出列。重复这一过程直到所有人出列，求出列次序

Answer 1

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int a[1000000];

struct LNode{
    int num;
    LNode *next;
};
LNode *p, *r, *list;

/*利用单向循环链表实现*/
void joseph(int n, int m){//n：总人数；m：报数上限
    printf("\n%d个人报数，上限为%d \n", n, m);
    int i;
    //创建链表
    for (i = 1; i <= n; i++){
        p = new LNode;
        p->num = i;
        if (list == NULL)
            list = p;
        else
            r->next = p;
        r = p;
    }

    p->next = list;//使链表循环
    p = list;//p指向头结点
    r = p;

    //x循环删除队列中的结点，即出列
    printf("出列者序列：");
    while (p->next != p){
        for (i = 1; i<m; i++){
            r = p;
            p = p->next;
        }
        r->next = p->next;
        printf("%d ", p->num);
        free(p);
        p = r->next;
    }
    printf("\n最后留下的人是：%d\n", p->num);
}

int main(){
    for (int m, n; cin >> m >> n;)
        joseph(m, n);
    return 0;
}
/*
* n的初值为10，m为2，则出列顺序为 2 4 6 8 10 3 7 1 9，最后留下者是 5.
* n的初值为20，m为5，则出列顺序为 5 10 15 20 6 12 18 4 13 1 9 19 11 3 17 16 2 8 14，最后留下者是 7.
*/