发布时间 : 星期二 文章C语言典例解析更新完毕开始阅读
了记录在每趟排序中是否出现交换，函数中使用了变量b来记录。当b为非0值时，表示出现过交换。当b为0时，表示在该趟排序中未出现交换。因此，（5）空的答案b=0或给b赋一个非0的整数。
16.递归实例1
递归函数sum（int a[ ],int n）的返回值是数组a[ ]的前n个元素之和。 〔函数〕
int sum（int a[ ],int n） {
if（n>0） return ___（1）___ ; else ___（2）___ ; } 答案：
（1）sum（a,n-1）+a[n-1] 或sum（a+1,n-1）+a[0] （2）return 0
分析：
递归函数sum的功能是求计算机数组a[ ]的前n个元素之和，是一种简单的递归。在平时的编程中，对于数组中元素求和都是采用循环来累加a[0]、a[1]、?、a[n-1]这n个元素。但是，在该题中却是以递归方法来实现。那么，我们如何来解答该题呢？
在这类递归程序中，首先要考虑递归调用的结束条件，若没有结束条件，将会由于不断调用函数自身而导致系统内存不够和程序运行失败。经分析，在该题中递归调用结束条件应是进行求和计算的元素个数为0，即n<=0。 根据函数中的if语句的条件为n>0，（1）空应填继续递归调用语句，（2）空应填递归调用结束，直接返回的某一具体值。由于是当待求和数组a中的元素个数为0时结束递归调用，这样就很容易知道（2）空应填return 0。（1）空的填写则可根据前面所讲的方法，需想办法将累加的范围缩小。若能计算出a[0]+a[1]+...+a[n-2]，则计算a[0]+a[1]+a[2]+...+a[n-1]时，只需要在前面计算的基础上再加上a[n-1]即可。这样，就将原来的n个元素求和转化为n-1个元素求和后再加上a[n-1]。而计算a[0]+a[1]+...+a[n-2]这n-1个元素，则可调用递归函数自身sum（a,n-1）来实现。综上所述，（2）空应填sum（a,n-1）+a[n-1]。前面在考虑缩小范围时，采用前n-1个数组元素相加，再加上最后一个元素。若采用后n-1个元素相加，再加上第一个元素，则也能达到同样的结果。因此，（1）空还有一个等价答案为sum（a+1,n-1）+a[0]。
17.递归实例2
递归函数invert（int a[ ],int k）将指定数组中的前k个元素逆置。 〔函数〕
void invert（int a[ ],int k） { int t;
if（ （1） ）
{ invert（ （2） ）; t=a[0];
a[0]=a[k-1]; a[k-1]=t; } } 答案：
（1）k>=2 或k>0或k>=1 （2）a+1,k-2
分析：
递归函数invert（int a[ ],int k）将指定数组中的前k个元素逆置，为了实现a数组中元素逆置，需要将a[0]与a[k-1]交换，将a[1]与a[k-2]交换，将a[2]与a[k-3] 交换，直到最后只剩下一个元素（k为奇数时）或所有元素都交换后（k为偶数时），a数组中所有元素都已经实现了逆置。
综上所述，在此函数中，可将数组元素分为a[1]、a[2]、a[3]?a[k-2]和a[0]与a[k-1]两部分，这样只要a[1]、a[2]、a[3]?a[k-2]进行逆置后，再对a[0]与a[k-1]两元素进行交换，就能实现对数组a中所有k个元素进行逆置。而a[1]、a[2]、a[3]?a[k-2]的逆置可通过递归调用的方法实现。
从上面分析和递归函数invert可以看出，每次调用都实现了a数组中一对元素交换，即实现了a[0]与a[k-1]交换。因此，本函数的递归调用结束条件应为只剩下一个元素或所有元素都交换完毕，即当k<2时递归调用结束。而（1）空需填写的为继续进行递归调用的条件，因此（1）空的正确答案为k>1。当只剩下一个元素时，即k为1时，再调用递归函数invert的功能是实现了剩下的最后一个元素自身交换，不影响a数组中其他元素的逆置，因此，k>0或k>=1也是（1）空的正确答案。 （2）空则需填写递归调用的参数，第一个参数为要进行元素逆置的数组首地址（数组名），在本函数中，需通过递归调用进行逆置元素为a[1]、a[2]、a[3]?a[k-2]，这些元素的首地址为a[1]的首地址，即a+1。第二个参数为需通过递归调用累计逆置元素个数，从a[1]?a[k-2]共有k-2个元素，因此递归调用的第二个参数为k-2。从而得出，（2）空的正确答案为a+1，k-2。
18.递归实例3
本程序采用递归算法将一个自然数分解成不多于m个整数之和。设构成和数n的各个整数取于数组d，d中的整数互不相等且由大到小存储。
例如，数组d中存储以下整数：d[ ]={100,81,64,49,36,25,16,9,4,1}，则有：
n m 程序运行后的输出结果 100 2 100=100 13 2 13=9+4
14 2 No answer（9+4+1 超过2个） 71 5 71=49+9+9+4 （表示可重复取数）
函数find（）的形参c表示d中可取的整数个数；形参pd指向能成为和数的整数的存放位置。 〔程序〕
# include
int find （int n,int m,int *d,int c, int *pd） { int r;
if（n==0） return 0; /* 已分解完成 */
if（m==0 ││ c==0 ） return -1; /* 不可以分解 */ if（___（1）___ ） return find（n,m,d+1,c-1,pd）; else { *pd=d;
r=find（___（2）___ , d, c , ___（3）___ ）; /* 继续对剩余数作分解 */ if（r>=0） return ___（4）___;
return find（n , m , ___（5）___ , pd ）; } }
void main（） {
int n,m,k,i,p[N],*pptr=p;
int d[ ]={ 100,81,64,49,36,25,16,9,4,1 };
printf（\）; scanf（\）; k=find（n, m , d ,10 ,pptr ）;
if（k<=0） printf（\）; else { printf（\）; for（i=1; i printf（\）; printf（\）; } } 答案： （1）*d>n （2）n-*d,m-1 （3）pd+1 （4）r+1 （5）d+1,c-1 分析： 递归函数find的功能是将自然数n分解成不多于m个整数之和，若分解成功则返回实际构成和数的整数个数，否则返回-1。构成和数的各个整数存储在数组d（共c个数组元素）中，d中的所有元素互不相等且按递减排列。pd指向能成为和数的整数的存放位置。该递归算法属于较复杂的递归算法，但考虑问题的思路与前几题相类似。递归结束也有两种情况：一种情况是找到解之后就结束，即待分解的自然数已经分解结束，其值为0。另一种情况是不能分解为所需个数的自然数，即n分解至规定的m个整数之后，还有剩余值。或者d数组中的数都已试过了，没有符合能进一步分解的数。都应该认为不可以分解而结束，而关于结束条件和结束返回值在程序中都已经给出。对于d数组中的当前需处理的元素都有两种可能情况： 第一种情况是当前元素的值大于n，则跳过该数，将继续处理d数组后面剩余的c-1个数。 第二种情况是当前元素的值小于等于n，则需处理两种情况：其一将该数作为构成n的一个整数因子，然后对n减去该数之后的剩余数继续下一次分解。若继续分解成功，则返回值为构成剩余数的整数个数加1。其二为该数不作为构成n的整数的情况，则只需跳过该数继续处理剩余的数。综上所述，该递归算法可描述为： 1. 若分解完成，则返回分解成功的值； 2. 若不可以分解，则返回分解失败的值； 3. 若当前处理的用于构成和数的数组元素值大于n，则用数组中剩余的数组元素值继续分解n；否则： （1）把当前数作为构成n的一个因子； （2）继续对剩余数作分解； （3）若分解成功，则返回，剩余数分解成的整数个数+1 ； （4）不把数组当前元素值作为构成n的一个因子，用数组中剩余的数组元素值继续分解n。 根据上述递归算法描述，结合（1）空后面语句return find（n,m,d+1,c-1,pd）的功能（即跳过d数组的当前元素，用数组d中剩余的数组元素值继续分解n），可知（1）空正确答案为*d>n。（2）空与（3）空是继续对剩余数作分解的递归函数的参数，（2）对应的参数为2个，即n与m。由于是对除去当前元素后的剩余数作分解，因此，（2）空的第一个参数为n-*d，即当前的n减去d数组中当前的元素*d。 由于d数组当前元素作为n分解的一个因子，继续分解的因子个数应为m-1，即第二个参数应为m-1。所以，（2）空的正确答案为n-*d,m-1。（3）空对应的参数为存放n因子的指针，由于d数组中当前的元素作为n的一个因子，并存入数组，因此，相应的指针应向后移一个位置。即（3）空的正确答案为pd+1 ，由于后面还要用到该指针，pd++、++pd等都不正确。根据前面的分析，很容易就得出（4）空的正确答案为r+1或++r。（5）空所在的递归函数find实现的功能为跳过数组d的当前元素，用数组中剩余的数组元素值继续分解n。因此，d数组的指针应向后移一个位置，元素个数也应减少1。即（5）空的正确答案为d+1,c-1。 19.回溯算法