算法第2次作业

发表于2025-03-16|更新于2025-03-20|算法设计

|总字数:2k|阅读时长:5分钟|浏览量:

1 不完美字符串问题

对于一个长度为的仅由和构成的字符串，其不完美度定义为所有相邻字符对中互不相同的字符对数量的和。比如，长度为的字符串 “” 的不完美度为，这是由和两个相邻数对贡献得到的。形式化地，字符串的不完美度如下式：

(运算的结果取决于其中布尔表达式的真值。若为假，其值为，若为真，其值为 )

现给定一个长度为的字符串，每一位仅由、和组成。你需要将其中的每一个替换成或者，且最小化字符串的不完美度。

例如，给定的字符串为 “”，一种使不完美度最小的替换方案为 “”，其不完美度为，可以证明，没有其他替换方案，请使用动态规划算法求解最小的不完美度，并给出一个替换方案。请描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。

分析：本问题可以使用动态规划的方法求解，对于长度为的字符串的第个字符，其与前个字符组成的字符串之间的关系会决定前个字符组成的字符串的不完美度与前个字符组成的字符串的不完美度间的关系。当时，；当时，。替换获得最小不完美度字符串时，当位于最左侧时，其应与右侧字符相同；当位于最右侧时，其应与左侧字符相同；当位于两字符之间时，若两字符相同，则其应与左侧字符相同，若两字符不相同，则其不完美度增量至少为，其也应与左侧字符相同。综上，可以获得替换方案：当左侧有字符时，其应与左侧字符相同；当左侧没有字符时，其应与右侧字符相同。如果右侧是字符，则应与第一个非字符相同。
时间复杂度：
伪代码：

2 鲜花组合问题

花店共有种不同颜色的花，其中第种库存有枝，现要从中选出枝花组成一束鲜花。请设计算法计算有多少种组合一束花的方案，请描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。（两种方案不同当且仅当存在一个花的种类，两种方案中第种花的数量不同）

分析：这是一个组合问题，具有最优子结构的特点。在这个问题中，每个问题可以化为子问题。当备选花有种，要选择枝时，可以得到方案数结果为，则当备选花为种时，就可以在此基础上进行进一步状态转移。当这枝花都不选第种时，其方案数与相等；当这枝花选一枝第种花时，其方案数与相等；以此类推，直至这枝花都选第种花，此时方案数即为。所以即可得到，计算即可获得结果。应当指出，当时，前式不成立，而是成立。
时间复杂度：
伪代码：

3 最长公共上升子序列问题

对两个序列和，序列为和的公共上升子序列，当且仅当是和的公共子序列，且是上升子序列（）。

对两个序列和，若某个序列是和的公共上升子序列，且对于任意的和的公共上升子序列，都有，那么称为和的最长公共上升子序列。

例如，给定两个序列和，其一个最长公共上升子序列为。

给定两个长度为的序列和。请设计一个动态规划算法，求它们的最长公共上升子序列的长度。请描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。

分析：对于有序序列 , 其前个元素组成的子序列和前个元素组成的子序列的公共子序列具有关系或。对于备选公共子序列，其主要有两种方式得到，一种是以序列为主序列，在序列中寻找元素匹配序列中最后一个元素，并不断扩展序列长度；另一种是以序列为主序列，在序列中寻找元素匹配序列中最后一个元素，并不断扩展序列长度。最终将这两种公共子序列长度对比即可获得最长公共子序列。
时间复杂度：最小时间复杂度，最大时间复杂度
伪代码：

4 叠塔问题

给定块积木，编号为到。第块积木的重量为 ( 为整数)，硬度为，价值为。

现要从中选择部分积木垂直摞成一座塔，要求每块积木满足如下条件: 若第块积木在积木塔中，那么在其之上摆放的所有积木的重量之和不能超过第块积木的硬度。

试设计算法求出满足上述条件的价值和最大的积木塔，输出摆放方案和最大价值和。请描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。

分析：首先应对积木进行排序，使得后规划承重能力强的积木。这里的承重能力指。若，规划这两块积木时，将放在上面，放在下面，在上还能放重量的积木；将放在上面，放在下面，在上还能放重量的积木。而，因此此时应该将承重能力更强的2放在下面(后面)。设立二维数组表示前块积木，选取总重量为的积木，搭建的积木塔价值和最大值。对于，当选取第块积木时，其最大值就是；当不选取第块积木时，其最大值就是前块积木，总重量为的积木的最大值。因此，转移方程为。
时间复杂度：，
伪代码：

5 最小划分问题

