8-2-17.c

2005软件工程师考试下午编程题源代码

/*中国系统分析员顾问团，http://www.csai.cn*/
/*程序员下午考试指南书籍源码*/

#include <stdio.h>
#define N 12
int b[N+1];
int pos;
int a[9]; /*用于存储方格所填入的整数　*/
checkMatrix[][3] = {{-1},{0,-1},{1,-1},{0,-1},{1,3,-1},{2,4,-1},{3,-1},{4,6,-1},{5,7,-1}};

void write(int a[]){
int i, j;
for ( i = 0; i < 3; i++) {
for ( j = 0; j < 3; j++) printf("%3d",a[3*i+j]);
printf("\n");
}
}

int isPrime(int m){
int i;
if (m == 2) return 1;
if (m == 1 || m % 2 == 0) return 0;
for (i = 3; i * i <= m; ) {
if (m % i == 0) return 0;
i += 2;
}
return 1;
}

int selectNum(int start){
int j;
for (j = start; j <= N; j++)
if (b[j]) return j;
return 0;
}

int check(){/*检查填入pos位置的整数是否合理*/
int i, j;
for (i = 0; (j = checkMatrix[pos][i]) >= 0; i++)
if (!isPrime(a[pos] + a[j]))  return 0;
return 1 ;
}

extend(){/*为下一方格找一个尚未使用过的整数*/
a[++pos] = selectNum(1); b[a[pos]] = 0; 
}

void change() { /*为当前方格找下一个尚未使用过的整数。（找不到回溯）*/
int j;
while (pos >= 0 && (j = selectNum(a[pos] + 1)) == 0) b[a[pos--]] = 1 ;
if (pos < 0) return;
b[a[pos]] = 1; a[pos] = j; b[j] = 0;
}

find(){
int ok = 1;
pos = 0; a[pos] = 1; b[a[pos]] = 0;
do {
if (ok)
if (pos == 8) {
write(a);
change();
}
else extend();
else change();
ok = check(pos);
} while (pos>=0);
}

main(){ 
int i;
for (i = 1;i <= N; i++) b[i] = 1;
find();
}