算法设计与分析—动态规划作业一(头歌实验)

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

第1关:最长上升子序列

任务描述

本关任务:求一个序列的最长上升子序列。

相关知识

最长上升子序列问题

当一个序列Bi满足B1 < B2 < ... < Bs的时候,我们称这个序列是上升的。对于给定的一个序列a1, a2, ..., aN,我们可以在其中找到一些上升的子序列。

现在给你一个序列,请你求出其中最长的上升子序列的长度

比如一个序列1, 7, 3, 5, 9, 4, 8

它的一些上升子序列包括1, 7, 9, 3, 4, 8

而其中最长的上升子序列的长度是4,比如1, 3, 5, 8

解题思路

我们可以将这个问题进行分解:

将“在全数列ak(k=1, 2, 3 … N)中求最长上升子序列”问题,分解成“求以ak(k=1, 2, 3 … N)终点的最长上升子序列的长度"。其中终点的含义为一个上升子序列中最右边的那个数。

为此我们可以使用一个数组maxLen来存放这些信息,maxLen[k]代表以ak为终点的最长上升子序列的长度。

显然,maxLen[1]是等于1的,那么如何通过maxLen[n]maxLen[n + 1]呢?

我们可以知道,对于一个数an+1,它一定能连接到在它之前,且比它小的元素的后面,如果以这个元素为终点的最长上升子序列的长度为k,则新的长度就为k + 1

那么我们就得到:maxLen[n] = max{ maxLen[k], 其中k < n, 且a[k] < a[n]} + 1

这样,我们就可以通过maxLen[1],逐步的得到maxLen[n]了。

大致的程序结构为:

 
  1. maxLen[1] = 1;
  2. for 枚举从2到n,设当前为i
  3. {
  4. 选出maxLen[1]到maxLen[i - 1]中最大,且对应的终点元素比ai要小的值max。
  5. maxLen[i] = max + 1。
  6. }
  7. 输出maxLen中最大的结果

至此程序结构已经大致完成,请你补全代码,完成本关任务。

编程要求

在右侧编辑器中有一个函数MaxUp,它有两个参数arrlen,代表一个数组和它的长度,其中len <= 100

请在这个函数中补充代码,计算并输出arr中最大上升子序列的长度。

输入数据由评测系统读取,并传递给MaxUp函数。具体见测试说明

测试说明

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

测试输入: 7 1 7 3 5 9 4 8

预期输出: 4

每组输入有两行,第一行有一个数n,第二行有n个数,是数组内容。


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

参考代码:

#include <iostream>
using namespace std;
int f[10010];
void MaxUp(int arr[],int len)
{
	int res=0;
    for(int i=0;i<len;i++){
        f[i]=1;
        for(int j=0;j<i;j++){
            if(arr[i]>arr[j])  f[i]=max(f[i],f[j]+1);
        }
        res=max(res,f[i]);
    }
    cout<<res<<endl;
}

第2关:数字三角形

任务描述

本关任务:计算数字三角形的最佳路径和。

数字三角形的最佳路径和

有一个数字三角形,从三角形的顶部到底部有很多条不同的路径,路径上的每一步只能从一个数走到下一层上和它最近左边的数或者右边的数。

对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。请找出最佳路径上的数字之和。

比如对于数字三角形:

 
  1. 7
  2. 3 8
  3. 8 1 0
  4. 2 7 4 4
  5. 4 5 2 6 5

最佳的路径和是:7 + 3 + 8 + 7 + 5 = 30

解题思路

对于这个题,我们也可以用递归方式解决,可以计算出所有的路径和,然后选出其中的最大值,比如:

 
  1. int arr[10][10];
  2. int height; //三角形的高度
  3. int MaxSum(int n,int k)
  4. {
  5. if(n == height - 1)
  6. {
  7. //三角形的底层直接返回节点值
  8. return arr[n][k];
  9. }
  10. //选择下一层的左边一个节点
  11. int v1 = MaxSum(n + 1,k);
  12. //选择下一层的右边一个节点
  13. int v2 = MaxSum(n + 1,k + 1);
  14. //选择两条路径中和最大的那一条
  15. return max(v1,v2) + arr[n][k];
  16. }

