【蓝桥杯选拔赛真题34】C++最大值 第十三届蓝桥杯青少年创意编程大赛C++编程选拔赛真题解析

目录

C/C++最大值

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、程序说明

五、运行结果

六、考点分析

七、推荐资料

---

C/C++最大值

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

一、题目要求

1、编程实现（C++）

给定一个正整数M(1≤M≤5)和一个只包含数字的字符串(5<字符长度≤20)。使用M个乘号插入到字符中，且两个乘号不能相邻，插入后生成一个乘法算式。找出一种使乘法算式数值最大的插入方式，并将结果输出。 (乘号不能放在字符串的首尾位置)如M=2.字符串为123456，插入2个乘号。插入方式有:
1*2*3456=6912，1*23*456=10488，1*234*56=13104，1*2345*6=14070，12*3*456=16416 12*34*56=22848，12*345*6=24840，123*4*56=27552，123*45*6=33210，1234*5*6=37020

2、输入输出

输入描述：第一行输入一个正整数M(1≤M≤5)，表示乘号个数

第二行输入一个只包含数字的字符串(5<字符串长度≤20)，表示要插入M个乘号的字符串。

输出描述：只有一行，输出一个整数，表示最大乘积数值

输入样例：

2
123456

输出样例：

37020

二、算法分析

1. 从给定题目的初步分析可以看出，本题还是有一定的难度
2. 本题应该属于比较典型的动态规划题型，我们在分析的时候可以将插入的乘号进行分段，如要插入k个乘号，就可以把问题看成是k个阶段的决策问题
3. 设f[i][k]表示在前i位数中插入k个乘号所得的最大值，a[j][i]表示从第j位所组成的自然数
4. 用f[i][k]存储阶段k的每一个状态，可以得到对应的状态转移方程：f[i][k] = max(f[i][k],f[j][k-1] * a[j+1][i]);
5. 对应的边界值为：f[j][0] = a[1][j];
6. 就可以得到对应的动态规划程序：
7. for(int k = 1;k <= m;k++)
           for(int i = k + 1;i <= n;i++)
               for(int j = k;j < i;j++)
                   f[i][k] = max(f[i][k],f[j][k-1] * a[j+1][i]);

三、程序编写

#include <iostream>
using namespace std;
long long a[21][21],f[21][21];
long long s;
//返回数字的长度
int getNumDigits(int num) 
{
    int count = 0;   
    if (num == 0) 
	{
        return 1;  // 如果num为0，直接返回1
    }
    while (num > 0) 
	{
        num = num / 10;
        count++;
    }
    return count;
}
int main(void) 
{
	int m,n;
	cin >> m >> s;
	n = getNumDigits(s);
	for(int i = n;i >= 1;i--)
	{
		a[i][i] = s % 10;
		s /= 10;
	}
	
	for(int i = 2;i <= n;i++)
		for(int j = i - 1;j >= 1;j--)
			a[j][i] = a[j][i-1] * 10 + a[i][i];
	
	for(int i = 1;i <= n;i++)//不加乘号的情况
		f[i][0] = a[1][i];
		
	for(int k = 1;k <= m;k++)
		for(int i = k + 1;i <= n;i++)
			for(int j = k;j < i;j++)
				f[i][k] = max(f[i][k],f[j][k-1] * a[j+1][i]);
	cout << f[n][m];
    return 0;
}

四、程序说明

1. 首先需要导入输入输出流头文件
2. 然后是引入std命名空间中的所有成员到当前的程序中，这样在当前的程序中就可以直接使用 std 命名空间中的所有成员，而不需要使用的时候在成员前面加上（std::）前缀
3. 接着声明两个长整型数二维组a存储对应的每一位和f存储中间计算的结果
4. 在声明一个长整型变量s
5. 先声明一个getNumDigits自定义函数用来返回输入整数的位数
6. 接着声明程序的入口，也就是主函数（主函数在一个程序中只允许出现一次）
7. 根据题目要求声明2个整形变量m和n
8. 然后利用输入流对象cin，从键盘读取这2个变量的值
9. 接着利用for循环将s的每一位数字存储到二维数组a的对角线上。注意这里是从最高位到最低位依次存储
10. 然后用一个双层for循环来填充数组a的其余部分
11. 紧接着的for循环用于初始化数组f的第一列（即没有乘号的情况）
12. 接下来的三层嵌套for循环就是我们的动态求解方程，目标是计算所有可能的m次乘法操作后得到的最大乘积
13. 最后利用输出流对象cout，输出计算得到的最大乘积f[n][m]
14. 最后返回0，程序结束

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

五、运行结果

7
You are too young！

六、考点分析

难度级别：难，这题相对而言还是有一定难度的，难在如何设计求解算法，是否会想到使用动态规划来求解，具体主要考查如下：

1. 充分掌握变量、数组的定义和使用
2. 充分掌握动态规划算法的求解步骤，如何确定边界值和状态转移方程
3. 学会输入流对象cin的使用，从键盘读入相应的数据
4. 学会for循环以及嵌套循环的使用，在确定循环次数的时候推荐使用学会
5. 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
6. 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
7. 充分掌握变量定义和使用、分支语句、循环语句和简单算法知识的使用及输入输出的用法

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

七、推荐资料

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