算法设计与分析2023秋-头歌实验-实验七 动态规划

文章目录

  • 第1关：数塔问题
    • 任务描述
    • 相关知识
    • 编程要求
    • 解题思路
    • 测试说明
    • 参考答案
  • 第2关：最长公共子序列
    • 任务描述
    • 相关知识
    • 编程要求
    • 解题思路：
    • 测试说明
    • 参考答案
  • 第3关：求序列-2 11 -4 13 -5 -2的最大子段和
    • 任务描述
    • 相关知识
    • 编程要求
    • 解题思路：
    • 测试说明
    • 参考答案
  • 第4关：求最长的单调递增子序列长度
    • 任务描述
    • 相关知识
    • 编程要求
    • 解题思路：
    • 测试说明
    • 参考答案
  • 第5关：矩阵连乘问题
    • 任务描述
    • 相关知识
    • 编程要求
    • 测试说明
    • 参考答案

第1关：数塔问题

任务描述

本关任务：编写用动态规划解决数塔问题。

相关知识

为了完成本关任务，你需要掌握：动态规划。

编程要求

image.jpg
求上图从顶层到顶层的一个路径，使路径上的数字和最大。要求输出最大的数字和max和数值和最大的路径。

解题思路

原始信息有层数和数塔中的数据，层数用一个整型变量n存储，数塔中的数据用二维数组data，存储成如下的下三角阵:

             9
             12    15
             10    6     8
             2     18    9    5
             19    7     10   4   16

必需用二维数组d存储各阶段的决策结果。二维数组d的存储内容如下：、

  d[n][j]=data[n][j]，         j=1,2,……,n；
    d[i][j]=max(d[i+1][j]，d[i+1][j+1])+data[i][j]，   i=n-1,n-2,……1，j=1,2,……,i

最后d[1][1]存储的就是问题的结果。

测试说明

平台会对你编写的代码进行测试：
测试输入：

5
9
12    15
10    6     8
2    18     9    5
19    7     10   4   16

输出示例：

max=59
数值和最大的路径是：9->12->10->18->10

参考答案

#include <stdio.h> 
#define N 5 //问题规模
int main() {
    int a[50][50];
    a[1][1] = 9;
    a[2][1] = 12, a[2][2] = 15;
    a[3][1] = 10, a[3][2] = 6, a[3][3] = 8;
    a[4][1] = 2, a[4][2] = 18, a[4][3] = 9, a[4][4] = 5;
    a[5][1] = 19, a[5][2] = 7, a[5][3] = 10, a[5][4] = 4, a[5][5] = 16;

    int i, j, dp[50][50] = { 0 }, path[50][50] = { 0 };
    for (j = 1; j <= N; j++)                           //初始子问题 ，倒数第二层（第i-1层）开始
        dp[N][j] = a[N][j];
    for (i = N - 1; i >= 1; i--)                       //进行第 i+1 层的决策，从i 到 1 向上
        for (j = 1; j <= i+1; j++) {                     //每一层有 i+1 个
            if (dp[i + 1][j] > dp[i + 1][j + 1]) {
                dp[i][j] = a[i][j] + dp[i + 1][j];
                path[i][j] = j;                        //本次决策选择下标j的元素
            }
            else {
                dp[i][j] = a[i][j] + dp[i + 1][j + 1];
                path[i][j] = j + 1;                     //本次决策选择下标j+1的元素
            }
        }
    printf("max=%d\n", dp[1][1]);
    printf("数值和最大的路径是：");            
    j = path[1][1];                          //计算dp[1][1]的选择
    for (i = 1; i < N; i++)
    {
        printf("%d->", a[i][j]);
        j = path[i][j];                         //计算dp[i][j]的选择
    }
    printf("%d\n", a[i][j]);

}
/********** End **********/

第2关：最长公共子序列

任务描述

本关任务：编写用动态规划解决最长公共子序列问题。

相关知识

为了完成本关任务，你需要掌握：动态规划。

编程要求

求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列

解题思路：

