头歌实验七 动态规划

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

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

相关知识

为了完成本关任务,你需要掌握:动态规划。文章来源地址https://www.toymoban.com/news/detail-475218.html

编程要求

头歌实验七 动态规划

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

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

 

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

相关知识

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

编程要求

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

#include <stdio.h>
#include <string.h>
int dp[100][100];
char a[100];
char b[100];
int maxm(int m,int n){
	if(m>n) return m;
	else return n;
}
int main(){
	scanf("%s",a);
	scanf("%s",b);
	int m=strlen(a);
	int n=strlen(b);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(a[i-1]==b[j-1]){
				dp[i][j]=dp[i-1][j-1]+1;
			}
			else{
				dp[i][j]=maxm(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	//bnchdn
	//chdn
	printf("%d",dp[m][n]);
} 

/********** End **********/

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

相关知识

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

编程要求

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

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

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

相关知识

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

编程要求

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

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

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

相关知识

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

#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模板网!

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

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

相关文章

  • 【计算机网络实验】实验三 IP网络规划与路由设计(头歌)

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

    2024年02月04日
    浏览(167)
  • 国开电大《WEB开发基础》形考任务【答案】实验1-5:电商网站前端页面内容编写

    国开电大《WEB开发基础》形考任务1 国开电大《WEB开发基础》形考任务1 国开电大《WEB开发基础》形考任务3 国开电大《WEB开发基础》形考任务4 国开电大《WEB开发基础》形考任务5 作业答案 联系QQ:1603277115 【目标】 根据素材中的设计图,编写网站首页,查询列表页和详情页三

    2024年02月03日
    浏览(72)
  • 独立任务的最优调度问题(动态规划)

    问题描述: 用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai,若由机器B来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些i,有aibi,而对于某些j,j≠i,有ajbj。既不能将一个作业分开由2台机器处理,也没有一台机器能同时处理

    2024年02月04日
    浏览(49)
  • 实验七 动态规划

    第1关:数塔问题 300 任务要求 参考答案 评论9 任务描述 相关知识 编程要求 解题思路: 测试说明 任务描述 本关任务:编写用动态规划解决数塔问题。 相关知识 为了完成本关任务,你需要掌握:动态规划。 编程要求 求上图从顶层到顶层的一个路径,使路径上的数字和最大

    2024年01月25日
    浏览(37)
  • 算法设计与分析实验---动态规划

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

    2024年02月08日
    浏览(51)
  • 动态规划问题实验:数塔问题

    动态规划是一种解决复杂问题的方法,它将一个问题分解为若干个子问题,然后从最简单的子问题开始求解,逐步推导出更复杂的子问题的解,最终得到原问题的最优解。动态规划的关键是找到子问题之间的递推关系,以及确定合适的边界条件和初始值。 数塔问题是一个经典

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

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

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

    目录 一、零钱兑换 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日
    浏览(75)
  • 租用游艇问题 石子合并问题 动态规划实验

    实验名称:                动态规划                          一、实验预习 1、实验目的 1. 理解并掌握动态规划方法的设计思想; 2. 提高应用动态规划方法解决问题和设计算法的能力; 3. 通过编程实现租用游艇问题和石子合并问题,进一步理解动态规划方

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

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

    2023年04月19日
    浏览(81)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包