头歌 算法 实验七 动态规划

这篇具有很好参考价值的文章主要介绍了头歌 算法 实验七 动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

第1关:数塔问题

300

  • 任务要求
  • 参考答案
  • 评论9
  • 任务描述
  • 相关知识
  • 编程要求
  • 解题思路:
  • 测试说明

任务描述

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

相关知识

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

编程要求

头歌 算法 实验七 动态规划,头歌算法,算法,动态规划

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

解题思路:

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

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

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

 
  1. d[n][j]=data[n][j], j=1,2,……,n;
  2. 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]存储的就是问题的结果。

测试说明

平台会对你编写的代码进行测试:

测试输入:

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

输出示例:

 
  1. max=59
  2. 数值和最大的路径是:9->12->10->18->10

开始你的任务吧,祝你成功!

#include <stdio.h>
int main(){
    int a[50][50][4],i,j,n;
    // printf("Please input the number of rows:\n");
    // scanf("%d",&n);
    n = 5;
    i=1;
    a[1][1][1]=9;
    a[2][1][1]=12, a[2][2][1]=15;
    a[3][1][1]=10, a[3][2][1]=6,  a[3][3][1]=8;
    a[4][1][1]=2,  a[4][2][1]=18, a[4][3][1]=9,  a[4][4][1]=5;
    a[5][1][1]=19, a[5][2][1]=7,  a[5][3][1]=10, a[5][4][1]=4, a[5][5][1]=16;
    for(i=1;i<=n;i++)
        for(j=1; j<=i; j++)
        {
            a[i][j][2]=a[i][j][1];
            a[i][j][3]=0;
        }
    for(i=n-1; i>=1; i--)
        for(j=1; j<=i; j++)
            if(a[i+1][j][2]>a[i+1][j+1][2])
            {
                 a[i][j][2] = a[i][j][2] + a[i+1][j][2];
                 a[i][j][3] = 0;
            }
            else
            {
                 a[i][j][2] = a[i][j][2] + a[i+1][j+1][2];
                 a[i][j][3] = 1;
            }
            printf("max=%d\n",a[1][1][2]);
            printf("数值和最大的路径是:");
            j=1;
            for(i=1;i<=n-1;i++)
            {
                printf("%d->",a[i][j][1]);
                j = j+a[i][j][3];
            }
            printf("%d\n\n\n",a[n][j][1]);
    return 0;
}

第2关:最长公共子序列

400

  • 任务要求
  • 参考答案
  • 评论9
  • 任务描述
  • 相关知识
  • 编程要求
  • 解题思路:
  • 测试说明

任务描述

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

相关知识

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

编程要求

求字符串序列“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]结果的产生过程,从而逆向构造出最长公共子序列。

测试说明

平台会对你编写的代码进行测试:

测试输入:

 
  1. a=“ABCDBAB”
  2. b=“BDCABA”

输出示例:

 
  1. BCBA

开始你的任务吧,祝你成功!

#include "stdio.h"
#include "string.h"
char a[1000]="ABCDBAB";
char b[1000]="BDCABA";
char str[100];
int c[100][100]; 
int lcs_len()
{   
    int m,n,i,j,lcs;
    m = strlen(a);
    n = strlen(b);
    for(i=0;i<=m;i++) c[i][0]=0;
    for(i=0;i<=n;i++) c[0][i]=0;
    for(i=1;i<=m;i++)
       for(j=1;j<=n;j++)
       {
           if(a[i-1]==b[j-1])
               c[i][j] = c[i-1][j-1]+1;
           else if(c[i-1][j]>=c[i][j-1])
                   c[i][j] = c[i-1][j];
                else
                   c[i][j] = c[i][j-1];
       }
    lcs = c[m][n];
    return lcs; 
}
void build_lcs()
{   
    int k,i=strlen(a),j=strlen(b);
    k = lcs_len();
    str[k]=' ';
    while(k>0)
        if(c[i][j]==c[i-1][j])
            i=i-1;
        else if(c[i][j]==c[i][j-1])
                j=j-1;
             else
             {
                 k=k-1;
                 str[k]=a[i-1];
                 j=j-1;
             }
}
int main()
{  
    build_lcs();
    printf("%s",str); 
    return 0;
}

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

300

  • 任务要求
  • 参考答案
  • 评论9
  • 任务描述
  • 相关知识
  • 编程要求
  • 解题思路:
  • 测试说明

任务描述

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

相关知识

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

编程要求

给定由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。

测试说明

平台会对你编写的代码进行测试:

测试输入:

 
  1. 6
  2. -2 11 -4 13 -5 -2

输出示例:

 
  1. 20

开始你的任务吧,祝你成功!

#include <stdio.h>
int maxsubsequence(int n,int a[],int b[],int max)
{
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            b[i] = a[i];
            max = b[i];
        }
        else
        {
            if (b[i - 1] <= 0)
                b[i] = a[i];
            else
                b[i] = b[i - 1] + a[i];
            if (b[i] > max)
                max = b[i];
        }
    }
    return max;
}
int main()
{
    int n;
    scanf("%d",&n);
    int a[1000];
    for (int i = 0; i < n; i++)
        scanf("%d",&a[i]);
    int b[100],max = 0;
    max = maxsubsequence(n, a, b, max);
    printf("%d",max);
}

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