递推关系分析： 设 A=“a0，a1，…，am−1”，B=“b0，b1，…，bn−1”，Z=“z0,z1,…,zk−1” 为它们的最长公共子序列。 有以下结论： 1）如果am−1=bn−1,则zk−1=am−1=bn−1,且“z0,z1,…,zk−2”是“a0,a1,…,am−2”和“b0,b1,…,bn−2”的一个最长公共子序列； 2）如果am−1=bn−1，则若zk−1=am−1，蕴涵“z0，z1，…，zk−1”是“a0,a1,…,am−2”和“b0,b1,…,bn−1”的一个最长公共子序列； 3）如果am−1=bn−1，则若zk−1=bn−1，蕴涵“z0，z1，…，zk−1”是“a0，a1，…，am−1”和“b0，b1，…，bn−2”的一个最长公共子序列。 定义c[i][j]为序列“a0,a1,…,ai−1”和“b0,b1,…,bj−1”的最长公共子序列的长度，计算c[i][j]可递归地表述如下： 1）c[i][j]=0 如果i=0或j=0； 2）c[i][j]=c[i−1][j−1]+1 如果i,j>0,且a[i−1]=b[j−1]； 3）c[i][j]=max(c[i][j−1],c[i−1][j]) 如果i,j>0,且a[i−1]=b[j−1]。 由二维数组c的递归定义，c[i][j]的结果依赖于c[i−1][j−1]，c[i−1][j]和c[i][j−1]。可以从c[m][n]开始，跟踪c[i][j]结果的产生过程，从而逆向构造出最长公共子序列。

测试说明

平台会对你编写的代码进行测试：
测试输入：

a=“ABCDBAB”
b=“BDCABA”

输出示例：

BCBA

参考答案

/*动态规划之最大子序列*/
#include <stdio.h>
int main()
{
	char A[7]={'A','B','C','B','D','A','B'};			
	char B[6]={'B','D','C','A','B','A'};
	int dp[8][7];						//dp数组记录最长公共子序列的长度 
	for(int i=0;i<7;i++)		//边界赋值为0 
	{
		dp[i][0]=0;
	 }
	for(int i=0;i<8;i++)
	{
		dp[0][i]=0;
	}
	
	// printf("test1=%d\n",dp[6][7]);
	
	for(int i=1;i<=7;i++)
	{
		for(int j=1;j<=6;j++)
		{
			if(A[i-1]==B[j-1])			//如果相等就dp[i][j]=dp[i-1][j-1]+1; 
			{
				dp[i][j]=dp[i-1][j-1]+1;
			}
			else{
					if(dp[i-1][j]>dp[i][j-1])
					{
						dp[i][j]=dp[i-1][j];   //取两者之间较大者；局部的最优值 
					}
					else{
						dp[i][j]=dp[i][j-1];
					} 	
			}
		}
	  }
	  
	char str[100];							//记录公共的字符
	int i=7,j=6;
	int count=0;
	while(i>0&&j>0)
	{
		if(dp[i][j]==dp[i-1][j])			//往上遍历 
		{
			i--;
		}
		else if(dp[i][j]==dp[i][j-1])		//往左遍历 
		{
			j--;
		}
		else{
			str[count++]=A[i-1];
			i--;
			j--;
		}
	}
	
	for(int i=count-1;i>=0;i--)
	{
		printf("%c",str[i]);
	 } 
 }

第3关：求序列-2 11 -4 13 -5 -2的最大子段和

任务描述

本关任务：编写用动态规划解决最大子段和问题。

相关知识

为了完成本关任务，你需要掌握：动态规划。

编程要求

给定由n个整数（可能为负数）组成的序列：a1,a2,……,an, 求该序列的最大子段和。当所有整数均为负数，定义其最大子段和为0。

解题思路：

定义b[j]=max(a[i]+a[i+1]+…+a[j])，其中1<=i<=j，并且1<=j<=n。那么所求的最大子段和可以表示为max b[j]，1<=j<=n。 由b[j]的定义可知，当b[j−1]>0时b[j]=b[j−1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归表达式为: b[j]=max(b[j−1]+a[j],a[j])，1<=j<=n。

测试说明

平台会对你编写的代码进行测试：
测试输入：

6
-2 11 -4 13 -5 -2

输出示例：

20

参考答案

#include <stdio.h>
/********** Begin **********/
int main(){
	int n;
	scanf("%d",&n);
	int a[n][2];
	int max=0;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i][0]);
		if(i==0){
			a[i][1]=a[i][0];
		}
		else{
			a[i][1]=a[i-1][1]+a[i][0]>a[i][0]?a[i-1][1]+a[i][0]:a[i][0];
		}
		
		max=max>a[i][1]?max:a[i][1];
		
	}
	printf("%d",max);
	return 0;
	
}
/********** End **********/

第4关：求最长的单调递增子序列长度

任务描述

本关任务：编写用动态规划解决求最长的单调递增子序列长度问题。

相关知识

为了完成本关任务，你需要掌握：动态规划。

编程要求

给定一个长度为n的数组，找出一个最长的单调递增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为7的数组A5，6，7，1，2，8,9，则其最长的单调递增子序列为5，6，7，8，9，长度为5。求318714101223411624的最长的单调递增子序列长度。

