递归(七):递归程序填空
2019-08-16 07:45:44来源:博客园 阅读 ()
递归(七):递归程序填空
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)
原文链接:https://www.cnblogs.com/cs-whut/p/11144049.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C语言程序结构 2020-05-31
- ftp客户端封装 2020-05-10
- C代做 C++代做 C++编程代做 C++程序代做 2020-04-29
- 测量C++程序运行时间 2020-04-17
- DSA_07:递归算法 2020-03-30
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash