盖子的c++小课堂——第二十二讲:2维dp

前言

大家好,我又来更新了,今天终于有时间了aaaaaaaa

破500粉了,我太高兴了哈哈哈哈哈哈(别看IP地址,我去北京旅游回来了,他没改回来),然后我马上就成为创作者一年了,希望大家别取关啊,一会儿没更新,粉丝就刷刷往下掉(我刚破的510啊┭┮﹏┭┮)

哎哎,话不多说,我们开始吧(诶诶!先别直接退,这次可花了我一个多小时写的,麻烦看到底吧)

二维递推、二维动态规划

要理解二维递推、二维动态规划,我们先分别讲一下一维数组和二维数组。

什么是数组

在程序中,经常需要对一批数据进行操作,例如,统计某个公司100个员工的平均工资。如果使用变量来存放这些数据,就需要定义100个变量,显然这样做很麻烦,而且很容易出错。这时,可以使用X[0]、X[1]、X[2]、…、X[99]表示这100个变量,并通过方括号中的数字来对这100个变量进行区分。
在程序设计中,使用X[0]、X[1]、X[2]、…、X[99]表示的一组具有相同数据类型的变量集合称为数组X,数组中的每一项称为数组的元素,每个元素都有对应的下标(n),用于表示元素在数组中的位置序号,该下标是从0开始的。

 需要注意的是,根据数据的复杂度,数组下标的个数是不确定的。通常情况下,数组元素下标的个数也称为维数,根据维数的不同,可将数组分为一维数组、二维数组、三维数组、四维数组等。通常情况下,我们将二维及以上的数组称为多维数组。

一维数组

一维数组的定义与初始化

一维数组指的是只有一个下标的数组,它用来表示一组具有相同类型的数据。在C语言中,一维数组的定义方式如下所示:

类型说明符 数组名[常量表达式];

在上述语法格式中,类型说明符表示数组中所有元素的类型,常量表达式指的是数组的长度,也就是数组中存放元素的个数。

例:

