长春网站建设与健,微商各种软件拿码渠道,Wordpress制作一个时间轴,免费网站在哪下载文章目录 第1关#xff1a;数塔问题任务描述相关知识编程要求解题思路测试说明参考答案 第2关#xff1a;最长公共子序列任务描述相关知识编程要求解题思路#xff1a;测试说明参考答案 第3关#xff1a;求序列-2 11 -4 13 -5 -2的最大子段和任务描述相关知识编程要求解题思… 文章目录 第1关数塔问题任务描述相关知识编程要求解题思路测试说明参考答案 第2关最长公共子序列任务描述相关知识编程要求解题思路测试说明参考答案 第3关求序列-2 11 -4 13 -5 -2的最大子段和任务描述相关知识编程要求解题思路测试说明参考答案 第4关求最长的单调递增子序列长度任务描述相关知识编程要求解题思路测试说明参考答案 第5关矩阵连乘问题任务描述相关知识编程要求测试说明参考答案 第1关数塔问题 任务描述
本关任务编写用动态规划解决数塔问题。
相关知识
为了完成本关任务你需要掌握动态规划。
编程要求 求上图从顶层到顶层的一个路径使路径上的数字和最大。要求输出最大的数字和max和数值和最大的路径。
解题思路
原始信息有层数和数塔中的数据层数用一个整型变量n存储数塔中的数据用二维数组data存储成如下的下三角阵: 912 1510 6 82 18 9 519 7 10 4 16必需用二维数组d存储各阶段的决策结果。二维数组d的存储内容如下、 d[n][j]data[n][j] j1,2,……,nd[i][j]max(d[i1][j]d[i1][j1])data[i][j] in-1,n-2,……1j1,2,……,i 最后d[1][1]存储的就是问题的结果。
测试说明
平台会对你编写的代码进行测试 测试输入
5
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16输出示例
max59
数值和最大的路径是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--) //进行第 i1 层的决策从i 到 1 向上for (j 1; j i1; j) { //每一层有 i1 个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; //本次决策选择下标j1的元素}}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“a0a1…am−1”B“b0b1…bn−1”Z“z0,z1,…,zk−1” 为它们的最长公共子序列。 有以下结论 1如果am−1bn−1,则zk−1am−1bn−1,且“z0,z1,…,zk−2”是“a0,a1,…,am−2”和“b0,b1,…,bn−2”的一个最长公共子序列 2如果am−1bn−1则若zk−1am−1蕴涵“z0z1…zk−1”是“a0,a1,…,am−2”和“b0,b1,…,bn−1”的一个最长公共子序列 3如果am−1bn−1则若zk−1bn−1蕴涵“z0z1…zk−1”是“a0a1…am−1”和“b0b1…bn−2”的一个最长公共子序列。 定义c[i][j]为序列“a0,a1,…,ai−1”和“b0,b1,…,bj−1”的最长公共子序列的长度计算c[i][j]可递归地表述如下 1c[i][j]0 如果i0或j0 2c[i][j]c[i−1][j−1]1 如果i,j0,且a[i−1]b[j−1] 3c[i][j]max(c[i][j−1],c[i−1][j]) 如果i,j0,且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 i0;i7;i) //边界赋值为0 {dp[i][0]0;}for(int i0;i8;i){dp[0][i]0;}// printf(test1%d\n,dp[6][7]);for(int i1;i7;i){for(int j1;j6;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 i7,j6;int count0;while(i0j0){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 icount-1;i0;i--){printf(%c,str[i]);} }第3关求序列-2 11 -4 13 -5 -2的最大子段和
任务描述
本关任务编写用动态规划解决最大子段和问题。
相关知识
为了完成本关任务你需要掌握动态规划。
编程要求
给定由n个整数可能为负数组成的序列a1,a2,……,an, 求该序列的最大子段和。当所有整数均为负数定义其最大子段和为0。
解题思路
定义b[j]max(a[i]a[i1]…a[j])其中1ij并且1jn。那么所求的最大子段和可以表示为max b[j]1jn。 由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])1jn。
测试说明
平台会对你编写的代码进行测试 测试输入
6
-2 11 -4 13 -5 -2输出示例
20参考答案
#include stdio.h
/********** Begin **********/
int main(){int n;scanf(%d,n);int a[n][2];int max0;for(int i0;in;i){scanf(%d,a[i][0]);if(i0){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];}maxmaxa[i][1]?max:a[i][1];}printf(%d,max);return 0;}
/********** End **********/第4关求最长的单调递增子序列长度
任务描述
本关任务编写用动态规划解决求最长的单调递增子序列长度问题。
相关知识
为了完成本关任务你需要掌握动态规划。
编程要求
给定一个长度为n的数组找出一个最长的单调递增子序列不一定连续但是顺序不能乱。例如给定一个长度为7的数组A567128,9则其最长的单调递增子序列为56789长度为5。求318714101223411624的最长的单调递增子序列长度。
解题思路
设长度为n的数组为(a[0]a[1],a[2],…a[n−1])则假定以a[j]结尾的数组序列的最长递增子序列长度为L(j)则L(j)max(L(i))1,ij且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 i0;in;i){scanf(%d,m[i][0]);if(i!0){m[i][1]0;int ki-1;while(k0){if(m[i][0]m[k][0]){if(ki-1){m[i][1]m[k][1]1;m[i][2]k;}else{int maxm[k][1]1;if(maxm[i][1]){m[i][1]max;m[i][2]k; }}}k--;}if(k0m[i][1]0){m[i][1]1;m[i][2]i;}}}int maxm[0][1],j0;for(int i0;in;i){if(m[i][1]max){maxm[i][1];ji;}}printf(%d\n,max);
}
/********** End **********/第5关矩阵连乘问题
任务描述
本关任务编写用动态规划解决矩阵连乘问题。
相关知识
为了完成本关任务你需要掌握动态规划。
编程要求
将矩阵连乘积AiAi1…Aj简记为A[i:j]其中ij。设在矩阵Ak和Ak1之间将矩阵链断开则其相应加括号为(AiAi1…Ak) (Ak1Ak2…Aj)。A[i:j]的计算量等于三部分计算量之和 1A[i:k]的计算量 2A[k1:j]的计算量 3A[i:k]与A[k1:j]相乘的计算量。 设计算A[i:j]所需最少乘积数目为则原问题的最优值为。 当ij时,a[i:j]Ai因此m[i][j]0,i1,⋅⋅⋅,n 当ij时m[i][j]ikjmin{m[i][k]m[k1][j]pi−1pkpj} 其中矩阵Ai的矩阵数为pi−1×pi 矩阵A1的维度p0p13035 矩阵A2的维度p1p23515 矩阵A3的维度p2p3155 矩阵A4的维度p3p4510 矩阵A5的维度p4p51020 矩阵A6的维度p5p62025 求这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 i0;in;i){scanf(%d %d,a[i][0],a[i][1]); }for(int i1;in;i){for(int j0;jn-i;j){b[j][ji]b[j][j]b[j1][ji]a[j][0]*a[j][1]*a[ji][1]; int kj1;for(;kji;k){int tb[j][k]b[k1][ji]a[j][0]*a[k][1]*a[ji][1];if(tb[j][ji]) {b[j][ji]t;}}}}printf(m[%d][%d]%d,1,n,b[0][n-1]);return 0;
}
/********** End **********/
