资源描述：
《算法课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计技巧与分析课程设计题目一数塔问题问题描述：有如右图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大解决问题所用的方法：动态规划为了求得数塔1的解。我们将数塔1分解为如下的数塔1顶点、数塔2和数塔3数塔1的解=数塔1的顶点+数塔2解与数塔3解的最大值，同理，我们也将数塔2和数塔3分解为更小的数塔4、数塔5、数塔6和数塔7……………当数塔不可再分（仅有一层）时，就是分治的最小单元。现运用动态规划的思想，自底向上求解，并将中间果存储想来以便以后再用。A(1……n,1……n)表示数塔各层数的数字B(1……n,1
2、,……n)用来存储中间结果基于分治的方法，得到递推公式如下：注：i=1……n,j=1……i自底向上求解该问题.算法描述：算法名称：MAXVALUE输入：树塔的层数n和各层的数字A[n][n]输出：最大值和路径C[n]算法实现细节（可以用流程图，伪代码）:18算法设计技巧与分析课程设计1.fori←1ton2.B[n,i]←A[n,i]comment:最下面一层为A[n,j]3.endfor4.fori←n-1to15.forj←1toi+16.B[i,j]←max{B[i+1,j],B[i+1,j+1]}+A[i,j]7.comment:B[i,j]等于下面它下面两个数
3、的最大值加上A[i,j]8.endfor9.endfor10.k←111.C[1]←112.fori←2ton13.ifB[i,k+1]>B[i,k]thenk←k+114.comment:寻找路径，找它下面两个数中最大一个的下标并记录15.endif16.C[i]←k17.endfor18.returnB[1,1]comment：返回最大路径的值算法的时间复杂度算法实例：数据的输入（可以有屏幕截图）数据的输出（可以有屏幕截图）18算法设计技巧与分析课程设计题目二校园导航问题问题描述：设计你所在学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也
4、可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。解决问题所用的方法：贪心算法校园导航问题为最短路径问题。设G=(V,E)是一个每条边有非负长度的无向图，有一点s称为源点，校园导航问题就是要确定从s到V中的一个顶点x的的最短距离。初始时，将顶点集合分为两个集合B={s},C={1……s-1,s+1……n}，每一步中，我们选定源点到它的距离已经得到的一个顶点cC,并将它移入B中。与C中的每个顶点c联系的是标记D[c]，它是只经过B中顶点的最短路径，一旦顶点cC移到B中，与c相邻的每个顶点C的标记就会被更新。这表示找到了经过c到的更短路径。当xC被移入B中时，x的
5、标记就是从源s到顶点x的最短路径。为了方便找出具体的的最短图径，我们将标记矩阵定义为二维矩阵D，第x列的最小值就是源s到顶点x的最小路径。A(1……n,1……n)为无向图的邻接矩阵，我们寻找顶点s到s的最短路径无意义，我们将它到本身的距离定义为无穷大（只是为了方便）如下图：寻找最短路径时，我们选找顶点x列的最小值的行标i，若i不等于s，则再找第i列的最小值所在的行标j，依次下去，直到行标为s时，这条路径就是最短路径。算法描述：算法名称：FINDMIN输入：地点的个数n之间的距离A[i,j]，以及起始点a和终点b输出：最短路径值和其路径算法实现细节（可以用流程图，伪代码）
6、:18算法设计技巧与分析课程设计1.fori←1ton2.C[i]←0comment:初始化路径3.endfor4.fori←1ton5.B[i]←1comment:B[i]记录地点i是否可用6.endfor7.forj←1ton8.D[i,j]←9.endfor10.k←a11.min←012.whilek≠b13.fori←1ton14.ifA[k,i]≠15.thenD[k,j]←A[k,j]+min16.comment:如果A[k,j]不为无穷，则D[k,j]等于A[k,j]加上最小值17.endif18.min←19.forj←1ton20.ifB[j]=0t
7、hencontinue21.endif22.fori←1ton23.ifD[i,j]
