约瑟夫环(栈和队列)
时间: 1ms 内存:1000M
描述:
题目:n个数字(1,2,3…,n)形成一个圆圈,从数字1开始,每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。
当一个数字删除后,从被删除数字的下一个继续删除第m个数字。
求出在这个圆圈中剩下的最后一个数字。
输入:
输入:
n=9
m=5
输出:
The last one is 8
示例输入:
9 5
示例输出:
8
提示:
参考答案(内存最优[752]):
#include<stdio.h>
int main()
{
int m,n,i,j,s;
scanf("%d %d",&n,&m);
int a[n];
for(i=0;i<n;i++)
a[i]=i+1;
i=-1;
for(j=0;j<n-1;j++)
{
s=0;
while(s<m)
{
i=(i+1)%n;
if(a[i]!=0)
s++;
}
a[i]=0;
}
for(j=0;j<n;j++)
{
if(a[j]!=0)
printf("%d\n",a[j]);
}
return 0;
}
参考答案(时间最优[0]):
#include<stdio.h>
int main()
{
int m,n,i,j,s;
scanf("%d %d",&n,&m);
int a[n];
for(i=0;i<n;i++)
a[i]=i+1;
i=-1;
for(j=0;j<n-1;j++)
{
s=0;
while(s<m)
{
i=(i+1)%n;
if(a[i]!=0)
s++;
}
a[i]=0;
}
for(j=0;j<n;j++)
{
if(a[j]!=0)
printf("%d\n",a[j]);
}
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。