蓝桥杯-基础
蓝桥杯-简单
蓝桥杯-字符串
蓝桥杯-递归
蓝桥杯-堆栈队列链表
蓝桥杯-模拟
蓝桥杯-搜索
蓝桥杯-动态规划
leetcode-数组
leetcode-链表
leetcode-字符串
leetcode-栈与队列
leetcode-排序算法
leetcode-双指针
leetcode-树
leetcode-哈希表
leetcode-图与搜索
leetcode-数学
leetcode-设计
leetcode-动态规划
leetcode-回溯算法
leetcode-贪心
进阶任务
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
个国家可以派遣的人员的最大数量,从0
到a[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
前往答题