think: 1顺序建立循环链表+循环链表中的符合题意的元素结点的删除 2注意只有一个人玩死亡游戏的情况
sdut原题链接
约瑟夫问题 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
以下为accepted代码1
#include <stdio.h> #include <stdlib.h> struct node { int Data; struct node *next; }*head, *tail; void Build(int n);//顺序建立循环链表 void Search_ans(struct node *h, int m);//循环链表中删除满足题意的元素结点 int main() { int n, m; while(scanf("%d %d", &n, &m) != EOF) { if(n == 1) printf("%d\n", n); else { head = (struct node *)malloc(sizeof(struct node)); head->Data = 1;//循环链表中头结点不再为空 head->next = NULL; tail = head; Build(n);//顺序建立循环链表 Search_ans(head, m);//循环链表中删除满足题意的元素结点 } } return 0; } void Build(int n)//顺序建立循环链表 { struct node *p; for(int i = 2; i < n; i++) { p = (struct node *)malloc(sizeof(struct node)); p->Data = i; p->next = tail->next; tail->next = p; tail = p; } p = (struct node *)malloc(sizeof(struct node)); p->Data = n; tail->next = p; p->next = head; } void Search_ans(struct node *h, int m)//在循环链表中删除满足题意的元素结点 { int cnt = 0; struct node *q, *p; q = tail->next; p = head; while(p->next != p) { cnt++; if(cnt % m == 0) { q->next = p->next; free(p); p = q->next; } else { q = p; p = p->next; } } printf("%d\n", p->Data); } /*************************************************** User name: Result: Accepted Take time: 0ms Take Memory: 108KB Submit time: 2017-03-10 21:04:59 ****************************************************/以下为accepted代码2
#include <stdio.h> #include <stdlib.h> struct node { int Data; struct node *next; }*head, *tail; void Build(int n);//顺序建立循环链表 void Search_ans(struct node *h, int m);//循环链表中删除满足题意的元素结点 int main() { int n, m; while(scanf("%d %d", &n, &m) != EOF) { head = (struct node *)malloc(sizeof(struct node)); head->Data = 1;//循环链表中头结点不再为空 head->next = NULL; tail = head; Build(n);//顺序建立循环链表 Search_ans(head, m);//循环链表中删除满足题意的元素结点 } return 0; } void Build(int n)//顺序建立循环链表 { struct node *p; for(int i = 2; i < n; i++) { p = (struct node *)malloc(sizeof(struct node)); p->Data = i; p->next = tail->next; tail->next = p; tail = p; } if(n != 1) { p = (struct node *)malloc(sizeof(struct node)); p->Data = n; tail->next = p; p->next = head; } else { head->next = head; } } void Search_ans(struct node *h, int m)//在循环链表中删除满足题意的元素结点 { int cnt = 0; struct node *q, *p; q = tail->next; p = head; while(p->next != p) { cnt++; if(cnt % m == 0) { q->next = p->next; free(p); p = q->next; } else { q = p; p = p->next; } } printf("%d\n", p->Data); } /*************************************************** User name: Result: Accepted Take time: 0ms Take Memory: 108KB Submit time: 2017-03-10 21:06:48 ****************************************************/