回 帖 发 新 帖 刷新版面

主题:约瑟夫环2

原题:
1) 2k个人坐成一个圈,前k个人为good guy,后k个人为bad guy.
2) 第一个人从1开始数,后面的依次跟着数。
3  某人数到m则要被处死,后一个人重新从1开始数。
4) 0<k<14
5)求最小的m,m的值使得出现第一个good guy被处死时全部bad guy已经全部被处死。

我已经设计出一个算法,但k>=10时,要耗费大量的时间,效率太低。希望各位高手能指点一下,提高程序的效率。
我的程序:

#include<stdio.h>
void main()
{
    long  min_m(int k);//求最小m
    int k;
    long m;
    scanf("%d",&k);
    while(k!=0)
    {
        m=min_m(k);
        printf("%ld\n",m);
        scanf("%d",&k);
    }
}

long min_m(int k)
{
    int people[28];//数组元素值为1时,表示该人未被处死。
    long  count;   //表示当前数到那一个数
    int death_people;//表示当前应处死的人的号码
    int people_left;//当前有多少人未被处死
    int i;//循环变量
    int success=0;//表示已经成功处死了多少个bad guy
    int j;//循环变量
    long m;
    
         m=k+1;
    while(success!=k)//
    {
        //初始化操作
        people_left=2*k;
        count=0;
        i=0;
        success=0;
                  for(j=0;j<=2*k-1;j++)
          people[j]=1;
        //开始处死人
        while(people_left>k)
        {
            if(people[i]==1)
            {
                (count==m)?(count=1):(count++);
                if(count==m)
                {
                    death_people=i;
                    if(death_people<=k-1)
                        break;
                    else success++;
                    people_left--;
                    people[i]=0;
                }
            }
            (i==2*k-1)?(i=0):(i++);
        }
        m++;       
    }
    return m-1;
}

回复列表 (共1个回复)

沙发

老你程序不够简练

我来回复

您尚未登录,请登录后再回复。点此登录或注册