当前位置: 代码迷 >> 综合 >> 约瑟夫问题 oj
  详细解决方案

约瑟夫问题 oj

热度:17   发布时间:2024-01-14 22:57:56.0

约瑟夫问题

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 no;struct node *next;
};
int main()
{int n,m,i,num = 0,count = 0;struct node *head, *p, *tail;scanf("%d%d",&n,&m);head = (struct node *)malloc(sizeof(struct node));tail = head;for(i = 1;i <= n;i++){p = (struct node *)malloc(sizeof(struct node));p->no = i;p->next = NULL;tail->next = p;tail = p;}tail->next = head->next;p = head->next;tail = head;while(count < n - 1){p = tail->next;num++;if(num % m== 0){tail->next = p->next;free(p);count++;}else{tail = p;p = p->next;}}printf("%d\n",tail->next->no);return 0;
}

  相关解决方案