●試題五
閱讀下列程序說(shuō)明和C代碼，將應(yīng)填入(n)處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【程序5說(shuō)明】
著名的四色定理指出任何平面區(qū)域圖均可用四種顏色著色，使相鄰區(qū)域著不同的顏色。本程序?qū)o定的區(qū)域圖找出所有可能的不超過(guò)四種顏色的著色方案。
程序中用1~4表示四種顏色。要著色的N個(gè)區(qū)域用0~N-1編號(hào)，區(qū)域相鄰關(guān)系用adj［］［］矩陣表示，矩陣的i行j列的元素為1，表示區(qū)域i與區(qū)域j相鄰；矩陣的i行j列的元素為0，表示區(qū)域i與區(qū)域j不相鄰。數(shù)組color［］用來(lái)存儲(chǔ)著色結(jié)果，color［i］的值為區(qū)域i所著顏色。
【程序5】
#include<stdio.h>
#define N 10
void output(int color［］)/*輸出一種著色方案*/
{int i;
for(i=0;i<N;i++)
printf("%4d"，color［i］);
printf("＼n");
}
int back(int*ip,int color［］)/*回溯*/
{int c=4;
while(c==4){
if(*ip<=0)return 0;
--(*ip);
c= (1) ;
color［*ip］=-1;
}
return c;
}
/*檢查區(qū)域i，對(duì)c種顏色的可用性*/
int color0k(int i,int c,int［］［N］,int color［］}
{int j;
for(j=0;j<i;j++)
if( (2) )
return 0;
return 1;
}
/*為區(qū)域i選一種可著的顏色*/
int select(int i,int c,int adj［］［N］,int color［］)
{int k;
for(k=c;k<=4;k++)
if(colorOK( (3) ))
return k;
return 0;
}
int coloring(int adj［］［N］)/*尋找各種著色方案*/
{int color［N］,i,c,cnt;
for(i=0;i<N;i++)color［i］=-1;
i=c=0;cnt=0;
while (1) {
if((c= (4) )==0){
c=back(&i,color);
if(c==0)return cnt;
}else{ (5) ;i++;
if(i==N){
output(color);
++cnt;
c=back(&i,color);
}else c=0;
}
}
}
void main()
{int adj［N］［N］=
{{0，1，0，1，1，1，1，1，1，1},
{1，0，1，1，0，1，1，1，1，0},
{0，1，0，1，0，1，1，0，1，1},
{1，1，1，0，1，1，0，0，1，1},
{1，0，0，1，0，1，0，0，0，0},
{1，1，1，1，1，0，1，0，0，1},
{1，1，1，0，0，1，0，0，1，0},
{1，1，0，0，0，0，0，0，1，1},
{1，1，1，1，0，0，1，1，0，1},
{1，0，1，1，0，1，0，1，1，0}
}；
printf("共有%d組解.＼n",coloring(adj));
}
2007下半年計(jì)算機(jī)軟件水平考試模擬試題匯總
希望與其他軟考考生進(jìn)行交流？點(diǎn)擊進(jìn)入軟考論壇>>>
進(jìn)入考試吧博客記錄下自己的備考?xì)v程吧
更多信息請(qǐng)?jiān)L問(wèn)：考試吧軟件水平考試欄目
