2746:约瑟夫问题
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
- 输入
- 每行是用空格分开的两个整数，第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是：
0 0
- 输出
- 对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号
- 样例输入
6 2
12 4
8 3
0 0- 样例输出
5
1
7
代码：#include<iostream>
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
using namespace std; int main()
{
int m,n;
while(true)
{
int i,j;
int count=;
cin>>m>>n;
if(m==&&n==)//m,n同时为0的时候退出
break;
char *str;
if((str=(char *)malloc((m+)*sizeof(char)))==NULL)//判断是否能够分配空间
{
printf("failed!\n");
exit();
}
memset(str,'',(m+)*sizeof(char));//分配空间，赋初值
int last=m,ptr=;//last为计数当前还有多少个没报数的猴子，ptr为移动指针，指向剩下的猴子
while(last>)
{
ptr++;
if(str[ptr]=='')//如果还没报数，则处理
{
count++;
if(count==n)//计数到了出列的数字
{
count=;//重新计数
str[ptr]='';//数组置零
last--;//猴子的数目减少
}
}
if(ptr==m)//指针移动到了最后一个猴子
{
ptr=;
}
}
for(int k=;k<=m;k++)
{
if(str[k]=='')
{
cout<<k<<endl;
break;
}
}
free(str);
str=NULL;
}
return ;
}#include<iostream>
#include <stdio.h>
#include<string.h>
#include <stdlib.h>
using namespace std;
int main()
{
int m,n;
while(cin>>m>>n)
{
if(m==&&n==)
{
break;
}
char *str;
int last,ptr,count;
if ((str=(char *) calloc (m + , sizeof(char))) == NULL) //这里判断需小心，是数组的长度
{
printf("空间分配失败!\n");
exit(-);
}
memset(str,'',(m+)*sizeof(char));
count=ptr=;
last=m;
while(last>)
{
ptr++;
if(str[ptr]=='')
{
count++; if(count==n)
{
count=;
str[ptr]='';
last--;
}
}
if(ptr==m)
{
ptr=;
}
}
for(ptr=;ptr<=m;ptr++)
{
if(str[ptr]=='')
{
cout<<ptr<<endl;
break;
}
}
free(str);
str=NULL;
}
return ;
}#include<iostream>
#include <stdio.h>
#include<string.h>
#include <stdlib.h>
using namespace std;
int main()
{
int m,n;
while(cin>>m>>n)
{
if(m==&&n==)
{
break;
}
/*
char *str;
int last,ptr,count;
if ((str=(char *) calloc (m + 1, sizeof(char))) == NULL) //这里判断需小心，是数组的长度
{
printf("空间分配失败!\n");
exit(-1);
}
memset(str,'1',(m+1)*sizeof(char));
count=ptr=0;
last=m;
while(last>1)
{
ptr++;
if(str[ptr]=='1')
{
count++; if(count==n)
{
count=0;
str[ptr]='0';
last--;
}
}
if(ptr==m)
{
ptr=0;
}
}
for(ptr=1;ptr<=m;ptr++)
{
if(str[ptr]=='1')
{
cout<<ptr<<endl;
break;
}
}
free(str);
str=NULL;*/
int s=;
for(int i=;i<=m;i++)
{ s=(s+n)%i;
}
cout<<s+<<endl;
}
return ;
}