欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

递归(七):递归程序填空

程序员文章站 2023-10-18 22:42:58
1. 字母组串(2017年第8届蓝桥杯省赛试题) 由 A,B,C 这3个字母就可以组成许多串。比如:"A","AB","ABC","ABA","AACBB" .... 现在,小明正在思考一个问题:如果每个字母的个数有限定,能组成多少个已知长度的串呢? 他请好朋友来帮忙,很快得到了代码,解决方案超级简 ......

1. 字母组串(2017年第8届蓝桥杯省赛试题)

由 a,b,c 这3个字母就可以组成许多串。
比如:"a","ab","abc","aba","aacbb" ....

现在,小明正在思考一个问题:
如果每个字母的个数有限定,能组成多少个已知长度的串呢?

他请好朋友来帮忙,很快得到了代码,
解决方案超级简单,然而最重要的部分却语焉不详。

请仔细分析源码,填写划线部分缺少的内容。

#include <stdio.h>

// a个a,b个b,c个c 字母,能组成多少个不同的长度为n的串。
int f(int a, int b, int c, int n)
{
      if (a<0 || b<0 || c<0) return 0;
      if (n==0) return 1;
      return ______________________________________ ; // 填空
}

int main()
{
      printf("%d\n", f(1,1,1,2));
      printf("%d\n", f(1,2,3,3));
      return 0;
}

对于上面的测试数据,小明口算的结果应该是:
6
19

分析:为组成长度为n的串,可以先选1个a,再在a-1个a,b个b,c个c 中进行选择组成长度为n-1的串,即递归调用f(a-1,b,c,n-1);也可以先选1个b,再在a个a,b-1个b,c个c 中进行选择组成长度为n-1的串,即递归调用f(a,b-1,c,n-1);还可以先选1个c,再在a个a,b个b,c-1个c 中进行选择组成长度为n-1的串,即递归调用f(a,b,c-1,n-1)。

划线处填写代码为:f(a-1,b,c,n-1)+f(a,b-1,c,n-1)+f(a,b,c-1,n-1)

 

2. 取数位(2017年第8届蓝桥杯省赛试题)

求1个整数的第k位数字有很多种方法。
以下的方法就是一种。

// 求x用10进制表示时的数位长度
int len(int x) {
    if (x<10)  return 1;
    return  len(x/10)+1;
}
// 取x的第k位数字
int  f(int x, int k) {
     if  (len(x)-k==0)  return x%10;
     return _____________________; //填空
}
int main()
{
    int x = 23574;
    printf("%d\n", f(x,3));
    return 0;
}

对于题目中的测试数据,应该打印5。

分析:一个整数x的个位数最容易求得,公式为x%10。一个k位数的第k位就是其个位数。而一个n位数x(n>k)的第k位数就是其高k位数的最后一位,因此可以通过不断舍弃其个位数的方式(x/10)递归求得。

划线处填写代码为:f(x/10,k)

 

3. 抽签(2016年第7届蓝桥杯省赛试题)

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;
}

仔细阅读代码,填写划线部分缺少的内容。

分析:函数void f(int a[], int k, int m, char b[])的四个参数分别表示:a[]-每个国家可以派出的最多的名额,k-第k个国家,m-还剩多少人可以选,b[]-最终组合。

构造时,确定第k个国家(k的初始值为0,表示国家a)可以派出的选手数i(i从0到a[k]),并将国家代号填写到字符串b中,再递归调用确定第k+1个国家的派出选手,此时剩余可派选手数为m-i。

划线处填写代码为:f(a,k+1,m-i,b)