400

  • 任务要求
  • 参考答案
  • 评论9
  • 任务描述
  • 相关知识
  • 编程要求
  • 解题思路:
  • 测试说明

任务描述

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

相关知识

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

编程要求

给定一个长度为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),找出最大值即为最大递增子序列。

测试说明

平台会对你编写的代码进行测试:

测试输入:

 
  1. 10
  2. 3 18 7 14 10 12 23 41 16 24

输出示例:

 
  1. 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关:矩阵连乘问题

400

  • 任务要求
  • 参考答案
  • 评论9
  • 任务描述
  • 相关知识
  • 编程要求
  • 测试说明

任务描述

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

相关知识

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

编程要求

将矩阵连乘积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−1​pk​pj​} 其中,矩阵Ai​的矩阵数为pi−1​×pi​ 矩阵A1​的维度:p0​p1​=3035 矩阵A2​的维度:p1​p2​=3515 矩阵A3​的维度:p2​p3​=155 矩阵A4​的维度:p3​p4​=510 矩阵A5​的维度:p4​p5​=1020 矩阵A6​的维度:p5​p6​=2025 求这6个矩阵连乘的最小相乘次数。

测试说明

平台会对你编写的代码进行测试:

测试输入:

 
  1. 6
  2. 30 35
  3. 35 15
  4. 15 5
  5. 5 10
  6. 10 20
  7. 20 25

输出示例:

 
  1. m[1][6]=15125

开始你的任务吧,祝你成功!文章来源地址https://www.toymoban.com/news/detail-851190.html

#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 **********/

到了这里,关于头歌 算法 实验七 动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法设计与分析实验---动态规划

    任务描述 沿着河岸摆放 N 堆石子,现要将石子有次序地合并成一堆,规定每次只能选相邻的 2 堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。 例如: 4 堆石子 4,5,9,4 ,可以按 (((4,5),9),4) 合并。 第一次合并得分是 9 分,合并之后石子堆是 9,9,4 第二次合并得

    2024年02月08日
    浏览(47)
  • 算法设计与分析 实验三 动态规划

    1.打家劫舍:  给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 入: 每组测试案例有两行,第一行只有一个整数N,代表着有N间房屋 第二行有N个整数,代表着每间房屋里的金额,金额范围[0, 1000]。 出:

    2024年01月24日
    浏览(76)
  • 算法设计与分析实验:动态规划与贪心

    目录 一、零钱兑换 1.1 思路一:动态规划 1.2 思路二:贪心 二、安排工作以达到最大效益 2.1 具体思路 2.2 思路呈现 2.3 代码实现 2.4 复杂度分析 2.5 运行结果 三、雇佣k名工人的最低成本 3.1 具体思路 3.2 思路展示 3.3 代码实现 3.4 复杂度分析 3.5 运行结果 结尾语 “生活有意思的

    2024年02月19日
    浏览(64)
  • 【Python算法】实验12-动态规划与背包问题

    目录 实验内容 1.数塔dp -A 2.骨牌铺方格 3.一只小蜜蜂

    2024年02月15日
    浏览(40)
  • 【Python算法】实验8-动态规划与背包问题

    目录 实验内容 1.数塔dp -A 2.骨牌铺方格 3.一只小蜜蜂

    2023年04月19日
    浏览(66)
  • 南邮|算法分析与设计实验二 动态规划法

    目录 实验目的 实验内容 实验步骤 一、最长公共子序列 二、矩阵连乘  加深对动态规划法的算法原理及实现过程的理解,学习用动态规划法解决实际应用中的 最长公共子序列问题 和 矩阵连乘问题 ,体会 动态规划法 和 备忘录方法 的异同。 一、用动态规划法和备忘录方法

    2024年02月01日
    浏览(42)
  • 湘潭大学 算法设计与分析实验 回溯 动态规划 贪心 模拟退火解决背包问题

    https://download.csdn.net/download/SQ_ZengYX/88620871 测试用例

    2024年02月02日
    浏览(58)
  • 算法设计与分析实验二:动态规划法求解TSP问题和01背包问题

    【实验内容】 (1)tsp问题:利用动态规划算法编程求解TSP问题,并进行时间复杂性分析。 输入:n个城市,权值,任选一个城市出发; 输出:以表格形式输出结果,并给出向量解和最短路径长度。 (2)01背包问题:利用动态规划算法编程求解0-1背包问题,并进行时间复杂性分

    2024年02月03日
    浏览(55)
  • 【计算机网络实验】实验三 IP网络规划与路由设计(头歌)

    目录 一、知识点 二、实验任务 三、头歌测试 IP子网掩码的两种表示方法    32位IP子网掩码,特点是从高位开始连续都是1,后面是连续的0,它有以下两种表示方法: 传统表示法,如:255.255.255.0 IP前缀(长度),如:24,表示IP地址的前24位是网络位。 节点、网段、广播三种

    2024年02月04日
    浏览(123)
  • 算法设计与分析实验4 :利用动态规划的方法解决子集等和分割判断问题

    实验4  利用动态规划的方法解决子集等和分割判断问题 一、实验目的 1. 了解动态规划的主要思想。 2. 掌握背包问题解决方法用以解决该问题。 3. 分析核心代码的时间复杂度和空间复杂度。 二、实验内容和要求 题目:给定一个只包含正整数的非空数组。是否可以将这个数组

    2024年04月23日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包