2019-06-16 YTUOJ 2018: 约瑟夫问题

--------------------------------

Author ： ShawnDong

updateDate ：2019.6.16

Blog ： ShawnDong98.github.io

--------------------------------

题目描述：n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。 请输出最后一个人的编号。

//Author ： ShawnDong
//updateDate ： 2019/6/11.
//Blog ： ShawnDong98.github.io
//
#include "iostream"

using namespace std;
typedef long long ll;

typedef struct CLinkList{
    int data;
    struct CLinkList *next;
}node;

void Josephus(int n, int m){
    node *pHead = (node*)malloc(sizeof(node));
    pHead->next = pHead;
    node *r = pHead;

    for(int i=1; i<=n; i++){
        node *p = (node*)malloc(sizeof(node));
        p->data = i;
        r->next = p;
        r = p;
    }
    r->next = pHead->next;

    //n %=  m;

    node *p = pHead->next;
    while(p != p->next){
        for (int i = 1; i < m-1; i++)
        {
            p = p->next ;
        }

//        printf("%d->", p->next->data );

        node *temp = p->next ;              //删除第m个节点
        p->next = temp->next ;
        free(temp);

        p = p->next ;
    }

    printf("%d\n", p->data );


}

int main(){
    int n;
    int m;
    cin >> n;
    cin >> m;
    Josephus(n, m);
    return 0;
}