首页 > > 程序设计 > C/C++ >

P1996 约瑟夫问题

2018-06-17 22:36:41来源：未知阅读 ()

题目背景

约瑟夫是一个无聊的人！！！

题目描述

n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号.

输入输出格式

输入格式：

n m

输出格式：

出圈的编号

输入输出样例

输入样例#1：

10 3

输出样例#1：

3 6 9 2 7 1 8 5 10 4

说明

你猜，你猜，你猜猜猜......

猜不着吧，我也不告诉你！！！‘

我确信我的是对的

但是不知道为什么会超时

跟填涂颜色那题一样

明明在自己机子上秒出但是超时？？

 1 #include<cstdio>
 2 #include<cstring>
 3 const int MAXN=10001;
 4 int vis[MAXN];
 5 int flag=0;
 6 int main()
 7 {
 8     int n,m;
 9     scanf("%d%d",&n,&m);
10     int tot=0;
11     int i=1;//有几个人报数 
12     int now=1;// 正在枚举第几个人 
13     while(tot<n)
14     {
15         while(vis[now+1]==0&&i<m&&now<n){i++;now++;}
16         if(i==m)
17         {
18             tot++;
19             i=0;
20             vis[now]=1;
21             printf("%d ",now);
22             continue;
23         }
24         while(vis[now+1]!=0)
25         {now=now++;if(vis[now]==0)i++;}
26         
27         if(now==n)now=0;
28     }
29     return 0;
30 }

TLE

 1 #include<iostream>
 2 using namespace std;
 3 int n,m;
 4 bool out[102];//out[i]:记录点i是否已经出圈,为true则已出圈,之后循环需要跳过i;false则表示还未出圈 
 5 int main()
 6 {
 7     scanf("%d%d",&n,&m);
 8     int cnt=0,now=0,tot=0;//cnt:当前数的数  now:当前轮到第几个人   tot:已出圈人数,用来在达到条件时结束循环(等于总人数n) 
 9     while(tot!=n)
10     {
11         cnt++;now++;
12         if(cnt==m+1)//循环处理,形成一个环 
13           cnt=1;
14         if(now==n+1)//同上 
15           now=1;
16         while(out[now])//当now这个人已经出圈时,应跳过now,直到找到下个未出圈的人(out[now]=false) 
17         {
18             ++now;
19             if(now==n+1)//形成环 
20               now=1;
21         }
22         if(cnt==m)//当前数到m,now出圈,总出圈人数+1 
23           out[now]=1,++tot,printf("%d ",now);
24     }
25     return 0;
26 }