2017年蓝桥杯软件类省赛C++大学A组第5题“字母组串”。一道代码填空题，据说这是传统的送分题，一起来看看是怎么送分的。

* 本文内容由罗勇军老师提供。

01

题目描述

由 A,B,C 这3个字母就可以组成许多串。比如：“A”,“AB”,“ABC”,“ABA”,“AACBB” …

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

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

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

# include<stdio.h>

// a个A，b个B，c个C 字母，能组成多少个不同的长度为n的串。

intf( inta, intb, intc, intn)

{

if(a< 0|| b< 0|| c< 0) return0;

if(n== 0) return1;

return______________________________________ ; // 填空

}

展开全文

intmain

{

printf( "%d\n", f( 1, 1, 1, 2));

printf( "%d\n", f( 1, 2, 3, 3));

return0;

}

对于上面的测试数据，小明口算的结果应该是：

6

19

注意：只填写划线部分缺少的代码，不要提交任何多余内容或说明性文字。

02

DP填空

1.C++代码

一个排列组合问题，题目要求用递归实现。答案如下：

returnf(a - 1, b, c, n - 1) + f(a, b - 1, c, n - 1) + f(a, b, c - 1, n - 1);;

2.Java代码

2017蓝桥杯Java类的第5题也是“字母组串”，这里附上答案。

publicclass_05字母组串 {

// a个A，b个B，c个C 字母，能组成多少个不同的长度为n的串。

staticintf( inta, intb, intc, intn) {

if(a < 0|| b < 0|| c < 0) return0;

if(n == 0) return1;

returnf(a - 1, b, c, n - 1) + f(a, b - 1, c, n - 1) + f(a, b, c - 1, n - 1); //填空

}

publicstaticvoidmain(String[] args){

System.out.println(f( 1, 1, 1, 2));

System.out.println(f( 1, 2, 3, 3));

}

}

03

母函数

对于排列组合问题，经典的解法是母函数。用母函数处理组合问题，较为直接。

参考本篇参考书籍 《算法竞赛入门到进阶》173页“指数型母函数”，书上的例题 hdu 1521 和这题“字母组串”几乎一样。

下面图片为所涉及到的书中内容贴图：

04

参考书籍

《算法竞赛入门到进阶》

ISBN：978-7-302-52915-6

罗勇军 郭卫斌 编著

定价：59.80元

05

精彩文章回顾

从火种到能源，华为做AI的逻辑链

华为 AI，建造中的全景图

逻辑回归的MATLAB实践｜附代码

Python爬虫实例：采集微博博文｜附视频

MySQL利用E-R模型的数据库概念设计｜附视频

HTML5 实现黑白棋游戏 附代码

利用微信小程序实现活动报名登记 | 附代码

使用Flutter小部件跨平台开发移动端App组件 | 附代码

电脑病毒木马的清除和防范方法 | 附视频

教你用Python做在线人脸 检测

一篇文章读懂：Spark运行模式

有监督机器学习——K近邻算法解决二分类问题｜附代 码

无监督机器学习——K均值算法解决病毒聚类问题｜附代 码

无监督机器学习——K均值算法实现简单聚类｜附代码

实战Spring Boot | 天气预报系统的开发

从火种到能源，华为做AI的逻辑链

华为 AI，建造中的全景图

逻辑回归的MATLAB实践｜附代码

Python爬虫实例：采集微博博文｜附视频

MySQL利用E-R模型的数据库概念设计｜附视频