解题思路：

设长度为n的数组为(a[0]，a[1],a[2],…，a[n−1])，则假定以a[j]结尾的数组序列的最长递增子序列长度为L(j)，则L(j)=max(L(i))+1,i<j且a[i]<a[j]。也就是说，我们需要遍历在j之前的所有位置i(从0到j−1)，找出满足条件a[i]<a[j]的L(i)，求出max(L(i))+1即为L(j)的值。最后，我们遍历所有的L(j)（从0到n−1），找出最大值即为最大递增子序列。

测试说明

平台会对你编写的代码进行测试：
测试输入：

10
3 18 7 14 10 12 23 41 16 24

输出示例：

6

参考答案

#include <stdio.h>
/********** Begin **********/
int main(){
	 int n;
	 scanf("%d",&n);
	 int m[n][3];
	 m[0][1]=1;
	 m[0][2]=0;
	 for(int i=0;i<n;i++){
		scanf("%d",&m[i][0]);
		if(i!=0){
			m[i][1]=0;
			int k=i-1;
			while(k>=0){
				if(m[i][0]>m[k][0]){
						if(k==i-1){
							m[i][1]=m[k][1]+1;
							m[i][2]=k;
						}
						else{
							int max=m[k][1]+1;
							if(max>m[i][1]){
								m[i][1]=max;
								m[i][2]=k;	
							}
					    }
				}
			 k--;
			}
			if(k<0&&m[i][1]==0){
			    m[i][1]=1;
			    m[i][2]=i;
			}
		}
	 }
 
	int max=m[0][1],j=0;
	for(int i=0;i<n;i++){
	      if(m[i][1]>=max){
	             max=m[i][1];
	             j=i;
	      }
	 }
	printf("%d\n",max);
}
/********** End **********/

第5关：矩阵连乘问题

任务描述

本关任务：编写用动态规划解决矩阵连乘问题。

相关知识

为了完成本关任务，你需要掌握：动态规划。

编程要求

将矩阵连乘积AiAi+1…Aj简记为A[i:j]，其中i<=j。设在矩阵Ak和Ak+1之间将矩阵链断开，则其相应加括号为(AiAi+1…Ak) (Ak+1Ak+2…Aj)。A[i:j]的计算量等于三部分计算量之和： （1）A[i:k]的计算量， （2）A[k+1:j]的计算量， （3）A[i:k]与A[k+1:j]相乘的计算量。 设计算A[i:j]所需最少乘积数目为，则原问题的最优值为。 当i=j时,a[i:j]=Ai，因此，m[i][j]=0,i=1,⋅⋅⋅,n 当i<j时，m[i][j]=i<k<jmin{m[i][k]+m[k+1][j]+pi−1pkpj} 其中，矩阵Ai的矩阵数为pi−1×pi 矩阵A1的维度：p0p1=3035 矩阵A2的维度：p1p2=3515 矩阵A3的维度：p2p3=155 矩阵A4的维度：p3p4=510 矩阵A5的维度：p4p5=1020 矩阵A6的维度：p5p6=2025 求这6个矩阵连乘的最小相乘次数。

测试说明

平台会对你编写的代码进行测试：
测试输入：

6
30 35
35 15
15 5
5 10
10 20
20 25

输出示例：

m[1][6]=15125

参考答案

#include <stdio.h>
#include <stdlib.h>
/********** Begin **********/
int main(){
	int n;
	scanf("%d",&n);
	int a[n][2];
	int b[n][n]={0};
	for(int i=0;i<n;i++){
	    scanf("%d %d",&a[i][0],&a[i][1]);   
	}
	
	for(int i=1;i<n;i++){
	    for(int j=0;j<n-i;j++){
	      b[j][j+i]=b[j][j]+b[j+1][j+i]+a[j][0]*a[j][1]*a[j+i][1];         
	      int k=j+1;
	      for(;k<j+i;k++){
	              int t=b[j][k]+b[k+1][j+i]+a[j][0]*a[k][1]*a[j+i][1];
	                if(t<b[j][j+i]) {
	                    b[j][j+i]=t;
	                }
	              
	      }
	
	    }
	        
	}
	printf("m[%d][%d]=%d",1,n,b[0][n-1]);
	return 0;
}
/********** End **********/

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

可实现RSSD云硬盘120万IOPS的SPDK IO路径优化

可实现RSSD云硬盘120万IOPS的SPDK IO路径优化

