【免费】山东大学软件学院算法设计与分析2024年以前的部分往年题总结附答案资源-CSDN文库

需积分: 0 122 浏览量 2024-06-14 16:16:11 上传评论 1 收藏 1.91MB DOCX 举报

资源推荐

资源详情

资源评论

1. Floyd - Warshall 算法，简述算法思想，分析时间复杂度。

算法思想:

Floyd-Warshall 算法基于动态规划思想，它维护一个二维的数组 d，其中 d[i][j]

表示从顶点 i 到顶点 j 的最短路径长度。算法的核心思想是动态规划转移方程，

假设 k 为中间节点，如果从 i 到 j 的路径经过中间节点 k，则有:

d[i][j] = min(d[i][j], d[i][k]+d[k][j])

该式的意思是，如果从 i 到 j 的路径经过 k 的话，那么 i 到 j 的最短路径长度

就可以通过 i 到 k 的最短路径长度加上 k 到 j 的最短路径长度得到。通过枚举

所有的 k，我们可以逐步计算出 d 数组的所有值，从而得到任意两个顶点之间的

最短路径。

时间复杂度:

Floyd-Warshall 算法的时间复杂度为 O(n^3)，其中 n 为图的顶点数。这是因为

算法需要三重循环来枚举 i、j 和 k，每一次循环需要 O(1)的时间来更新

d[i][j]。因此，总时间复杂度为 O(n^3)。

2. 使用动态规划求解：一个字符串允许出现的字符可以是 a、b 或 c，求长度为

n 且不包括两个连续 a 的字符串个数。简述算法思想，写出伪代码，分析时间复

杂度、空间复杂度。

动态规划的思想来解决。我们定义一个状态数组 dp[i]，表示长度为 i 的字符串

中不包含两个连续的 a 的字符串的个数。对于第 i 个字符，若他是 b,c 则第 i-1

个字符可以是任意一个，若是 a，第 i-2 可以是任意字符，但第 i-1 可以是 b

或 c。因此，对于第 i 个字符，它可以为 b 或 c，也可以为 a(前面必须是 b 或

c)，因此可以得到递推式:

dp[i]= (dp[i-1] + dp[i-2])*2，其中 dp[1]=3,dp[2]=8。

dp[1] = 3

dp[2] = 8

for i = 3 to n

dp[i] = (dp[i-1] + dp[i-2])*2

return dp[n]

3. 使用动态规划求解：x 的初值为 1，每一步可对 x 进行加 1 或乘 2 的操作，求

对一个大于 0 的整数 n 来说，x 经过操作后等于 n 所需的最小步数。写出 Bellman

方程，伪代码。

多项式归约:指的是将一个问题转化为另一个问题的过程，使得对原问题的解可

以直接通过解决转化后的问题来获得。如果一个问题可以在多项式时间内归约

到另一个问题，那么它被认为是多项式归约可解的。

6. 求单源最长路径，要求使用动态规划算法(bellman-ford 算法即可)，写出伪

代码，时间复杂度，思想，动态规划方程。

思想:Bcllman-Ford 算法使用了动态规划的思想，通过多轮松弛操作逐步更新顶

点之间的最长路径。算法首先将源顶点的距离初始化为 0，然后按照拓扑排序的

顺序依次遍历每个顶点。对于每个顶点，我们通过比较从前驱顶点到当前顶点

的距离加上边的权重与当前顶点的距离的大小，来更新当前顶点的距离值。经

过|V|-1 轮松弛操作后，所有顶点之间的最长路径长度已经得到计算。

Input:有向加权图 G=(V. E)，源顶点 s

Output:源顶点 s 到图中所有其他顶点的最长路径长度

1.初始化距离数组 dist[]，将源顶点 s 的距离设为 0

2.对于图中的每个顶点 v in V，按照拓扑排序的顺序执行步骤 3-4

3.对于 v 的每个邻接顶点 u，执行步骤 4:

-如果 dist[v] + weight(v, u) > dist[u]，则更新 dist[u] = dist[v]+ weight(v, u)

4.如果经过一轮松弛操作后，没有发生任何距离的更新，则终止算法

5.返回距离数组 dist[]作为输出结果

时间复杂度:Bellman-Ford 算法的时间复杂度为 O(|V|*|E|)，其中|V|是顶点数，

|E|是边数。由于算法要进行|V|-1 轮松弛操作，每轮松弛操作需要遍历所有的

边，因此总的时间复杂度为 O(|V|*|E|)。

2.给你一个整数数组 nums，请你找出一个具有最大和的连

续子数组（子数组最少包含一个元素），返回其最大和。

（子数组是数组中的一个连续部分）

求一个数组中的最大子数组，利用分治算法，首先第一步

需要做的就是将该数组划分为两个规模相当的子数组

2.第二步就是要分别考虑求解两个子数组的最大子数组，但

是也会出现另外一种情况:原数组的最大子数组可能起始位

置位于 mid 左边，终止位置位于 mid 右边，即 cross_mid,

3.但无论如何，具体情况只可能是以下三种:

（1）最大子数组位于 mid 左边

（2）最大子数组位于 mid 右边

（3）cross_mid

剩余21页未读，继续阅读

内容反馈

real_pcyyyyyyyy

粉丝: 2
资源: 1

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip