EEPW论坛

这两天学习C语言时遇到这样一道题：

“据说，鲁智深一天中午匆匆来到开封府大相国寺，想蹭顿饭吃，当时大相国寺有99个和尚，只做了99个馒头。智清长老不愿得罪鲁智深，便把他安排在一个特定位置，之后对所有人说： 从我开始报数（围成一圈），第5个人可以吃到馒头（并退下） ,按此方法，所有和尚都吃到了馒头，唯独鲁智深没有吃上。请问他在那个位置？”

对于这道题，我选择用筛数法进行求解：

int main()

{

    int a[101];//定义一个数组，有100个人，但是数组是从【0】开始计数，所以是【101】

int i,j=0,k,count=0;//定义循环的变量 
    int num=99; //共有99个馒头 
    for(i=0; i<101; i++)//对100个人进行清零：表示还没有吃到馒头 
    {
        a[i] = 0;
    }
    
    do
    {
        j++;//依次检查100个人里没有吃到馒头的 
        if(a[j] == 0)//如果没吃到馒头 
        {
            count++;//报数 
            if(count==5)
            {
                a[j] = 1;//第五个人 吃到馒头并退下 
                count = 0;//重新计数 
                num--;//馒头减1 
            }
 
        }
        if(j==100)//如果数到第一百个人之后，重新从第1个人开始 
        {
            j=0;
        }
        
    }while(num>0);//如果馒头还有，就一直循环 
    
    for(k=1; k<101; k++)//查找100个人，谁还没吃到馒头 
    {
        if(a[k] == 0)
        {
            printf("%d\n",k);
        }
    }
    
    return 0;
}

这是一道非常经典的约瑟夫环题目，即令m个人围成一圈（编号为1，2，…m），从编号为1的人开始依次报数，编号为k的人退下，他的下一个人再从1开始报数，数到k的人继续退下，反复几次之后，剩下的那个人就是胜利者。对于这道题，他的时间规模是T(n)=5(n-1),时间复杂度是O(n)。