一. 简介 用户对超高并发、超大规模计算等需求推动了存储硬件技术的不断发展&#xff0c;存储集群的性能越来越好&#xff0c;延时也越来越低&#xff0c;对整体IO路径的性能要求也越来越高。在云硬盘场景中&#xff0c;IO请求从生成到后端的存储集群再到返回之间的IO路径比较…
阅读更多...
less基础介绍

less基础介绍

什么是less&#xff1f; Less是一个C5S预处理器,Less文件后缀是,less。扩充了 CSS 语言,使CSS 具备一定的逻辑性、计算能力 注意事项&#xff1a; 浏览器不识别 Less 代码&#xff0c;目前阶段&#xff0c;网页要引入对应的 CSS 文件 VS Code 插件: Easy LESS&#xff0c;保存 …
阅读更多...
JVM快速入门

JVM快速入门

JVM 字节码 字节码文件的组成 字节码由五个部分组成&#xff1a;基础信息 常量池 字段 方法 属性 基础信息&#xff1a; 魔数、字节码文件对应的版本号、访问标识&#xff08;public final&#xff09;、该类的父类索引、该类实现哪些接口的索引 魔数&#xff1a;文件无法…
阅读更多...
鸿蒙 - arkTs：渲染（循环 - ForEach，判断 - if）

鸿蒙 - arkTs：渲染（循环 - ForEach，判断 - if）

ForEach循环渲染&#xff1a; 参数&#xff1a; 要循环遍历的数组&#xff0c;Array类型遍历的回调方法&#xff0c;Function类型为每一项生成唯一标识符的方法&#xff0c;有默认生成方法&#xff0c;非必传 使用示例&#xff1a; interface Item {name: String,price: N…
阅读更多...
ValueError: source code string cannot contain null bytes

ValueError: source code string cannot contain null bytes

解决&#xff1a;把存在这个问题的包&#xff0c;全部卸载重装 pip uninstall xxx pip install xxx
阅读更多...
美国联邦机动车安全标准-FMVSS

美国联邦机动车安全标准-FMVSS

FMVSS标准介绍&#xff1a; FMVSS是美国《联邦机动车安全标准》&#xff0c;由美国运输部下属的国家公路交通安全管理局(简称NHTSA)具体负责制定并实施。是美国联邦政府针对机动车制定的安全标准&#xff0c;旨在提高机动车的安全性能&#xff0c;减少交通事故中的人员伤亡。F…
阅读更多...
路由跳转传递参数注意事项，查询字符串传参，params传参需要注意的地方，菜单内容的二级内容 vue3

路由跳转传递参数注意事项，查询字符串传参，params传参需要注意的地方，菜单内容的二级内容 vue3

路由跳转和传参(vue3)_vue3路由传参-CSDN博客 注意&#xff1a; import {useRouter} from "vue-router"const routeruseRouter()1.查询字符串传参&#xff0c;传一个对象&#xff0c;对象里面可以写path字段 router.push({path:/item,query:{id:1}} ) 通过当前路由…
阅读更多...
（保姆级教程）一篇文章，搞定所有Linux命令，以及tar解压缩命令，wget、rpm等下载安装命令，Linux的目录结构，以及用户和用户组

（保姆级教程）一篇文章，搞定所有Linux命令，以及tar解压缩命令，wget、rpm等下载安装命令，Linux的目录结构，以及用户和用户组

文章目录 Linux命令1. Linux目录结构2. 基本命令&#xff08;了解&#xff09;3. 目录&#xff08;文件夹&#xff09;命令列出目录切换目录创建目录删除目录复制目录移动和重命名目录 4. 文件命令创建文件编辑文件编辑文件时的其他操作 查看文件移动/重命名文件复制文件删除文…
阅读更多...
如何通过ETLCloud的API对接功能实现各种SaaS平台数据对接

如何通过ETLCloud的API对接功能实现各种SaaS平台数据对接

前言 当前使用SaaS系统的企业越来越多&#xff0c;当我们需要对SaaS系统中产生的数据进行分析和对接时就需要与SaaS系统提供的API进行对接&#xff0c;因为SaaS一般是不会提供数据库表给企业&#xff0c;这时就应该使用ETL&#xff08;Extract, Transform, Load&#xff09;的…
阅读更多...
Jmeter接口程序项目实战教程

Jmeter接口程序项目实战教程

1.什么是jmeter&#xff1f; JMeter是100%完全由Java语言编写的&#xff0c;免费的开源软件&#xff0c;是非常优秀的性能测试和接口测试工具&#xff0c;支持主流协议的测试 2.jmeter能做什么&#xff1f; JMeter是100%完全由Java语言编写的软件性能测试的GUI的测试工具&am…
阅读更多...
车载蓝牙物联网解决方案

