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

2026年《计算机算法设计与分析导论》课后习题附答案1.考虑分治策略在矩阵乘法优化中的应用。给定两个n×n的矩阵A和B（n为2的幂），传统Strassen算法通过将矩阵分块为4个(n/2)×(n/2)子矩阵，构造7次乘法和18次加减法，时间复杂度为O(n^log₂7)。若将分块大小调整为k×k（k为常数且k>2），假设每次分块后需要m次k×k矩阵乘法和c次加减法，推导新算法的时间复杂度递推式，并分析当k=3时是否可能比Strassen算法更优（假设3×3矩阵乘法的最优乘法次数为23次）。答案：设T(n)为n×n矩阵相乘的时间复杂度。当分块为k×k时，n=k^m（m为分治层数），则递推式为T(n)=m×T(n/k)+c×(n²)。对于k=3，假设3×3矩阵乘法需要23次乘法（比直接计算的27次少），则递推式为T(n)=23×T(n/3)+c×n²。根据主定理，当a=23，b=3，f(n)=n²时，比较n^log_ba与f(n)的增长速度：log₃23≈3.15，因此n^3.15增长快于n²，故T(n)=Θ(n^log₃23)≈Θ(n^3.15)。而Strassen算法的时间复杂度为Θ(n^2.81)，因此k=3时分治策略的时间复杂度更高，无法超越Strassen。2.动态规划解决带约束的资源分配问题。某工厂需将100单位资源分配给5条生产线，每条生产线i分配x_i单位资源（x_i≥0且为整数），产生的利润为p_i(x_i)=max{0,5x_ix_i²/10}。要求总利润最大，且任意两条生产线分配的资源差不超过10单位。设计动态规划状态转移方程，并计算最优分配方案。答案：状态定义为dp[i][j][d]，表示前i条生产线分配j单位资源，且第i条生产线分配量与第i-1条的差为d（d∈[-10,10]）时的最大利润。初始条件：i=1时，x₁可取0到100，dp[1][x₁][]=p₁(x₁)（d无意义，设为特殊值）。状态转移：对于i≥2，j从0到100，d从-10到10，枚举前i-1条分配k单位资源，第i-1条分配x_{i-1}=ksum_{1≤t≤i-2}x_t（需满足x_{i-1}≥0），则x_i=jk，需满足|x_ix_{i-1}|≤10。转移方程为dp[i][j][x_ix_{i-1}]=max{dp[i-1][k][d_prev]+p_i(x_i)}，其中k≤j，x_i=j-k≥0，|x_ix_{i-1}|≤10。最终答案为max{dp[5][100][d]|d∈[-10,10]}。通过计算，最优分配为各生产线分配20、20、20、20、20（总资源100，差为0），总利润5×20×55×(20²)/10=500200=300；若允许差10，如25、15、25、15、20，利润为(5×25-625/10)+(5×15-225/10)×2+(5×20-400/10)=(125-62.5)+(75-22.5)×2+(100-40)=62.5+105+60=227.5，小于均匀分配的300，故最优解为各20单位。答案：状态定义为dp[i][j][d]，表示前i条生产线分配j单位资源，且第i条生产线分配量与第i-1条的差为d（d∈[-10,10]）时的最大利润。初始条件：i=1时，x₁可取0到100，dp[1][x₁][]=p₁(x₁)（d无意义，设为特殊值）。状态转移：对于i≥2，j从0到100，d从-10到10，枚举前i-1条分配k单位资源，第i-1条分配x_{i-1}=ksum_{1≤t≤i-2}x_t（需满足x_{i-1}≥0），则x_i=jk，需满足|x_ix_{i-1}|≤10。转移方程为dp[i][j][x_ix_{i-1}]=max{dp[i-1][k][d_prev]+p_i(x_i)}，其中k≤j，x_i=j-k≥0，|x_ix_{i-1}|≤10。最终答案为max{dp[5][100][d]|d∈[-10,10]}。通过计算，最优分配为各生产线分配20、20、20、20、20（总资源100，差为0），总利润5×20×55×(20²)/10=500200=300；若允许差10，如25、15、25、15、20，利润为(5×25-625/10)+(5×15-225/10)×2+(5×20-400/10)=(125-62.5)+(75-22.5)×2+(100-40)=62.5+105+60=227.5，小于均匀分配的300，故最优解为各20单位。3.贪心算法在带权重的区间调度中的应用。某服务器需处理n个任务，每个任务i有开始时间s_i、结束时间e_i和权重w_i（w_i>0），同一时间只能处理一个任务。要求选择任务集合，使得总权重最大且无时间重叠。证明：若按结束时间排序，使用动态规划选择，而贪心策略（每次选当前可选的权重最大任务）不一定能得到最优解，并构造反例。答案：贪心策略的反例：任务A（s=1,e=3,w=3），任务B（s=2,e=4,w=3），任务C（s=1,e=4,w=5）。按结束时间排序为A(3)、B(4)、C(4)。贪心若选当前可选权重最大的任务，初始可选A（w=3）、C（w=5），选C，总权重5；但最优解为选A和B，总权重6。因此贪心策略失败。动态规划方法正确：将任务按结束时间排序，设dp[i]为前i个任务的最大权重，dp[i]=max(dp[i-1],w_i+dp[p(i)])，其中p(i)是最大的j使得e_j≤s_i。对上述例子，排序后A(3)、B(4)、C(4)，p(A)=0，p(B)=1（e_A=3≤s_B=2？不，s_B=2<e_A=3，故p(B)=0），p(C)=0。dp[1]=3，dp[2]=max(3,3+0)=3，dp[3]=max(3,5+0)=5，但实际最优是A+B=6，说明排序需按结束时间升序且正确计算p(i)。正确排序应为A(1-3)、B(2-4)、C(1-4)，p(B)应为0（因s_B=2<e_A=3），p(C)=0，此时动态规划未考虑A和B的重叠，实际A和B重叠（A结束于3，B开始于2），故不能同时选，正确最优解应为选C（权重5）或A（3）或B（3），之前反例构造错误。修正反例：任务A（1-4,w=3），任务B（2-3,w=3），任务C（5-6,w=3）。贪心选当前可选最大权重（A和B可选，权重均3，选A则后续无法选B，总权重3；选B则后续可选C，总权重6）。此时贪心若按权重优先选A则错误，正确贪心应按结束时间排序后动态规划，而单纯选权重最大的贪心策略失败。4.图算法中的带约束最短路径问题。在有向图G=(V,E)中，边(u,v)的权重为时间t_uv，部分节点v有访问限制：必须在时间区间[l_v,r_v]内到达（否则路径无效）。设计算法求解从起点s到终点t的最短有效路径，要求路径上所有节点的到达时间满足其时间窗口。答案：采用改进的Dijkstra算法，状态为(v,a_v)，其中v是节点，a_v是到达v的时间。优先队列按a_v+h(v,t)（h为启发式函数，如到t的最短时间下界）排序。对于每个状态(v,a_v)，若a_v∉[l_v,r_v]（若v有时间窗口），则跳过；否则遍历所有出边(v,u)，计算到达u的时间a_u=a_v+t_vu。若u有时间窗口且a_u∉[l_u,r_u]，则跳过该边；否则若a_u小于当前记录的到达u的最短时间，则更新并加入队列。初始化时，s的到达时间a_s需满足其时间窗口（若有），否则无解。终止条件是取出t节点的状态，此时a_t即为最短时间。时间复杂度为O((V+E)logV)，因每个节点可能有多个到达时间状态，但实际中时间窗口限制可减少状态数。例如，节点v的时间窗口为[5,10]，则只有到达时间在5到10之间的状态有效，其他状态被剪枝。5.NP难问题的近似算法设计。给定集合U={u₁,u₂,...,u_n}，子集族F={S₁,S₂,...,S_m}，每个S_i有代价c_i>0，要求选择k个子集，使得覆盖的元素数最多（覆盖指元素属于至少一个选中的子集）。设计贪心算法并证明其近似比不低于(1-1/e)。答案：贪心算法步骤：初始化未覆盖元素集合T=U，选中集合C=∅。重复k次：选择子集S_i∈F\C，使得|S_i∩T|/c_i最大（若c_i=1则等价于选覆盖最多未覆盖元素的子集），将S_i加入C，T=T\S_i。最终返回C。近似比证明：设最优解覆盖OPT个元素，贪心解覆盖GREEDY个。令O_j为最优解中前j个子集覆盖的新元素数，G_j为贪心第j步覆盖的新元素数。由于贪心每步选的是当前最优，有G_j≥(OPTΣ_{i=1}^{j-1}G_i)/k（因最优解中至少有一个子集在第j步时覆盖至少(OPTΣG_i)/k个新元素）。递推得ΣG_j≥OPT(1(1-1/k)^k)≥OPT(1-1/e)（因(1-1/k)^k≤1/e）。故近似比为(1-1/e)。6.随机化算法在素数检测中的应用。Miller-Rabin素数测试中，对于奇数n>2，写n-1=2^sd（d为奇数），取随机基a∈[2,n-2]，若a^d≡1modn或存在r∈[0,s-1]使得a^(2^rd)≡-1modn，则n可能为素数；否则n为合数。证明：若n是合数，则至少3/4的a会使其被判定为合数（即n是强伪素数的概率≤1/4）。6.随机化算法在素数检测中的应用。Miller-Rabin素数测试中，对于奇数n>2，写n-1=2^sd（d为奇数），取随机基a∈[2,n-2]，若a^d≡1modn或存在r∈[0,s-1]使得a^(2^rd)≡-1modn，则n可能为素数；否则n为合数。证明：若n是合数，则至少3/4的a会使其被判定为合数（即n是强伪素数的概率≤1/4）。答案：设n为奇合数，称a为“证人”若a使n被判定为合数。需证证人数量≥3(n-3)/4。令G为模n的乘法群，阶为φ(n)（n为合数时φ(n)<n-1）。设H为所有a∈G满足a^d≡1modn或存在r∈[0,s-1]使得a^(2^rd)≡-1modn的集合。H是G的子群。若n是Carmichael数（即对所有a与n互质，a^(n-1)≡1modn），则a^d的阶整除2^s。设最大的r使得存在a∈G满足a^(2^rd)≡-1modn，则H的大小≤2^rt，其中t是满足a^d≡1的元素数。由于n是合数，存在至少一个素因子p，其指数e≥1，且p-1整除n-1=2^sd。若p²|n，则G非循环，H的大小≤φ(n)/2。若n为不同素数乘积，如n=pq，p≡q≡3mod4，s=1，d=(p-1)(q-1)/4，则H中元素满足a^d≡1或a^d≡-1modn，共4个元素（因模p和模q各有两个解），而G的大小为(p-1)(q-1)≥44=16，故H的大小≤4，证人数量≥16-4=12≥316/4=12，符合3/4下界。一般情况下，H的阶≤φ(n)/4，故证人比例≥11/4=3/4。答案：设n为奇合数，称a为“证人”若a使n被判定为合数。需证证人数量≥3(n-3)/4。令G为模n的乘法群，阶为φ(n)（n为合数时φ(n)<n-1）。设H为所有a∈G满足a^d≡1modn或存在r∈[0,s-1]使得a^(2^rd)≡-1modn的集合。H是G的子群。若n是Carmichael数（即对所有a与n互质，a^(n-1)≡1modn），则a^d的阶整除2^s。设最大的r使得存在a∈G满足a^(2^rd)≡-1modn，则H的大小≤2^rt，其中t是满足a^d≡1的元素数。由于n是合数，存在至少一个素因子p，其指数e≥1，且p-1整除n-1=2^sd。若p²|n，则G非循环，H的大小≤φ(n)/2。若n为不同素数乘积，如n=pq，p≡q≡3mod4，s=1，d=(p-1)(q-1)/4，则H中元素满足a^d≡1或a^d≡-1modn，共4个元素（因模p和模q各有两个解），而G的大小为(p-1)(q-1)≥44=16，故H的大小≤4，证人数量≥16-4=12≥316/4=12，符合3/4下界。一般情况下，H的阶≤φ(n)/4，故证人比例≥11/4=3/4。7.回溯算法求解带冲突约束的排列问题。n个任务需排列顺序，任务i和j有冲突c_ij∈{0,1}（c_ij=1表示i和j不能相邻）。设计回溯算法提供所有合法排列，并分析其剪枝策略。答案：回溯框架：维护当前排列path，已选任务集合used。递归函数backtrack(path,used)：若|path|=n，输出path；否则，遍历所有未选任务i∉used，若|path|≥1且c_{path[-1],i}=1则跳过（剪枝），否则将i加入path和used，递归调用backtrack(path+i,used∪{i})，回溯时移除i。剪枝策略：①提前终止：若剩余任务中每个任务都与path末尾任务冲突