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

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 18:13
点赞 评论 收藏
分享
Yki_:你要算时间成本呀,研究生两三年,博士三四年,加起来就五六年了,如果你本科去腾讯干五年,多领五年的年薪,加上公司内涨薪,可能到时候十五年总薪资也跟博士差不多
点赞 评论 收藏
分享
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 17:30
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务