計(jì)算機(jī)等級(jí)考試三級(jí)網(wǎng)絡(luò)復(fù)習(xí)資料總錄

難題解釋——出圈題

設(shè)有n個(gè)人圍坐一圈并按順時(shí)針?lè)较驈?到n編號(hào)，從第s個(gè)人開(kāi)始進(jìn)行1到m的報(bào)數(shù)，報(bào)數(shù)到第個(gè)m人，此人出圈，再?gòu)乃�的下一個(gè)人重新開(kāi)始1到m的報(bào)數(shù)，如此進(jìn)行下去直到所有的人都出圈為止。現(xiàn)要求按出圈次序，每10人一組，給出這n個(gè)人的順序表。請(qǐng)考生編制函數(shù)Josegh()實(shí)現(xiàn)此功能并調(diào)用函數(shù)WriteDat()把結(jié)果p輸出到文件OUT.DAT中。

設(shè)n=100,c=1,m=10.
(1)將1到n個(gè)人的序號(hào)存入一維數(shù)組p中；
(2)若第i個(gè)人報(bào)數(shù)后出圈，則將p[i]置于數(shù)組的倒數(shù)第i個(gè)位置上，而原來(lái)第i+1個(gè)至倒數(shù)第i個(gè)元素依次向前移動(dòng)一個(gè)位置；
(3)重復(fù)第(2)步直至圈中只剩下p[1]為止。
部分源程序已給出。
請(qǐng)勿改動(dòng)主函數(shù)main()和輸出數(shù)據(jù)函數(shù)writeDat()的內(nèi)容。 #include
#define N 100
#define S 1
#define M 10

int p[100],n,s,m;
void WriteDat(void);

void Josegh(void)
{

}

void main()
{
m=M;
n=N;
s=S;
Josegh();
WriteDat();
}

void WriteDat(void)
{
int i;
FILE *fp;

fp=fopen("out.dat" ," w" );
for(i=N-1;i>=0;i--){
printf(" %4d" ,p[i]);
fprintf(fp," %4d" ,p[i]);
if(i % 10==0){
printf("\n" );
fprintf(fp, "\n" );
}
}
fclose(fp);
}

解法：

這是南開(kāi)題中的極品，其實(shí)個(gè)人認(rèn)為這個(gè)題目是的要求很低，只是要你把題目中描述的算法用代碼實(shí)現(xiàn)出來(lái)。
題目中已經(jīng)給出了算法過(guò)程，我們下面就看看怎么用代碼實(shí)現(xiàn)：
(1)將1到n個(gè)人的序號(hào)存入一維數(shù)組p中；

這個(gè)我想大家應(yīng)該都沒(méi)有問(wèn)題的了：很簡(jiǎn)單的一句循環(huán)賦值。
for(i=1;i<=n;i++)p[i-1]=i;

(2)若第i個(gè)人報(bào)數(shù)后出圈，則將p[i]置于數(shù)組的倒數(shù)第i個(gè)位置上，而原來(lái)第i+1個(gè)至倒數(shù)第i個(gè)元素依次向前移動(dòng)一個(gè)位置；
(3)重復(fù)第(2)步直至圈中只剩下p[1]為止。

難點(diǎn)就在這后面兩步，首先可以看出是要做一個(gè)循環(huán)，而且循環(huán)的條件是遞減
馬上可以先寫出一個(gè)循環(huán)遞減的框架
for(i=n;n>1;n--){}

接下來(lái)就是該怎么寫循環(huán)體的內(nèi)容了：我們可以發(fā)現(xiàn)，題目的算法過(guò)程2描述的很清楚，具體如下：
s=(s+m-1)%i;首先，求出出圈人的位置，這里用一個(gè)求余是為了實(shí)現(xiàn)圈循環(huán)（也就是將隊(duì)列頭尾相連），這里i是圈中剩余的人數(shù)（除去出圈后的人）。 當(dāng)然，我們稍微注意一下，那就是沒(méi)有第0位的出圈人存在，所以這里如果s=0是不對(duì)的，
其實(shí)這種情況是出圈人是隊(duì)尾的那一個(gè)人，所以這里加上一個(gè)判斷：
if(s==0)s=i;

好了，我們?nèi)〉搅顺鋈θ说奈恢昧耍�那我們就要�?BR>"則將p[i]置于數(shù)組的倒數(shù)第i個(gè)位置上，而原來(lái)第i+1個(gè)至倒數(shù)第i個(gè)元素依次向前移動(dòng)一個(gè)位置"

實(shí)現(xiàn)這一句的算法過(guò)程的代碼，可以看出也是一個(gè)循環(huán)：
w=p[s-1]; 首先，把出圈人的號(hào)碼暫時(shí)放起來(lái)（因?yàn)榇藭r(shí)倒數(shù)第i個(gè)位置還有人占據(jù)，不能替換掉）
接著我們要把倒數(shù)第i個(gè)位置騰空出來(lái)，
而這個(gè)算法的實(shí)現(xiàn)就是“第i+1個(gè)至倒數(shù)第i個(gè)元素依次向前移動(dòng)一個(gè)位置”
明白了這句話的意思后，馬上可以寫出下面的一個(gè)循環(huán)代碼來(lái)實(shí)現(xiàn)
for(j=s;j

最后出圈人占據(jù)倒數(shù)第i個(gè)位置：p[i-1]=w;（注意這里第i個(gè)位置在數(shù)組中下標(biāo)是i-1,因?yàn)閿?shù)組下標(biāo)是0開(kāi)始的，

到這里為止，循環(huán)體也寫完了，整合起來(lái)，就可以得到下面的完整函數(shù)代碼了：

void Josegh(void)
{
int i,j,w; 定義一些用于暫時(shí)存放出圈人和循環(huán)變量。
for(i=1;i<=n;i++) 開(kāi)始初始化循環(huán)賦值。
p[i-1]=i;
for(i=n;i>=2;i--) 循環(huán)體開(kāi)始
{s=(s+m-1)%i; 尋找出圈人
if(s==0)
s=i;
w=p[s-1]; 暫時(shí)安置出圈人
for(j=s;jp[j-1]=p[j];
p[i-1]=w; 重新安置出圈人
}
}