参考资料
练习题 icon lost
交流讨论
笔记
img lost

X星球要派出一个5人组成的观察团前往W星。
其中:
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
….

那么最终派往W星的观察团会有多少种国别的不同组合呢?

下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为:
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
….
(以下省略,总共101行)

给出代码,请你填空:

#include <stdio.h>

#define N 6
#define M 5
#define BUF 1024

void f(int a[], int k, int m, char b[])
{
    int i,j;

    if(k==N){ 
        b[M] = 0;
        if(m==0) printf("%s\n",b);
        return;
    }

    for(i=0; i<=a[k]; i++){
        for(j=0; j<i; j++) b[M-m+j] = k+'A';
        ________________;  //填空
    }
}
int main()
{   
    int  a[N] = {4,2,2,1,1,3};
    char b[BUF];
    f(a,0,M,b);
    return 0;
}

思路:

很少做这种填空的,但是递归的话,会有遵循一定的技巧
可以看到递归的首次调用:

f(a,0,M,b);

a, b数组肯定是不变的参数了,关键是如何确定中间的参数

通过题意理解,中间的参数应该是:

/*
function : 由第k~N个国家,派遣m个人组成队伍
param k  : 第k个国家派遣人员
param m  : 还有m个空位
*/
void f(int a[], int k, int m, char b[])

关键是看递归中是如何实现的:

k的判断:

if(k==N)

终止条件是k==N,那么应该是k逐渐递增的,这也符合逻辑:各个国家按顺序,派遣人员,逐渐填满下标,所以大概率是填:k+1

m的判断:

 for(i=0; i<=a[k]; i++){
        for(j=0; j<i; j++) b[M-m+j] = k+'A';
        ______________________;  //填空位置
    }
  • 观察这个循环,a[k]是第k个国家可以派遣的人员的最大数量,从0a[k]说明是在穷举第k个国家派出人员的情况
  • 而内循环则是:第k个国家派遣了i人,循环填掉i个位置(m越少,M-m越大,空位起始的下标逐渐靠后,也是合理的)

那么递归就很清晰了:
k个国家出了i个人,剩下m-i个空位,留给k+1 ~ N个国家,于是m大概率填 m-i,因为循环结束,i==j,填m-j也可以

答案:

f(a, k+1, m-i, b);

完整代码

#include <stdio.h>

#define N 6
#define M 5
#define BUF 1024

void f(int a[], int k, int m, char b[])
{
    int i,j;

    if(k==N){ 
        b[M] = 0;
        if(m==0) printf("%s\n",b);
        return;
    }

    for(i=0; i<=a[k]; i++){
        for(j=0; j<i; j++) b[M-m+j] = k+'A';
        f(a, k+1, m-i, b);  //填空位置
    }
}
int main()
{   
    int  a[N] = {4,2,2,1,1,3};
    char b[BUF];
    f(a,0,M,b);
    return 0;
}
资料来源 蓝桥杯:抽签(代码填空题,递归搜索)
博客作者 weixin_44176696
前往答题
我的笔记