约瑟夫问题

点击获取原题链接

约瑟夫问题 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 <string.h> #include <stdlib.h> /********数组模拟约瑟夫环*******/ int a[1000000]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n; i++) { a[i]=1; } int count=0;///用count来记录众人数数的功能 int N=n;///记录人数 while(1)///死循环 { for(int i=1; i<=n; i++)///遍历士兵 { if(a[i])///该人还没死 { count++;///数数 if(count%m==0) { a[i]=0;///枪毙 N--;///总人数减少 if(N==1) break; } } } if(N==1)break; } for(int i=1;i<=n;i++) { if(a[i])///判断士兵是否活着 { printf("%d\n",i); } } return 0; } /*************************************************** User name: Result: Accepted Take time: 0ms Take Memory: 104KB Submit time: 2017-03-03 23:23:07 ****************************************************/

方法二：循环链表模拟

#include <bits/stdc++.h> using namespace std; struct node ///循环链表节点 { int data; struct node *next;///指针域 }; struct node *creat(int n)///建立循环链表 { struct node *head,*tail,*p; head=new node ; tail=head; for(int i=1;i<=n;i++) { p=new node; p->data=i; tail->next=p; tail=p; } tail->next=head->next;///循环去掉头结点 free(head); return tail->next; }; int Dell(int m,int n,node *head) { node *p=head; node * q=head->next; int count=1; while(n>1)///只剩下一个人时停止 { count++; if(count%m==0)///这个人被杀 { p->next=q->next; ///跳过被杀 q=p->next; n--; } else { p=p->next; q=q->next; } } return p->data;///只剩下一个人 } int main() { node *head=NULL; head=new node; int n,m; cin>>n>>m; head=creat(n); int t=Dell(m,n,head);///开始 数数 杀人 printf("%d\n",t); } /*************************************************** User name: Result: Accepted Take time: 0ms Take Memory: 160KB Submit time: 2017-03-05 12:04:29 ****************************************************/