车载蓝牙物联网解决方案

车载蓝牙物联网解决方案是一种基于蓝牙技术&#xff0c;结合物联网技术的智能车载系统。它利用蓝牙技术将智能手机、智能手表、智能车载设备等连接起来&#xff0c;实现设备之间的无缝通信和数据共享&#xff0c;为驾驶者提供更加便捷、安全和智能的驾驶体验。 车载蓝牙物联网解…
阅读更多...
【3D数据读取】利用JAVA读取GLB（GLTF）文件数据

【3D数据读取】利用JAVA读取GLB（GLTF）文件数据

了解GLB和GLTF&#xff1a; GLB和GLTF是用于共享3D数据的标准化文件格式。GLB是GLTF的二进制格式&#xff0c;而GLTF基于JSON&#xff0c;一种基于文本的数据格式。 GLB文件&#xff1a; 由一个头部和一个二进制数据块组成。头部包含文件的元数据&#xff0c;例如文件版本、文件…
阅读更多...
网络时代的新宠

网络时代的新宠

当今社会&#xff0c;随着科技的不断进步和互联网的普及&#xff0c;手机已经成为了人们生活中不可或缺的一部分。它不仅仅是一个通信工具&#xff0c;更是娱乐、学习和获取信息的利器。而其中&#xff0c;手机无人直播更是近年来备受关注的热门话题。 直播&#xff0c;一种实…
阅读更多...
hive 用户自定义函数udf，udaf，udtf

hive 用户自定义函数udf，udaf，udtf

udf&#xff1a;一对一的关系 udtf&#xff1a;一对多的关系 udaf&#xff1a;多对一的关系 使用Java实现步骤 自定义编写UDF函数注意&#xff1a; 1.需要继承org.apache.hadoop.hive.ql.exec.UDF 2.需要实现evaluete函数 编写UDTF函数注意&#xff1a; 1.需要继承org.apache…
阅读更多...
【MongoDB】--MongoDB的Sort排序问题

【MongoDB】--MongoDB的Sort排序问题

目录 一、问题背景描述1.1、问题背景1.2、问题分析 二、建立索引支持深度翻页查询2.1、调整sort排序的内存限制【不建议】2.2、创建索引2.3、拓展--组合索引什么时候失效 二、聚合查询解决深度翻页查询 一、问题背景描述 1.1、问题背景 现实系统页面翻页到20000页之后&#x…
阅读更多...
MQTT直连接入

MQTT直连接入

本文介如绍何使用MQTT协议&#xff0c;将设备直连到平台内置的MQTT服务。 操作步骤 创建产品 物联网->设备管理->选择产品&#xff0c;填写产品基础信息。 参数 对应设备侧参数 ID 产品唯一标识&#xff0c;若不填写&#xff0c;系统将自动生成唯一ID 设备类型 直…
阅读更多...
[Linux] LVS+Keepalived高可用集群部署

[Linux] LVS+Keepalived高可用集群部署

一、Keepalived实现原理 1.1 高可用方案 Keepalived 是一个基于VRRP协议来实现的LVS服务高可用方案&#xff0c;可以解决静态路由出现的单点故障问题。 在一个LVS服务集群中通常有主服务器&#xff08;MASTER&#xff09;和备份服务器&#xff08;BACKUP&#xff09;两种角色…
阅读更多...
【qt信号槽-5】信号槽相关注意事项记录

【qt信号槽-5】信号槽相关注意事项记录

背景&#xff1a; 信号槽是qt很重要的概念&#xff0c;遇到问题帮助没少看。其中就有signals and slots这一章节&#xff0c;说得很到位。 概念琐碎&#xff0c;记录备忘。不对之处望指正。 【qt信号槽-1】槽函数重写问题&#xff0c;qt_metacall和qt_static_metacall-CSDN博…
阅读更多...
12.19力扣

12.19力扣

1901. 寻找峰值 II 题目描述&#xff1a;   一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。   给你一个 从 0 开始编号 的 m x n 矩阵 mat &#xff0c;其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 […
阅读更多...
docker-compose部署容器可视化管理平台portainer

docker-compose部署容器可视化管理平台portainer

一、安装docker docker--安装docker-ce-CSDN博客 二、安装docker-compose 安装docker-compose-CSDN博客 三、docker-compose部署portainer yml文件&#xff0c;需要开放9000端口 [rootlgb /]# vi /opt/docker-compose-yml/portainer/docker-compose.yml version: "…
阅读更多...
最新文章

Copyright @ 2022~2023