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

news/2024/2/28 7:57:05

目录

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:方式方法有多种,小朋友们只要能够达到题目要求即可!

七、推荐资料

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

http://www.ppmy.cn/news/1350412.html

相关文章

【GameFramework框架内置模块】1、全局配置(Config)

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址 大家好&#xff0c;我是佛系工程师☆恬静的小魔龙☆&#xff0c;不定时更新Unity开发技巧&#xff0c;觉得有用记得一键三连哦。 一、前言 【GameFramework框架】系列教程目录&#xff1a; https://blog.csdn.net/q7…

第9讲用户信息修改实现

用户信息修改实现 后端修改用户昵称&#xff1a; /*** 更新用户昵称* param wxUserInfo* param token* return*/ RequestMapping("/updateNickName") public R updateNickName(RequestBody WxUserInfo wxUserInfo,RequestHeader String token){if(StringUtil.isNot…

vue3学习——集成sass

安装 pnpm i sass sass-loader -D在vite.config.ts文件配置: export default defineConfig({css: {preprocessorOptions: {scss: {javascriptEnabled: true,additionalData: import "./src/styles/variable.scss";,},},},} }创建三个文件 src/styles/index.scss //…

openkylin(Debian系)安装nginx及安装前需要的准备

前言 现在很多linux系统都可以使用高级包管理工具安装软件了&#xff0c;但是在像是 openkylin这些新系统中&#xff0c;好多软件包虽然有&#xff0c;但是因为其依赖的包还没有做好&#xff0c;所 以安装会提示你一大堆依赖错误。所以还是要自己来编译安装咯。安装前准备&…

【QT+QGIS跨平台编译】之三十六:【RasterLite2+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、RasterLite2介绍二、文件下载三、文件分析四、pro文件五、编译实践一、RasterLite2介绍 RasterLite2是一个开源的轻量级栅格数据库,可以用于存储和管理各种类型的栅格数据,包括卫星遥感图像、数字高程模型等。 与传统的GIS数据存储方式不同,RasterLite2采用基…

[ubuntu]split命令分割文件

split 命令 $ split --help Usage: split [OPTION]... [INPUT [PREFIX]] Output fixed-size pieces of INPUT to PREFIXaa, PREFIXab, ...; default size is 1000 lines, and default PREFIX is x. With no INPUT, or when INPUT is -, read standard input.Mandatory argume…

Java集合补充

List和array的转换 Object[] arraylist.toArray(); Integer[] array list.toArray(new Integer[3]); 注意&#xff0c;这里的3是指创建array的大小&#xff0c;当数组小的话&#xff0c;会自动扩容为刚好的大小&#xff0c;若是大了&#xff0c;剩下的空间会变为null。可以使…

STM32自学☞PWM驱动舵机(按键控制)

PWM.c文件 #include "stm32f10x.h" /*初始化函数*/ void PWM_Init(void){ /*开启时钟*/ RCC_APB1PeriphClockCmd(RCC_APB1Periph_TIM2, ENABLE); //开启TIM2的时钟 RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOA, ENABLE); //开启GPIOA的时钟 /*GPIO初始化*/ G…

Redis的删除策略

在Redis中的数据删除策略有三种&#xff1a;定时删除、惰性删除、定期删除 定时删除 当key设置有过期时间&#xff0c;且过期时间到达时&#xff0c;立即执行key的删除操作 优点&#xff1a;节约内存&#xff0c;到时就删除&#xff0c;立即释放不必要的内存占用 缺点&#xf…

「数据结构」线性表

定义和基本操作 定义&#xff1a;相同数据类型的 n ( n ≥ 0 ) n(n \ge 0) n(n≥0)个数据元素的有限序列&#xff0c;其中n为表长&#xff0c;当n0时线性表是一个空表一般表示&#xff1a; L ( a 1 , a 2 , … … , a i , a i 1 , a n ) L(a_1,a_2,……,a_i,a_{i1},a_n) L(a…

