【蓝桥杯选拔赛真题45】C++最大乘积 第十四届蓝桥杯青少年创意编程大赛 算法思维 C++编程选拔赛真题解析

目录

C++最大乘积

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、程序说明

五、运行结果

六、考点分析

七、推荐资料

---

C++最大乘积

第十四届蓝桥杯青少年创意编程大赛C++选拔赛真题

一、题目要求

1、编程实现

小明有N(4≤N≤60)个玻璃球，他想将N个玻璃球拆分成若千份(份数≥2，且每份中的数量互不相等)，从而使拆分后的每份玻璃球数量的乘积最大。请你编写程序帮助小明计算出最大乘积是多少。
例如：N=5，5个玻璃球有2种符合条件的拆分方法：(4,1)、(3,2)；其中，能得到最大乘积的拆分方法为(3,2)，最大乘积为6(6=3*2)。

2、输入输出

输入描述：只有一行，共三个整数，整数之间由一个空格分隔。整数是32位有符号整数。

输出描述：只有一行，一个整数，即输入的第二个整数。

输入样例：

5

输出样例：

6

二、算法分析

1. 从给定题目的初步分析可以看出，题目相对而言比较复杂，有一定的难度
2. 当然这题也可以有多种解题方法，可以采用暴力破解，也可以采用深搜的方式等
3. 小兔子老师这里采用深搜的方式进行实现，具体思路就是采用递归的方式将每一种拆分方法进行求解乘积，然后保留最大的那个
4. 具体如下所示

三、程序编写

#include <iostream>
using namespace std;
int maxMul;
void dfs(int num, int mul, int k) 
{
  	if (num == 0) 
  	{
    	maxMul = max(mul, maxMul);
    	return;
  	}
  	for (int i = k + 1; i <= num; i++) 
	{
    	dfs(num - i, mul * i, i);
  	}
  	return;
}
int main() 
{
	int n;
  	cin >> n;
  	dfs(n, 1, 0);
  	cout << maxMul;
  	return 0;
}

四、程序说明

1. 首先需要导入输入输出流头文件
2. 然后是引入std命名空间中的所有成员到当前的程序中，这样在当前的程序中就可以直接使用 std 命名空间中的所有成员，而不需要使用的时候在成员前面加上（std::）前缀
3. 定义一个全局变量maxMul，用于存储最大乘积
4.  然后，定义一个dfs深搜递归函数，该函数有三个参数：num表示剩余的数字个数，mul表示当前的乘积，k表示当前可以选择的数字的最大值。
5. 在dfs函数中，首先判断如果剩余的数字个数为0，则更新maxMul为当前乘积和maxMul中的最大值，并返回
6. 然后，使用一个循环从k+1到num之间的数字，对每个数字i进行递归调用dfs函数，传入的参数分别为剩余数字个数为num-i，当前乘积为mul*i，当前可选择的数字的最大值为i
7. 接着声明程序的入口，也就是主函数（主函数在一个程序中只允许出现一次）
8. 根据题目要求声明一个整形变量n
9. 然后利用输入流对象cin，从键盘读取这个变量的值
10. 然后调用dfs函数，传入的参数分别为num为n，当前乘积为1，当前选择的数字的最大值为0
11. 最后利用输出流对象cout，输出maxMul
12. 最后返回0，程序结束

 本文作者：小兔子编程 作者首页：https://blog.csdn.net/frank2102

五、运行结果

5

6

六、考点分析

难度级别：难，这题相对而言还是有一定难度的，难在算法的分析设计，具体主要考查如下：

1. 充分掌握变量的定义和使用
2. 学会输入流对象cin的使用，从键盘读入相应的数据
3. 学会for循环的使用，在确定循环次数的时候推荐使用学会
4. 学会while循环的使用，在不确定循环次数的时候推荐使用
5. 学会if条件判断语句的使用，满足一定条件才能执行后面的语句
6. 学会if...else...双分支语句的使用，条件满足执行一种处理，不满足执行另一种处理
7. 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
8. 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
9. 充分掌握变量定义和使用、分支语句、循环语句和深搜算法知识的使用及递归函数的用法

PS：方式方法有多种，小朋友们只要能够达到题目要求即可！

七、推荐资料

• 所有考级比赛学习相关资料合集【推荐收藏】