int array[5l;

上述代码定义了一个数组,其中,int是数组的类型,aray是数组的名称,方括号中的5是数组的长度。完成数组的定义后,只是对数组中的元素开辟了一块内存空间。这时,如果想使用数组操作数据,还需要对数组进行初始化。数组初始化的常见的方式有3种,具体如下

(1)直接对数组中的所有元素赋值,示例代码如下:

int i[5]={1,2,3,4,5};

上述代码定义了一个长度为5的数组i,并且数组中元素的值依次为1、2、3、4、5。

(2)只对数组中的一部分元素赋值,示例代码如下

int i[5]={1,2,3};

在上述代码中,定义了一个int类型的数组,但在初始化时,只对数组中的前3个元素进行了赋值,其他元素的值会被默认设置为

(3)对数组全部元素赋值,但不指定长度,示例代码如下:

int i[]={1,2,3,4};

在上述代码中,数组i中的元素有4个,系统会根据给定初始化元素的个数定义数组的长度,因此,数组i的长度为4。

注意!(1)数组的下标是用方括号括起来的,而不是圆括号;(2)数组名的命名同变量名的命名规则相同;(3)数组定义中,常量表达式的值可以是符号常量,如下面的定义就是合法的。

int a[N];      //假设预编译命令#define N 4,下标是符号常量

一维数组的引用

在程序中,经常需要访问数组中的一些元素,这时可以通过数组名和下标来引用数组中

的元素。一维数组元素的引用方式如下所示:

数组名 [下标];

在上述方式中,下标指的是数组元素的位置,数组元素的下标是从0开始的。例如,引用数组X的第3个元素的方式为X[2]为了帮助大家更好地理解数组元素的引用榜下业通计一个室例来演示,如下所示:

#include<stdio.h>
void main(int argc, char *argv[]){int x[5] = {2,3,1,4,6};int i;for (i = 0; i < 5; i++) {printf("%d\n", 2 * x[i]);}
}

注意!数组的下标都有一个范围,即“0~[数组长度-1]”,假设数组的长度为6,其下标范围为0~5。当访问数组中的元素时,下标不能超出这个范围,否则程序会报错。

 一维数组的常见操作

数组在编写程序时应用非常广泛,如经常需要对数组进行遍历、获取最值、排序等操作灵活地使用数组对实际开发很重要。接下来针对一维数组的常见操作进行详细的讲解,具体如下。

1、一维数组的遍历

在操作数组时,经常需要依次访问数组中的每个元素,这种操作称作数组的遍历。接下来使用for循环依次遍历数组中的元素,如下所示:

#include<stdio.h>
void main(int argc, char *argv[]){int x[5] = {2,3,1,4,6};int i = 0;for (i = 0; i < 5; i++) {printf("x[%d]:%d\n", i, x[i]);}
}

2、一维数组的最值

在操作数组时,经常需要获取数组中元素的最值。接下来通过案例演示如何获得数组中最大的数值。

#include<stdio.h>
int main(int argc, char *argv[]){int x[5] = {2,3,1,4,6};int nMax = x[0];int i = 0;for (i = 0; i < 5; i++) {if (x[i] > nMax) {nMax = x[i];}}printf("max:%d\n", nMax);return 0;
}

 在上面案例找那个实现了获取数组X最大值的功能。在第5行代码中假定数组中的第1个元素为最大值,并将其赋值给nMax,在第7~13行代码对数组中的其他元素进行遍历,如果发现比mMax值大的元素,就将最大值nMx设置为这个元素的值,这样,当数组遍历完成后,nMax中存储的就是数组中的最大值。

3、一维数组的排序

在操作数组时,经常需要对数组中的元素进行排序。接下来为大家介绍一种比较常见的排序算法一冒泡排序。在冒泡排序的过程中,不断地比较数组中相邻的两个元素,较小者向上浮、较大者往下沉,整个过程和水中气泡上升的原理相似,接下来,分步骤讲解冒泡排序的整个过程,具体如下。

第1步,从第1个元素开始,将相邻的两个元素依次进行比较,直到最后两个元素完成比较。如果前1个元素比后1个元素大,则交换它们的位置。整个过程完成后,数组中最后1个元素自然就是最大值,这样也就完成了第1轮的比较。

第2步,除了最后1个元素,将剩余的元素继续进行两两比较,过程与第1步相似,这样就可以将数组中第二大的数放在倒数第2个位置。

第3步,依次类推,持续对越来越少的元素重复上面的步骤,直到没有任何一对元素需要比较为止。

了解了冒泡排序的原理之后,接下来通过一个案例来实现冒泡排序。

#include<stdio.h>
void main(int argc, char ** argv[]){int arr[5] = { 9,8,3,5,2 };int temp = 0;int i, j;printf("冒泡排序前:\n");for (i = 0; i < 5; i++) {printf("%d ", arr[i]);}printf("\n");for (i = 0; i < 5 - 1; i++) {for (j = 0; j < 5 - 1 - i; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}printf("冒泡排序后:\n");for (i = 0; i < 5; i++) {printf("%d ", arr[i]);}printf("\n");
}

 在上面的案例中,通过嵌套for循环实现了冒泡排序。其中,外层循环用来控制进行多少轮比较,每一轮比较都可以确定1个元素的位置,由于最后1个元素不需要进行比较,因此,外层循环的次数为数组的长度-1,内层循环的循环变量用于控制每轮比较的次数,在每次比较时,如果前者小于后者,就交换两个元素的位置。下面通过一张动图来演示冒泡排血的运算过程。

 

二维数组

二维数组的定义与初始化 

在实际的工作中,仅仅使用一维数组是远远不够的,例如,一个学习小组有5个人,每个人有3门课的考试成绩,如果使用一维数组解决是很麻烦的。这时,可以使用二维数组,维数组的定义方式与一维数组类似,其语法格式如下:

类型说明符 数组名[常量表达式1] [常量表达式2];

在上述语法格式中,“常量表达式1”被称为行下标,“常量表达式2”被称为列下标。

例如,定义一个3行4列的二维数组,具体如下:

int a[3][4];

在上述定义的二维数组中,共包含3*4个元素,即12个元素。

完成二维数组的定义后,需要对二维数组进行初始化,初始化二维数组的方式有4种,具体如下。

(1)按行给二维数组赋初值。例如:

int a[2][3] = {{1,2,3},{4,5,6}};

在上述代码中,等号后面有一对大括号,大括号中的第1对括号代表的是第1行的数组元素,第2对括号代表的是第2行的数组元素。

(2)将所有的数组元素按行顺序写在1个大括号内。例如

int a[2][3] = {1,2,3,4,5,6};

在上述代码中,二维数组a共有两行,每行有3个元素,其中,第1行的元素依次为1、2、3,第2行元素依次为4、5、6。

(3)对部分数组元素赋初值。例如:

int b[3][4] = {{1},{4,3},{2,1,2}};

在上述代码中,只为数组b中的部分元素进行了赋值,对于没有赋值的元素,系统会自动赋值为0

(4)如果对全部数组元素置初值,则二维数组的第1个下标可省略,但第2个下标不能省略。例如

int a[2][3] = {1,2,3,4,5,6};

可以写为

int a[][3] = {1,2,3,4,5,6};

系统会根据固定的列数,将后边的数值进行划分,自动将行数定为2。

二维数组的引用

二维数组的引用方式同一维数组的引用方式一样,也是通过数组名和下标的方式来引用数组元素,其语法格式如下:

数组名[下标] [下标];

在上述语法格式中,下标值应该在已定义的数组的大小范围内,例如,下面这种情况就是错误的。

int a[3][ 4];    //定义a为3行4列的二维数组
a[3][4]=3;    //对数组a第3行第4列元素赋值,出错在上述代码中,数组a可用的行下标范围是0~2,列下标是0~3,a[3][4]超出了数组的下标范围。为了帮助读者更好地掌握二维数组的引用,接下来,通过一个案例来演示二维数组的遍历。#include<stdio.h>
void main() {//申明并初始化数组int array[3][4] = { {1,2,3,4},{5,6,7,8},{9,10,11,12} };for (int i = 0; i < 3; i++)    //循环遍历{for (int j = 0; j < 4; j++)    //循环遍历{printf("[%d][%d]: %d", i, j, array[i][j]);}printf("\n");    //每行添加换行字符}
}

 当使用嵌套for循环遍历二维数组元素时,外层for循环用于变量数组的行元素,内层for循环用于遍历数组的列元素。从图中可以看出,程序依次将数组aray中的元素输出了。

二维数组的应用

熟悉了二维数组的定义和引用,接下来定义一个二维数组 StuScore[5][3],用来存放5名同学3门课程的成绩,并定义变量m表示学生,n表示第几门成绩,aver表示每名同学3门课程的平均成绩,sum表示每名同学3门课的总成绩,具体如下案例所示:

#include<stdio.h>
void main(int argc, char *argv[])
{int StuScore[5][3] = {//张同学{88, 70, 90},//王同学{80, 80, 60},//李同学{89, 60, 85},//赵同学{80, 75, 78},//周同学{70, 80, 80}};int m = 0, n = 0;int nStuTotalScore = 0;int nMathTotalScore = 0;int nChineseTotalScore = 0;int nEnglishToatalScore = 0;printf("个人总成绩:\n");for (m = 0; m < 5; m++) {nStuTotalScore = 0;for (n = 0; n < 3; n++) {nStuTotalScore += StuScore[m][n];switch (n){case 0:{nMathTotalScore += StuScore[m][n];break;}case 1:{nChineseTotalScore += StuScore[m][1];break;}case 2:{nEnglishToatalScore += StuScore[m][2];}}}switch (m){case 0:{printf("张同学:%d\n", nStuTotalScore);break;}case 1:{printf("王同学:%d\n", nStuTotalScore);break;}case 2:{printf("李同学:%d\n", nStuTotalScore);break;}case 3:{printf("赵同学:%d\n", nStuTotalScore);break;}case 4:{printf("周同学:%d\n", nStuTotalScore);break;}}}printf("小组数学总分: %d 小组数学平均分:%.2f\n",nMathTotalScore, (double)nMathTotalScore / 5);printf("小组语文学总分: %d 小组语文平均分:%.2f\n",nChineseTotalScore, (double)nChineseTotalScore / 5);printf("小组英语总分: %d 小组英语平均分:%.2f\n",nEnglishToatalScore, (double)nEnglishToatalScore / 5);}

 上面案例中实现了计算小组各科平均分的功能。其中,第415行代码定义了一个二维数组,用来存储小组中每个成员的各科成绩。第25~45行代码通过遍历列下标获取每个小组不同学科的总分,第46~74行代码通过遍历行下标获取每个小组成员的总分,最后将小组不同学科的总分和平均分输出。

以上参考C语言中的一维数组和二维数组什么?怎么用? - 知乎 (zhihu.com) 

例题——杨辉三角形

输入一个正整数n,打印出一个n行的杨辉三角形。n<=20。

若i==1,且j==1 ——> yh[1][1]=1(初始条件)

若i>=2,且j<=i——>yh[i][j]=yh[i-1][j-1]+yh[i-1][j](递推方程)

 代码

#include<bits/stdc++.h>
using namespace std;
int tri[25][25], n;
int main(){cin>>n;tri[1][1] = 1;for(int i = 2; i <=n; i ++)for(int j = 1; j <= i; j ++)tri[i][j] = tri[i-1][j-1] + tri[i-1][j];for(int i = 1; i<=n; i ++){for(int j = 1; j <=i-1; j ++)cout<<tri[i][j]<<" ";cout<<tri[i][i]<<endl;}return 0;
}

总结

好了,这次就到这里了,希望大家多多支持,记得点个不要钱的关注,谢谢大家Thanks♪(・ω・)ノ,拜拜

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/119885.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于Java+SpringBoot+Vue前后端分离农商对接系统设计和实现

博主介绍&#xff1a;✌全网粉丝30W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专…

Android样本Repack重打包检测思路

1. 什么是Android样本重打包&#xff0c;为什么要检测重打包 &#xff08;1&#xff09;apk是zip&#xff0c;很容易做repack &#xff08;2&#xff09;repack后&#xff0c;被抄袭&#xff0c;redirect ad&#xff0c;或者插入malicious payloads &#xff08;3&#xff09;…

传输层—TCP原理详解

目录 前言 1.TCP协议 2.TCP协议段格式 3.如何解包如何分用 4.网络协议栈和文件的关系 5.如何理解TCP报头 6.TCP的特点 7.TCP字段 7.1 16位窗口大小 7.2标志位 8.超时重传 9.连接管理机制 10.滑动窗口 11.拥塞控制 12.延迟应答 13.捎带应答 14.理解TCP的面向字…

使用LightPicture开源搭建私人图床:详细教程及远程访问配置方法

文章目录 1.前言2. Lightpicture网站搭建2.1. Lightpicture下载和安装2.2. Lightpicture网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 现在的手机越来越先进&#xff0c;功能也越来越多&#xff0c;而手机…

计算机网络-谢希任第八版学习笔记总结

一.计算机网络概述 21世纪三个特点 数字化 信息化 智能化&#xff0c;其中主要是围绕智能化。 网络的常见分类&#xff1a; 电话网络 有线电视网络 计算机网络 互联网&#xff1a;Internet 由数量极大的计算机网络相连接 特点&#xff1a; 共享性 连通性 互联网&…

【python爬虫】中央气象局预报—静态网页图像爬取练习

静态网页爬取练习 中央气象局预报简介前期准备步骤Python爬取每日预报结果—以降水为例 中央气象局预报简介 中央气象台是中国气象局&#xff08;中央气象台&#xff09;发布的七天降水预报页面。这个页面提供了未来一周内各地区的降水预报情况&#xff0c;帮助人们了解即将到来…

项目介绍:《Online ChatRoom》网页聊天室 — Spring Boot、MyBatis、MySQL和WebSocket的奇妙融合

在当今数字化社会&#xff0c;即时通讯已成为人们生活中不可或缺的一部分。为了满足这一需求&#xff0c;我开发了一个名为"WeTalk"的聊天室项目&#xff0c;该项目基于Spring Boot、MyBatis、MySQL和WebSocket技术&#xff0c;为用户提供了一个实时交流的平台。在本…

神经网络与卷积神经网络

全连接神经网络 概念及应用场景 全连接神经网络是一种深度学习模型&#xff0c;也被称为多层感知机&#xff08;MLP&#xff09;。它由多个神经元组成的层级结构&#xff0c;每个神经元都与前一层的所有神经元相连&#xff0c;它们之间的连接权重是可训练的。每个神经元都计算…

机器连接和边缘计算

以一种高效、可扩展的方式进行连接和边缘计算的结合&#xff0c;解决了在工业物联网应用中的机器数据集成问题。 一 边缘计算 边缘计算描述了由中央平台管理的数据分散式处理&#xff0c;它对于工业物联网而言非常重要。在许多应用程序中&#xff0c;由于数据量非常大&#xf…

用ChatGPT做一个Chrome扩展 | 京东云技术团队

用ChatGPT做了个Chrome Extension 最近科技圈儿最火的话题莫过于ChatGPT了。 最近又发布了GPT-4&#xff0c;发布会上的Demo着实吸睛。 笔记本上手画个网页原型&#xff0c;直接生成网页。网友直呼&#xff1a;前端失业了&#xff01; 但我觉着啊&#xff0c;真就外行看热闹…

docker-compose 部署nacos 整合 postgresql 为DB

标题docker-compose 部署nacos 整合 postgresql 为DB 前提&#xff1a; 已经安装好postgresql数据库 先创建好一个数据库 nacos&#xff0c;执行以下sql: /** Copyright 1999-2018 Alibaba Group Holding Ltd.** Licensed under the Apache License, Version 2.0 (the "…

说说redo log 与 undo log

redo log redo log叫做重做日志.用于解决数据库事物提交 还未刷入磁盘,服务器down机导致的数据丢失的问题。 InnoDB作为MySQL的存储引擎&#xff0c;数据存储在磁盘中&#xff0c;如果每次读写数据都要操作磁盘IO效率会很低&#xff0c;为此InnoDB提供了缓存(Buffer Pool)&am…

白鲸开源 DataOps 平台加速数据分析和大模型构建

作者 | 李晨 编辑 | Debra Chen 数据准备对于推动有效的自助式分析和数据科学实践至关重要。如今&#xff0c;企业大都知道基于数据的决策是成功数字化转型的关键&#xff0c;但要做出有效的决策&#xff0c;只有可信的数据才能提供帮助&#xff0c;随着数据量和数据源的多样…

阿里云centos9stream安装宝塔+vscode(code-server)集成云端开发环境

一、 安装宝塔面板 官网 https://www.bt.cn/new/download.htm 题外话&#xff1a;虽然感觉现在宝塔没以前好用了&#xff0c;而且有centos7、8 mysql编译导致OOM服务器挂掉无法ssh登录的情况&#xff0c;但他还是远程管理服务器的好选择&#xff0c;提示宝塔只支持最新的centos…

QT listWidget 中实现元素的自由拖拽

QListWIdget中拖拽元素移动 setMovement(QListView::Movement::Free);setDragEnabled(true); setDragDropMode(DragDropMode::DragDrop); setDefaultDropAction(Qt::DropAction::MoveAction);

stable diffusion实践操作-宽高设置以及高清修复

系列文章目录 stable diffusion实践操作 文章目录 系列文章目录前言一、SD宽高怎么设置&#xff1f;1.1 宽高历史 二、高清修复1. 文生图中的高清修复1.按钮Hires.fix2.不同放大算法对比1.第一类2.第二类3.第三类4.第四类5.第五类6.第六类7.第七类8.第八类9.第九类10.第十类11…

深入理解css3背景图边框

border-image知识点 重点理解 border-image-slice 设置的值将边框背景图分为9份&#xff0c;图像中间的舍弃&#xff0c;其他部分图像对应边框的相应区域放置&#xff0c;上右下左四角固定&#xff0c;border-image-repeat设置的是除四角外其他部分的显示方式。 截图来自菜鸟教…

文件包含漏洞及漏洞复现

文件包含漏洞 1. 文件包含概述 程序开发人员通常会把可重复使用函数或语句写到单个文件中&#xff0c;形成“封装”。在使用某个功能的时候&#xff0c;直接调用此文件&#xff0c;无需再次编写&#xff0c;提高代码重用性&#xff0c;减少代码量。这种调用文件的过程通常称为…

【AWS】实操-保护 Amazon S3 VPC 终端节点通信

文章目录 实验概览目标实验环境任务 1&#xff1a;探索并启动实验环境任务 1.1&#xff1a;探索 Amazon VPC 资源任务 1.2&#xff1a;探索 Amazon EC2 资源任务 1.3&#xff1a;创建 Amazon VPC 终端节点任务 1.4&#xff1a;连接私有 EC2 实例任务 1.5&#xff1a;探索 Amazo…

Nginx从入门到精通(超级详细)

文章目录 一、什么是Nginx1、正向代理2、反向代理3、负载均衡4、动静分离 二、centos7环境安装Nginx1、安装依赖2、下载安装包3、安装4、启动5、停止 三、Nginx核心基础知识1、nginx核心目录2、常用命令3、默认配置文件讲解4、Nginx虚拟主机-搭建前端静态服务器5、使用nignx搭建…