通过观察代码可以得出,计算MaxSum(n, k)MaxSum(n, k + 1)时,都需要计算MaxSum(n + 1, k + 1)。这就造成了重复计算,影响了计算效率。

因此我们可以在第一次计算完成后记录MaxSum(n + 1, k + 1)的结果,在之后的计算中直接使用。

可以设置一个数组maxSummaxSum[n][k]代表以第n层第k个节点为时,最佳路径的和。

由于上层数据依赖下层数据,因此我们采用从底向上的计算顺序。

显然对于三角形的底层,maxSum[height - 1][k]就等于对应的节点值,即arr[height - 1][k]

接下来我们思考如何从n + 1maxSum得到nmaxSum

为了取到最大值,那么n层的每个节点的值应该选择与相邻的两个n + 1层节点的值中最大的一个求和,即maxSum[n][k] = max(maxSum[n + 1][k] , maxSum[n + 1][k + 1]) + arr[n][k]

而且我们发现,每一层的maxSum只与下一层maxSum有关,那么我们只需要一个一维数组来存储maxSum即可。

因此得到的大致程序结构如下:

 
  1. 设置maxSum为三角形底层各节点的值
  2. for 遍历层数
  3. {
  4. 遍历maxSum,选出相邻两个元素中最大的一个,加上数字三角形中对应位置的节点值。
  5. 将求出的值写回到maxSum的适当位置
  6. }

至此程序结构已经大致完成,请你补全代码,完成本关任务。

编程要求

右侧编辑器中有一个函数MaxSum,它有两个参数arrwid,其中wid <= 10

arr是一个二维数组,有wid层,第一层(即arr[0])有1个元素,第二层(即arr[1])有2个元素,以此类推。数字三角形每一层的值,是从索引0开始,连续的存放在每一层对应的数组中的。

请你在这个函数中补充代码,计算并输出这个数字三角形的最佳路径和,占一行。具体见测试说明

测试说明

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

预期输入: 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

预期输出: 30

每组输入分为多行,第一行是一个整数wid,下面wid行为三角形的内容。


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

参考代码:

#include <iostream>
#include <algorithm>
using namespace std;
void MaxSum(int arr[][10],int wid)
{
	/**********   Begin   **********/
    for(int i=wid-2;i>=0;i--){
        for(int j=0;j<=i;j++){
            arr[i][j]+=max(arr[i+1][j],arr[i+1][j+1]);
        }
    }
    cout<<arr[0][0]<<endl;
	/**********   End   **********/
}

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

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

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

相关文章

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

    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)
  • 南邮|算法分析与设计实验二 动态规划法

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

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

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

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

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

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

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

    2024年04月23日
    浏览(42)
  • 头歌实验七 动态规划

    本关任务:编写用动态规划解决数塔问题。 相关知识 为了完成本关任务,你需要掌握:动态规划。 编程要求 求上图从顶层到顶层的一个路径,使路径上的数字和最大。要求输出最大的数字和max和数值和最大的路径。   本关任务:编写用动态规划解决最长公共子序列问题。

    2024年02月08日
    浏览(42)
  • 实验-动态规划(头歌实践教学平台-ACM/ICPC培训)

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

    2024年02月04日
    浏览(76)
  • 算法分析与设计--动态规划

    一、动态规划简介 二、动态规划求解步骤 三、动态规划典型应用 数字三角形问题 最大子段和问题 0-1背包问题 四、最长公共子序列问题 动态规划求解 五、总结 算法语言--java语言 动态规划算法通常用于求解具有某种最优性质的问题。动态规划与分治算法类似,其基本思想也

    2024年02月07日
    浏览(71)
  • 算法设计与分析复习--动态规划

    算法设计与分析复习–递归与分治(二) 与分析法类似:将原问题分解为子问题 不同点:不是通过递归的方式,而是自底向上的求解问题 矩阵连乘的次数是左矩阵行列,右矩阵行列取出左右中进行相乘。 由于矩阵乘积需要满足左矩阵列等于右矩阵的行,所以可以用一维数组

    2024年02月04日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包