1995年C试題精解
试题11（1995年试题7）
阅读下列程序说明和C程序，将应填入程序中 (n)
处的字句，写在答卷纸的对应栏内。
【程序说明】
本程序用回溯算法来产生由0或1组成的2m个二进位串，使该串满足以下要求。
视串为首尾相连的环，则由m位二进制数字组成的2m个子序列，每个可能的子序列都互不相同。例如，如果m=3，在串11101000首尾相连构成的环中，由3位二进制数字组成的每个可能的子序列都在环中恰好出现一次，它们依次是111、110、101、010、100、000、001、011，如图所示。
【程序】
#define N 1024
#define M 10
int b[N+M-1];
int equal(int k,int j, int m)
{ int i;
for(i=0;i<m;i++)
if(b[k+1] (1) ) return 0;
return 1;
}
int exchange(int k, int m, int v)
{ while(b[k+m-1] == v)
{ b[k+m-1] = !v; (2) ;}
(3) =v; return k;
}
init(int v)
{
int k;
for(k=0;k<N+M-1;k++) b[k] = v;
}
main()
{ int m,v,k,n,j;
printf("Enter m(1<m<10),v(v=0,v=1)\n");
scanf("%d%d",&m,&v);
n=0x01<<m; init(!v); k=0;
while( (4) < n)
for(j=0;j<k;j++)
if(equal(k,j,m))
{ k=exchange(k,m,v);
j= (5) ;
}
for(k=0;k<n;k++)
printf("%d\n",b[k]);
}
[解析]
本程序比较短，但处处都有填空，难度比较大，着重考查考生对试探回溯算法的掌握。
程序的功能是用回溯算法来产生由0或1组成的2m个二进制字串，所以主程序首先输入m和v，其中m是一个二进制字串的位数，v为0或1。由函数init可知，在主程序中先将要求的二进制字串初始化为!v，从而v只能为0或1，v为0表示将二进制字串初始化为1，第1个m位二进制字串为m位1；v为1表示将要求的二进制字串初始化为0，第1个m位二进制字串为m位0。接着程序通过移位运算使n为2m（其实就是一个乘幂运算，但用移位速度要快得多），n是要填写的位数，即要填写的二进制字串的元素的个数；置k为0，k为最新填写的m位二进制字串在b[
]（b[
]为所求的二进制字串）中的开始下标。在初始化时，自b[0]开始，已填写了一个m位的二进制字串，其值为!v。k+1也可看作已在b[
]中正确填写的二进制数的个数，然后是一个试探求解的循环。在已有k+1个二进制数满足要求，且k+1<n的情况下循环。一般地，试探循环应包括以下工作：
(1)增1。
(2)在b[k+m-1]处预填入试探的值（此处工作已由循环之前的函数完成，将其置为!v），表示一个新的m位二进制数字已填入。其高m-1位是前一个m位二进制数的低m-1位。
(3)检查新的m位二进制数是否与前面已经填写的k个m位二进制数相等。如都不相等，本次试探完成，继续下一次试探；如有相等的，就得改变最新填入得二进制数字的值，改变后，需重新检查。若仍不符合要求，则需要回溯，改变上一次试探的二进制数字的值，若仍不符合要求，则继续回溯，直至符合要求或无解。
在新一轮试探循环开始时，已经有k+1个正确的m位二进制字串，而本次循环的目的是测试第k+2个m位二进制字串是否符合要求，即与前k+1个m位二进制字串是否不相等。如初始循环时k=0，则已有一个正确的m位二进制数字（m位全是!v），进入循环是测试从b[1]开始的第2个m位二进制数字（m位也全是!v）与第1个m位二进制数字是否相等。所以while后的条件表达式为++k<n，即天空（4）的答案为"++k"。
for循环的功能是检查第k+1（因为在while条件表达式中k值已加1）个m位二进制数字串与前k个m位二进制字串是否相等。它首先调用函数equal判断第k个m位二进制字串是否与第j个m位二进制字串相等。函数equal比较两个m位二进制字串是否相等，采用的是逐位比较的方法，依次比较与b[k+i]与b[j+i]（0<=i<=m-1），若相等则继续比较下一位，直至最后一位仍相等，则这两个二进制字串相等，返回1；否则，两个二进制字串肯定不相等，不用再进行下面的比较，直接返回0即可。所以填空（1）的答案为"!=b[j+i]"。若equal函数返回1，即两个二进制字串相等，则说明这一步试探失败，此时调用exchange函数进行更改，包括可能的回溯，并返回更改（回溯）后的k值。更改（回溯）后，又要从第1个m位二进制字串开始检查第k+1个m位二进制字串是否与前面k个m位二进制字串的某个相等，即要让for循环重新开始（j=0）。因为for循环执行结束时，要先执行表达式j++，为了使下次循环重新开始时执行，即执行j++后，j的值是0，填空（5）处应置为-1。所以填空（5）的答案为"-1"。
函数exchange的功能是第1次试探失败后对b[k+m-1]（b[k+m-1]为第k+1个m位二进制的最后一位）的值进行更改（包括回溯）。首先判断b[k+m-1]的值，若为v则肯定b[k+m-1]的值已经更改过了，必须进行回溯，此时应先恢复b[k+m-1]的值为!v，然后k值减1。继续进行判断，若前一位的值仍为v，则继续回溯，直至其值不等于v为止才停止回溯，然后将其值改为v，并返回更改后的k值。若为!v则还没有更改过，将其值变为v后返回。所以填空（2）的答案是"k--"，或其他使k减1的C代码；填空（3）的答案是"b[k+m-1]"。
最后将求得得二进制字串打印。
[答案]
（1）!=b[j+1]
（2）k--或--k或k=k-1或k-=1
（3）b[k+m-1]
（4）++k或k=k+1或k+=1
（5）-1
|
