以下是为您整理出来关于【算法分析与设计】合集内容，如果觉得还不错，请帮忙转发推荐。
1.问题 对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径，按实验报告模板编写算法。 2.解析 第一点： 第二点：我们已经知道了起点s，一开始对于顶点s各个顶点的距离（用数组dis[j]表示s->j的距离），我们可以通过与顶点s相连的边得知。 假设顶点k，是距离顶点i最近的一个顶点（除去s本身），顶点j是除去i，k以外的一个节点 因此我们知道： dis[k] < dis[j] 再假设 dis[k] + path[k][j] < dis[j] 因此 如果我们先用顶点j去松弛...
第二章 递归算法 1. 递归的定义 若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接或间接的调用自己，则称这个过程是递归的过程。 2. 三种经典情况使用递归 （1）问题的定义是递归的 （2）数据结构是递归的 （3）问题求解的过程是递归的 3. 递归的分类 **直接递归** **间接递归**4. 递归模型第一个式子给出了递归的终止条件，称为递归边界 第二个式子给出了fun(n)的值与fun(n-1)的值之间的...
@ZHANGQIANYI2020 HNUCM-OJ 归并排序，大整数乘法，第k小元素问题，第k大元素问题，前m大数，找中位数 问题 A: 归并排序问题 B: 大整数乘法问题 C: 第k小元素问题问题 D: 第k大元素问题问题 E: 前m大数问题 F: 找中位数 问题 A: 归并排序 （时间限制: 1 Sec 内存限制: 256 MB） 题目描述：编写一个程序，使用分治策略实现二路归并排序（升序）。输入：多组输入，每组第一个数字为数组长度，然后输入一个一维整型数组。输出：输出排...
@ZHANGQIANYI2020 HNUCM-OJ 习题6-6 杨辉三角，小白鼠，放苹果，数字交换，棋盘覆盖问题，整数划分问题之备忘录法 问题 A: 习题6-6 杨辉三角问题 B: 小白鼠问题 C: 放苹果问题 D: 数字交换问题 E: 棋盘覆盖问题问题 F: 整数划分问题之备忘录法 问题 A: 习题6-6 杨辉三角 （时间限制: 1 Sec 内存限制: 12 MB） 题目描述：按要求输出如下格式的杨辉三角 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 最多输出10层。输入：输入只包含...
给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。 要求算法的时间复杂度为O(n)。 输入格式: 输入有两行： 第一行是n值（1<=n<=10000)； 第二行是n个整数。 输出格式: 输出最大子段和。 输入样例: 在这里给出一组输入。例如：6 -2 11 -4 13 -5 -2输出样例: 在这里给出相应的输出。例如：20 该问题可分为两个阶段：①累加...
实验报告 1.问题 二分归并排序：对n个不同的数构成的数组A[1…n]进行排序，其中n=2^k 2.解析3.设计4.分析5.源码 https://github.com/jinkaili-410/kl.github.io/blob/master/project4/project4.cpp
1.问题 写出两种检索算法：在一个排好序的数组T[1…n]中查找x，如果x在T中，输出x在T的下标j；如果x不在T中，输出j=0. 2.解析 顺序查找：这是最简单也是最先想到的算法，但是它的缺陷也很明显，如果要找到的数在数组的末尾，那么要找到这个数就必须遍历一遍数组，当这个数组很大时，找到这个数所要花费的时间是我们无法接受的。二分查找：相较于顺序查找，二分查找是我们所学过的较为快速的一种查找方式，它的操作步骤也很简单，首...
问题 给出一幅有n个顶点，m条边构成的图，求解各个顶点之间的最短距离。 解析 Floyd 算法： Floyd 算法的本质是动态规划。我们考虑两个点之间的最短路径只有两种可能， 第一种：起点直接通过一条路径到达终点。第二种：从一个点出发经过若干个别的点，然后到达终点。 那么我们就可以通过枚举中间点k，去判断是否存在比原来路径更短的路径，即如果 \(dis(i,k)+dis(k,j)<dis(i,j)\)，那么 \(dis(i,j)\) 就可以更新为 \(dis(i,k)+dis(...
目录 实验环境动态规划使用动态规划的特征 1.矩阵连乘问题问题描述解题思路 2.剪绳子问题问题描述解题思路 3.国王和金矿问题描述解题思路 4.最长公共子序列问题描述解题思路实验环境 Windows 10+DEV-C++ 动态规划 动态规划问题是算法设计与分析中的热门话题，如果要求一个问题最优解（通常是最大值或者最小值），而且该问题能够分解成若干个问题，并且小问题之间也存在重叠的子问题，则考虑采用动态规划。 使用动态规划的特征 使用...