2746-约瑟夫问题-模拟(但是可以优化)

方法

主流两种方法,像这种数据量n和m比较小,则直接模拟

其次是数学推导出规律《具体数学》一书,第一章有推导

其实,这个是约瑟夫问题,我们还是得知道方法二,也就是数学的
想想,要是不会,那时候约瑟夫在故事中就已经over了。。。

方法一,直接模拟

思想来源于,数据结构一书中,学循环队列的时候,取模

#include<stdio.h>
#include<string.h>

int main()
{
    int array[301]={0};//表示数字在

    int n,m;

    while((~scanf("%d%d",&n,&m))&&(0!=n)&&(0!=m))
    {
        memset(array,0,sizeof(array));
        int count=0;//表示数数字到几号了 
        int sum=0;
        int i=1;//当前序号 
        while(1)
        {


            //判断有没有被筛 
            if(0==array[i])//没有被筛掉了 
            {
                ++count; //数数字 

            }

            //判断需不需要筛掉
            if(m==count)
            {
                array[i]=1;
                ++sum;//筛掉了一个 
                count=0;//继续下一次 

            }

            if(sum==(n-1)) 
            {

                break;
            }

            ++i;

            if((n+1)==i)
            {
                i=1;            
            }
        }


        for(i=1;i<=n;++i)
        {
            if(!array[i])
            {
                printf("%d\n",i);
            }
        }

    } 


    return 0;
}

方法2

全部评论

相关推荐

11-09 11:01
济南大学 Java
Java抽象带篮子:外卖项目真得美化一下,可以看看我的详细的外卖话术帖子
点赞 评论 收藏
分享
ArisRobert:统一解释一下,第4点的意思是,公司按需通知员工,没被通知到的员工是没法去上班的,所以只要没被通知到,就自动离职。就是一种比较抽象的裁员。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务