四川大学算法设计.pdf

  1. 1、本文档共18页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
四川大学算法设计

《算法设计》课程报告 课序号: 学 号: 104304XXXX 姓 名: XXX 任课教师: 陈瑜 评阅成绩: 评阅意见: 提交报告时间:2012年 6 月 4 日 一、动态规划 1、 问题描述 下图是个数字三角,请编写一个程序计算从顶部至底部某处一条路径,使得该路径所经 过的数字总和最大。 7 3 8 8 1 0 2 7 4 4 1. 每一步可沿左斜线向下或右斜线向下走; 2. 1 三角形行数 100 3. 三角形中的数字为整数 0,1,……,99。 4. 如果有多种情况结果都最大,任意输出一种即可。 输入: 第一行一个整数N,代表三角形的行数。 接下来N行,描述了一个数字三角。 输出: 第一行一个整数,代表路径所经过底数字总和。 第二行N个数,代表所经过的数字。 2、 算法分析 很裸的DP,一个点的最优选择只能从下面和斜下面产生,所可以从最下的一层反面推到, 并且中间用二维数组进行0或者1标记表示选择的是那个,以便查询路径。 动态啊规划转移方程:dp[i-1][j] max(dp[i][j],dp[i][j+1]); 3、 核心代码 #includeiostream #includecstring #includecstdio using namespace std; int num[100][100]; int mid[100][100]; int mm[100][100]; int n; void slove() { int i,j; memset(mid,0,sizeof(mid)); for(i n-1;i 0;i--) for(j 0;ji;j++) { if(num[i][j]num[i][j+1]) {mid[i-1][j] j+1; num[i-1][j]+ num[i][j+1]; } else { mid[i-1][j] j; num[i-1][j]+ num[i][j]; } } coutnum[0][0]endl; j 0; for(i 0;in-1;i++) { coutmm[i][j] ; j mid[i][j]; } coutnum[i][j]endl; } int main() { int i; int j; while(scanf(%d,n) 1) { memset(num,0,sizeof(num)); for(i 0;in;i++) for(j 0;j i;j++) {scanf(%d,num[i]+j);mm[i][j] num[i][j];} slove(); } } 4、 测试数据 5、 算法复杂度分析 时间复杂度O(n) n+(n-1)+…+1 n*(n-1)/2; 即时间复杂度为O(n^2) 空间复杂度为 T(n) 3*(n^2); 6、 和其他算法比较 很裸的一个动态题目,效率一般,还可以在空间上加以优化,即储存路径的空间可以优 化一下,省出一定的空间。 二、二分有哪些信誉好的足球投注网站 1. 问题描述 1.1问题概述 Lumberjack Mirko needs to chop down M metres of wood. It is an easy job for him since he has a nifty new woodcutting machine that can take down forests like wildfire. However, Mirko is only allowed

文档评论(0)

yaocen + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档