2026年计算机算法设计与分析课后习题附答案

2026年计算机算法设计与分析课后习题附答案1.给定一个长度为n的互不相同的整数数组，其中数组元素满足先严格递增后严格递减的排列规律，即存在唯一的峰值元素，峰值左侧所有元素严格递增，右侧所有元素严格递减，请设计一个时间复杂度低于O(n)的算法找到这个峰值元素的下标，要求给出算法思路、递推式、时间复杂度分析并给出算法实现伪代码。解答：该问题可以通过分治策略中的二分查找实现，满足时间复杂度要求。算法思路：利用数组单峰的有序特性，每次取当前搜索区间的中间位置下标mid，判断mid处元素与相邻元素的大小关系，从而确定峰值所在的区间，不断缩小搜索范围直到找到峰值。具体判断逻辑：若nums[mid]>nums[mid-1]且nums[mid]>nums[mid+1]，则mid就是峰值，直接返回；若nums[mid]>nums[mid-1]，说明mid仍然处于递增区间，峰值必然在mid的右侧区间，因此将左边界更新为mid；若nums[mid]<nums[mid-1]，说明mid已经处于递减区间，峰值必然在mid的左侧区间，因此将右边界更新为mid。问题的规模每次缩小为原来的二分之一，每次比较操作仅需要O(1)时间，因此时间复杂度递推式为T(n)=T(n/2)+O(1)，根据主定理求解可得T(n)=O(logn)，该时间复杂度低于O(n)，满足要求。算法伪代码如下：Input:数组A[0..n-1],长度nOutput:峰值元素下标l=0,r=n-1whilel<r:mid=(l+r)//2ifA[mid]<A[mid+1]:l=mid+1else:r=midreturnl该循环最终会收敛到峰值下标，循环次数不超过log2n，执行效率符合要求。2.某工厂需要加工n个订单，每个订单i的开始时间为s_i，结束时间为f_i，加工该订单可以获得的利润为v_i，同一时间工厂只能加工一个订单，且加工订单不能中断，若选择加工某个订单则必须加工完整，设计算法求解工厂能够获得的最大总利润，要求分析时间复杂度。解答：该问题是带权的活动选择问题，适合用动态规划求解。具体步骤：首先将所有订单按照结束时间从小到大排序，排序后得到满足f_1≤f_2≤...≤f_n的订单序列；定义dp[i]表示前i个订单中能够获得的最大利润，对于第i个订单，存在两种决策：不加工该订单时，最大利润等于前i-1个订单的最大利润，即dp[i]=dp[i-1];加工该订单时，需要找到所有结束时间小于等于该订单开始时间s_i的订单中编号最大的订单，记该编号为p(i)，此时最大利润为dp[p(i)]+v_i。因此状态转移方程为：dp[i]=max(dp[i-1],dp[p(i)]+v_i)，初始状态dp[0]=0，即没有订单时利润为0。由于订单已经按照结束时间排序，寻找p(i)的过程可以通过二分查找完成，单次查找的时间复杂度为O(logi)。整个算法的过程分为两步：第一步对n个订单排序，时间复杂度为O(nlogn)；第二步依次计算每个dp[i]，共n次计算，每次计算包含一次二分查找，时间复杂度为O(nlogn)。因此总的时间复杂度为O(nlogn)，空间复杂度为O(n)，用于存储dp数组和p(i)的值。例如，当n=3，三个订单分别为s1=1,f1=3,v1=5；s2=2,f2=4,v2=6；s3=3,f3=5,v3=5，排序后得到p(1)=0,p(2)=0,p(3)=1，计算得dp[1]=5,dp[2]=6,dp[3]=max(6,5+5=10)，最终最大利润为10，对应选择加工第一个和第三个订单，结果符合实际。3.给定两个字符串X长度为m，Y长度为n，求两个字符串的最长公共子串（子串要求字符连续，区别于不要求连续的子序列）的长度，设计动态规划算法求解，说明状态定义、转移方程、时间空间复杂度，并说明如何对空间复杂度进行优化。解答：采用动态规划求解该问题的过程如下：首先定义状态dp[i][j]表示字符串X的前i个字符中，以第i个字符结尾，字符串Y的前j个字符中，以第j个字符结尾的最长公共子串的长度。状态转移的逻辑：若X的第i个字符（对应下标X[i-1]，字符串下标从0开始）等于Y的第j个字符（对应Y[j-1]），说明当前两个字符可以拼接到之前的公共子串末尾，因此dp[i][j]=dp[i-1][j-1]+1；若两个字符不相等，说明以当前两个字符结尾的公共子串不存在，长度为0，因此dp[i][j]=0。遍历所有i和j计算完dp数组后，取dp数组中的最大值就是整个问题的解。初始状态：dp[0][j]=0，dp[i][0]=0，空字符串结尾不存在公共子串，长度为0。该算法的时间复杂度为O(mn)，需要遍历所有i从0到m，j从0到n，每个状态转移为O(1)操作；原始的空间复杂度为O(mn)，需要存储整个二维dp数组。空间优化的核心思路是，计算当前行dp[i][]的时候，只需要用到上一行dp[i-1][]的值，更具体来说，计算dp[i][j]只需要用到dp[i-1][j-1]也就是左上角的值，因此可以将二维数组压缩为一维数组，长度为min(m+1,n+1)，也就是把较短的字符串作为列方向，每次计算当前行的时候从右向左遍历列，就不会提前覆盖需要用到的左上角值，也可以用一个额外变量存储当前计算需要的左上角值，避免覆盖错误。优化后的空间复杂度为O(min(m,n))，时间复杂度保持O(mn)不变，不会改变计算结果，仅降低空间占用。对于最长公共子串问题，还存在基于后缀数组+二分查找的优化算法，可以将时间复杂度降低到O((m+n)log(min(m,n)))，但该方法不属于动态规划范畴，此处不做展开。4.假设有n种不同面值的硬币，每种硬币的数量无限，现在要凑出总金额S，要求使用的硬币数量最少，请问贪心算法一定能得到最优解吗？如果一定能请证明，如果不一定请给出反例并说明贪心算法在哪种情况下可以保证得到最优解。解答：贪心算法并不能对任意面值系统得到该问题的最优解，此处给出反例：假设现有三种硬币，面值分别为1元、3元、4元，要凑出总金额6元。贪心算法的核心策略是每次选择面值最大的不超过剩余金额的硬币，因此第一步选择最大面值4元，剩余金额为2元，接下来选两个1元，总共得到3枚硬币。但该问题的最优解为选择两个3元，总共只需要2枚硬币，贪心得到的结果差于最优解，因此贪心算法不满足对任意面值系统都正确。贪心算法能够保证得到最优解的情况是当前硬币系统属于典范硬币系统（也叫正则硬币系统），典范硬币系统的核心性质是，对任意金额，贪心选择得到的硬币数量一定不大于任何其他组合的硬币数量。我们日常使用的人民币硬币系统（1角、5角、1元），以及绝大多数国家的流通货币面值系统都属于典范硬币系统，因此日常使用中贪心算法总能得到正确结果。对于任意非典范硬币系统，该问题需要使用动态规划求解，将其转化为完全背包问题，时间复杂度为O(nS)，可以保证得到最优解。5.n皇后问题是在n×n的棋盘上放置n个皇后，要求任意两个皇后不能在同一行、同一列、同一对角线，设计回溯算法求解n皇后问题所有可行解的个数，给出剪枝策略并分析最坏情况下的时间复杂度。解答：n皇后问题的回溯算法基于按行放置的思路设计，由于规则要求任意两个皇后不能同行，因此每行恰好放置一个皇后，我们按行顺序依次放置皇后，每一步尝试所有可能的列位置，通过剪枝排除冲突的分支，直到所有行放置完成后得到一个可行解。剪枝策略核心是提前排除存在冲突的分支，不需要递归向下搜索，具体的冲突分为三类，对应三类剪枝规则：第一，同列冲突：若当前尝试的列已经被之前放置的皇后占用，直接剪去该分支；第二，主对角线（左上到右下方向）冲突：主对角线上所有位置满足行号减列号为常数，因此若该差值已经被占用，直接剪枝；第三，副对角线（右上到左下方向）冲突：副对角线上所有位置满足行号加列号为常数，因此若该和值已经被占用，直接剪枝。为了快速判断冲突，我们可以用三个布尔数组分别标记已经被占用的列、主对角线差值、副对角线和值，每次判断冲突仅需要O(1)时间，不需要遍历所有已经放置的皇后重复检查，大大提升了搜索效率。算法实现的核心逻辑为：初始化可行解计数count=0，初始化三个标记数组全部为未占用，定义回溯函数backtrack(row)表示当前放置第row行的皇后，若row等于n说明所有行放置完成，count加一后返回；否则遍历所有列col，若当前col、对应的主对角线、对应的副对角线都未被占用，则标记三个位置为占用，递归调用backtrack(row+1)，递归返回后取消标记，回溯尝试下一个列位置。最坏情况下，每一行都需要尝试几乎所有列位置，第一行有n种选择，第二行有n-1种选择，第三行有n-2种选择，以此类推，因此最坏情况下的时间复杂度为O(n!)，剪枝策略可以大幅减少实际搜索的节点数，但最坏时间复杂度的上界仍然为O(n!)。6.简述P类问题、NP类问题、NP完全问题、NP难问题的定义，并说明四者之间的关系，同时举例说明每个类别。解答：P类问题是所有可以在确定性图灵机上用多项式时间求解的判定问题，换句话说，P类问题是存在多项式时间精确算法的问题，常见的例子包括单源最短路径问题、数组排序问题、判断一个整数是否为偶数，都属于P类问题。NP类问题是所有可以在非确定性图灵机上用多项式时间求解的判定问题，该定义等价于：对于问题的任意一个候选解，都可以在多项式时间内验证该候选解是否正确，这个等价定义更易于理解。所有P类问题都属于NP类问题，因为如果可以多项式时间求解，自然可以多项式时间验证候选解，常见的NP类问题例子包括哈密顿回路判定问题（给定一个无向图，问是否存在经过每个顶点恰好一次的回路），找解非常困难，但验证一个给定回路是否满足条件只需要线性时间，因此属于NP类。NP完全问题（简称NPC问题）需要满足两个条件：第一，该问题本身属于NP类问题；第二，所有NP类问题都可以在多项式时间规约到该问题，也就是任何NP问题都可以转化为这个问题的一个实例，因此只要任意一个NP完全问题找到了多项式时间算法，所有NP问题都可以用多项式时间求解，也就是P=NP成立。常见的NP完全问题例子包括3-SAT问题、子集和问题、旅行商问题的判定版本，都属于NP完全问题。NP难问题是满足所有NP问题都可以多项式时间规约到它，但本身不一定属于NP类问题的问题，也就是说NP难问题的难度不低于NP完全问题，甚至更难，常见的例子包括停机问题、旅行商问题的优化版本（求最短长度的哈密顿回路），都属于NP难问题。四者之间的关系可以总结为：在普遍被接受的P≠NP猜想下，P是NP的真子集，所有P问题都不是NP完全问题，NP完全问题也是NP的真子集，所有NP完全问题都是NP难问题，NP难问题包含所有NP完全问题和不在NP中的难问题，也就是关系可以表示为：P⊂NPC⊂NP⊂NP难，其中NP完全问题是NP和NP难的交集，不存在属于P的NP完全问题（若P≠NP成立）。目前既存在被证明既不属于P也不属于NPC的NP问题，比如整数因子分解问题，这类问题属于NP中的中间问题，是计算复杂性理论中重点研究的对象。7.有一个容量为W的背包，有n个物品，第i个物品的重量是w_i，价值是v_i，每个物品最多只能选一次，求背包能够装下的最大总价值，分别说明0-1背包问题的动态规划解法，以及当W比较小的时候和当总价值比较小的时候，两种不同的动态规划优化思路，分别给出对应时间复杂度。解答：0-1背包问题基础动态规划解法的核心思路是基于容量定义状态，具体来说：定义dp[i][j]表示前i个物品中，背包容量不超过j时能够获得的最大总价值，对于第i个物品，存在选和不选两种决策：如果当前容量j小于物品重量w_i，则无法选择该物品，dp[i][j]=dp[i-1][j]；如果j大于等于w_i，则dp[i][j]=max(dp[i-1][j],dp[i-1][j-w_i]+v_i)，也就是在不选和选两种情况中取最大值。初始状态dp[0][j]=0，没有物品时价值为0。通过滚动数组优化空间，可以将二维dp压缩为一维dp，每次从后往前遍历容量，避免重复覆盖，优化后空间复杂度为O(W)，时间复杂度为O(nW)。当W比较小时，这种基于容量的解法非常高效，时间复杂度O(nW)在W不大时可以快速出结果，是最常用的0-1背包解法。当W很大，比如W达到1e9级别，无法开辟长度为W的数组，同时所有物品的价值v_i都是整数，且总价值V=Σv_i不大时，可以采用基于价值的状态定义优化，也就是反转状态的维度。具体来说，定义dp[j]表示凑出总价值恰好为j时，需要的最小背包重量，初始状态dp[0]=0，其余dp[j]初始化为无穷大，表示无法凑出。状态转移逻辑：对于每个物品i，遍历j从当前总价值到v_i，更新dp[j]=min(dp[j],dp[j-v_i]+w_i)，也就是对每个价值j，取不选当前物品和