出圈問(wèn)題是上級(jí)考試中最難的題之一，可以說(shuō)如果能獨(dú)立解決這個(gè)問(wèn)題那么其他的題自然不在話(huà)下。
傳統(tǒng)的解法使用了一種橋難理解的復(fù)雜算法，在這里我提供一種相對(duì)來(lái)說(shuō)更易理解的算法“環(huán)鏈表模擬法”
void Josegh(void) /*標(biāo)準(zhǔn)答案*/
{int I,j,k,s1,w;
s1=s;
for(I=1;I<=n;I++) p[I-1]=I;
for(I=n;I>=2;I--)
{s1=(s1+m-1)%I; “原題中采用的算法關(guān)鍵”
if (s1==0) s1=I;
w=p[s1-1];
for(j=s1;j<=I-1;j++) p[j-1]=p[j];
p[I-1]=w;}
}
注：題中第一個(gè)for()循環(huán)是先對(duì)數(shù)組p賦初值。在第二個(gè)for()中用i來(lái)控制沒(méi)出圈的
總?cè)藬?shù)，s1=(s1+m-1)%i的作用是找出報(bào)數(shù)后出圈人的下標(biāo)，其中對(duì)i求余的作用是使報(bào)
數(shù)按圈進(jìn)行（即報(bào)到尾后又從頭報(bào)），該算法在很多題目中都用到。由于求余的作用當(dāng)
報(bào)數(shù)正好到最后一個(gè)時(shí)s1為0，故而要進(jìn)行if(s1==0)的判斷。內(nèi)嵌的for()循環(huán)是將出圈
以后的人依次往前移。
環(huán)鏈表模擬法
void Josegh(void)
{ typedef struct p { int n;
struct p *next;} m; /*定義結(jié)構(gòu)體*/
typedef m *link;
m *h,*s,*r; /*定義指針*/
int i,j,a[100]={0};
h=malloc(sizeof(m));
h->n=1;
r=h;
for(i=2;i<=100;i++) /*賦初值*/
{ r=(r->next=malloc(sizeof(m)));
r->n=i;
}
r->next=h;
r=r->next;
for(i=0;i<100;i++)
{ j=1;
while(j<9) /*模擬報(bào)數(shù)*/
{ r=r->next;
j++;}
a[i]=r->next->n;
h=r->next;
r=r->next=h->next;
free(h);
printf("%d\t",a[i]);}
}