约瑟夫问题

约瑟夫问题

Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic

Problem Description

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

Input

输入n和m值。

Output

输出胜利者的编号。

Example Input

5 3

Example Output

4 #include<stdio.h> #include<stdlib.h> struct node {     int data;     struct node*next; }; int main() {     int n ,i ,num ,m;     scanf("%d %d",&n,&m);     struct node*head,*p,*tail,*q;     i = num = 1;     p = (struct node*)malloc(sizeof(struct node));     p->data = i;     head = p;     tail = p;     p->next = NULL;     for(i = 2;i<=n;i++)     {         p = (struct node*)malloc(sizeof(struct node));         p->data = i;         p->next = NULL;         tail->next = p;         tail = p;     }     tail->next = head;     q = head;     while(q->next!=q)     {         p = q->next;         num++;         if(num%m==0)         {             q->next = p->next;             free(p);         }         else q = p;     }     printf("%d\n",q->data);     return 0; }