实验七动态规划-Toy模板网

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

第1关：数塔问题

300

任务要求
参考答案
评论9

任务描述
相关知识
编程要求
解题思路：
测试说明

任务描述

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

编程要求

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

求上图从顶层到顶层的一个路径，使路径上的数字和最大。要求输出最大的数字和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>
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]结果的产生过程，从而逆向构造出最长公共子序列。

测试说明

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

测试输入：

a=“ABCDBAB”
b=“BDCABA”

输出示例：

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。

测试说明

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

测试输入：

6
-2 11 -4 13 -5 -2

输出示例：

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），找出最大值即为最大递增子序列。

测试说明

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

测试输入：

10
3 18 7 14 10 12 23 41 16 24

输出示例：

开始你的任务吧，祝你成功！

#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−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

开始你的任务吧，祝你成功！文章来源地址https://www.toymoban.com/news/detail-823166.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模板网！

实验七动态规划

第1关：数塔问题

任务描述

相关知识

编程要求

解题思路：

测试说明

第2关：最长公共子序列

任务描述

相关知识

编程要求

解题思路：

测试说明

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

任务描述

相关知识

编程要求

解题思路：

测试说明

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

任务描述

相关知识

编程要求

解题思路：

测试说明

第5关：矩阵连乘问题

任务描述

相关知识

编程要求

测试说明

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

支付宝扫一扫打赏

微信扫一扫打赏

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

二维码1

二维码2

实验七 动态规划

第1关：数塔问题

任务描述

相关知识

编程要求

解题思路：

测试说明

第2关：最长公共子序列

任务描述

相关知识

编程要求

解题思路：

测试说明

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

任务描述

相关知识

编程要求

解题思路：

测试说明

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

任务描述

相关知识

编程要求

解题思路：

测试说明

第5关：矩阵连乘问题

任务描述

相关知识

编程要求

测试说明

相关文章

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

支付宝扫一扫打赏

微信扫一扫打赏

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

二维码1

二维码2

实验七动态规划