django实现外键

一&#xff1a;介绍 在Django中&#xff0c;外键是通过在模型字段中使用ForeignKey来实现的。ForeignKey字段用于表示一个模型与另一个模型之间的多对一关系。这通常用于关联主键字段&#xff0c;以便在一个模型中引用另一个模型的相关记录。 下面是一个简单的例子&#xff0…

CentOS 7.9安装Tesla M4驱动、CUDA和cuDNN

正文共&#xff1a;1333 字 21 图&#xff0c;预估阅读时间&#xff1a;2 分钟 上次我们在Windows上尝试用Tesla M4配置深度学习环境&#xff08;TensorFlow识别GPU难道就这么难吗&#xff1f;还是我的GPU有问题&#xff1f;&#xff09;&#xff0c;但是失败了。考虑到Windows…

​​​​​​​C#系列-C#EF框架的优缺点+针对大数据处理的优化(19)

C#EF框架的优缺点 C# EF&#xff08;Entity Framework&#xff09;框架的优缺点如下&#xff1a; 优点&#xff1a; 简单易用&#xff1a;EF框架提供了丰富的API和工具&#xff0c;使得开发者可以轻松地实现数据库的增删改查等操作&#xff0c;无需编写繁琐的SQL语句。对象化…

【Jenkins】Jenkins关闭Jenkins关闭、重启

目录 一、Jenkins关闭、重启 二、Jenkins服务的启动、停止方法。 一、Jenkins关闭、重启 1.关闭Jenkins 只需要在访问jenkins服务器的网址url地址后加上exit&#xff0c;关闭Jenkins服务。 例如&#xff1a;http://localhost:8081/exit 2.重启Jenkies 只有在Jenkins服务启动…

图像处理入门:OpenCV的基础用法解析

图像处理入门&#xff1a;OpenCV的基础用法解析 引言OpenCV的初步了解深入理解OpenCV&#xff1a;计算机视觉的开源解决方案什么是OpenCV&#xff1f;OpenCV的主要功能1. 图像处理2. 图像分析3. 结构分析和形状描述4. 动态分析5. 三维重建6. 机器学习7. 目标检测 OpenCV的应用场…

政安晨:在Jupyter中【示例演绎】Matplotlib的官方指南(二){Image tutorial}·{Python语言}

咱们接着上一篇&#xff0c;这次咱们讲使用Matplotlib绘制图像的简短尝试。 我的这个系列的上一篇文章在这里&#xff1a; 政安晨&#xff1a;在Jupyter中【示例演绎】Matplotlib的官方指南&#xff08;一&#xff09;{Pyplot tutorial}https://blog.csdn.net/snowdenkeke/ar…

ctfshow-文件上传(web151-web161)

目录 web151 web152 web153 web154 web155 web156 web157 web158 web159 web160 web161 web151 提示前台验证不可靠 那限制条件估计就是在前端设置的 上传php小马后 弹出了窗口说不支持的格式 查看源码 这一条很关键 这种不懂直接ai搜 意思就是限制了上传类型 允许…

C#系列-C#EF框架返回单行记录(24)

在C#中&#xff0c;使用Entity Framework (EF)框架时&#xff0c;如果你想要执行一个查询并返回单行记录&#xff0c;你可以使用SingleOrDefault、FirstOrDefault、Single或First方法。这些方法适用于DbSet<T>对象&#xff0c;它们可以执行查询并返回单个实体或默认值&am…

npm install express -g报错或一直卡着,亲测可解决

问题描述&#xff1a; 最近学习vue3前端框架&#xff0c;安装Node.js之后&#xff0c;在测试是否可行时&#xff0c;cmd窗口执行了&#xff1a;npm install express -g&#xff0c;发现如下图所示一直卡着不动&#xff0c;最后还报错了&#xff0c;网上找了好久&#xff0c;各…
最新文章