约瑟夫问题 (sdut oj)

约瑟夫问题

Time Limit: 1000MS  Memory Limit: 65536KB

Problem Description

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

Input

输入n和m值。

Output

输出胜利者的编号。

Example Input

5 3

Example Output

4

Hint

第一轮：3被杀第二轮：1被杀第三轮：5被杀第四轮：2被杀

Author

参考代码

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