- 1、本文档共18页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 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)