点击获取原题链接
约瑟夫问题Time Limit: 1000MS Memory Limit: 65536KBPRoblem Descriptionn个人想玩残酷的死亡游戏，游戏规则如下：n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。请输出最后一个人的编号。Input输入n和m值。Output输出胜利者的编号。Example Input5 3Example Output4Hint第一轮：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: AcceptedTake time: 0msTake Memory: 104KBSubmit 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: AcceptedTake time: 0msTake Memory: 160KBSubmit time: 2017-03-05 12:04:29****************************************************/新闻热点
疑难解答
