约瑟夫环(栈和队列)

约瑟夫环(栈和队列)

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