对一个序列上的某两个数和，若且，则称为一个不同数对。一个序列的不同数对数为序列中所有不同数对的个数之和。例如，序列的不同数对有四个。

给你一个长度为的正整数序列和一个正整数，满足序列中的任意一个数。请你将其划分为个子段，最小化每个子段最小不同数对数相加的和。你只需要回答这个最小的和。

例如，给定序列为和参数，则答案为，对应的一个划分方法为。

请使用动态规划求解该问题，描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。

分析：设立一维数组表示从序列开头到第个元素的不同数对数，设立二维数组表示从序列开头到第个元素与第个元素不同的数对数。对于，从序列第个元素到第个元素的不同数对数等于。为降低时间复杂度，可令。设立二维数组表示长度为，分段数为时的不同数对数（即所有数对的个数）。对于任意的，可以任取一个可分段位置 () ，将前个元素分为个子段，其余个元素作为一个子段，判断这些分段法得出的不同数对数 (即) 的最小值即可。（可选择动态维护此最小值，以降低时间复杂度）
时间复杂度：
伪代码：

文章作者: Mr-MysteryMan

文章链接: http://example.com/2025/03/16/Algorithm/算法第2次作业/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 ENIGMA！

相关推荐

算法第1次作业

请给出 T (n) 尽可能紧凑的渐进上界并予以说明。答案：说明：对于任意，存在，则可以得出。答案：说明：对于任意，存在，则可以得出或，其中。答案：说明：对于任意，存在，则可以得出，进一步可以得到。答案：说明：对于任意，存在，则可以得出，其中。答案：说明：对于任意，存在，则可以得出。答案：说明：对于任意，存在，则可以得出。答案：说明：对于任意，存在。游戏获奖问题在一场射击比赛中，有名选手参加比赛，每名选手的得分都不同，记为，其中第名选手的得分为，且对于任意的有。按照比赛规则，分数排名为前的选手可以获得与其得分相等的奖金（包括第名）。例如，当有名选手参加比赛，得分为时，排名位于前的选手得分为，则主办方应该发放奖金元。请你设计一个算法，计算这次比赛主办方一共要发放多少奖金。请描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。解：该问题即求数组最大的个元素求和值为多少。将数组从大到小按照顺序排序，选取头部个元素求和即可。伪代码如下，时间复杂度在：奇数因子和问题定义...

算法第3次作业

1 医院排队问题在一个医院中，有个病人排队等待就诊，医院每次只能接诊人。每个病人有一个病情严重度，不同病人的病情严重度可以相同。越大表示病情越严重，病情越严重的病人应当越优先就诊，形式化地说：对于任意两个病人,，如果接诊顺序，那么一定有。同时，每个病人还需要一定的时间来完成就诊。记每个病人在排队时的等待时间为，即从第一个人开始看病，到自己看完病为止的时间。请你安排病人接诊的顺序，在关注病人病情严重程度的前提下最小化总的等待时间。例如，有 , , 号三位病人前来就诊，，那么就诊顺序应该安排为号 - 号 - 号，总等待时间为。请设计一个高效算法，描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。分析：这是一个最优化队列问题。根据题目限制，病人病情严重程度具有排列的最高优先级，首先对进行排序。剩余个病人时，病情相同的情况下，接诊病人，总等待时间增加。因此，在病情相同的时候，应优先治疗就诊时间短的病人。因此，整体思路是以病情严重程度为高优先级标准，就诊时间为低优先级标准，同时对病人排序，获得接诊顺序 ...

算法第4次作业

1 判断正误对下面的每个描述，请判断其是正确或错误，或无法判断正误。对于你判为错误的描述，请说明它为什么是错的。如果一个问题是 NP-Hard 问题，那么它一定是 NP 问题。 P 问题 ∩ NPC 问题 = 。若 TSP 问题无法在多项式时间内被解决，则 3-SAT 问题也无法在多项式时间内被解决。对某问题 X NP 而言，若可以证明规约式 3-SAT X ，则 X NPC 。分析：错误。所有的 NP 问题都能约化到 NP-Hard 问题，但是 NP-Hard 问题不一定是一个 NP 问题。 NP 问题可在多项式时间内验证其解正确性，而 NP-Hard 问题则不一定。无法确定。P 问题指可以在多项式时间内解决的问题，而 NP 完全问题指可以在多项式时间内转化的 NP 问题。目前无法证明 P 问题与 NP 问题之间的关系，若 P = NP 那么 P = NPC，P 问题 ∩ NPC 问题 = 。正确。TSP（旅行商问题）和 3-SAT（三可满足性问题）都属于 NP 完全问题，按照 NP 完全问题的性质，如果一种 NP...

数据加载中