2017年全國計算機四級考試出圈問題的鏈表解法（經(jīng)典之作）

    出圈問題是上級考試中最難的題之一，可以說如果能獨立解決這個問題那么其他的題自然不在話下。
    傳統(tǒng)的解法使用了一種橋難理解的復(fù)雜算法，在這里我提供一種相對來說更易理解的算法“環(huán)鏈表模擬法”
    void Josegh(void) /*標準答案*/
    {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;}
    }
    注：題中第一個for()循環(huán)是先對數(shù)組p賦初值。在第二個for()中用i來控制沒出圈的
    總?cè)藬?shù)，s1=(s1+m-1)%i的作用是找出報數(shù)后出圈人的下標，其中對i求余的作用是使報
    數(shù)按圈進行（即報到尾后又從頭報），該算法在很多題目中都用到。由于求余的作用當
    報數(shù)正好到最后一個時s1為0，故而要進行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) /*模擬報數(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]);}
    }