主题:约瑟夫环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) 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;
}