算法设计练习题
一. 计算复杂性
1． P184 10.3 设计一个多项式时间的算法判断一个无向图G是否是2可着色的
算法：2-COLORING 输入：无向图G(V, E)
输出：该图是2可着色的，则输出yes；否则，输出no. 1.取任一节点，标记为白色
2.所有与它邻接的节点标记为黑色
3.对任意已标记的节点v，将所有与v邻接且未标记的节点标记为与v相反的颜色 4.重复步骤3，直到不存在与已标记节点邻接且还未标记的节点
5.如果图中还有未标记的节点，那么这些节点一定在一个新的连通分量中，再选 择其中一个节点标记为白色，转到步骤3
6.如果得到的图中，所有邻接的节点都标记为不同的颜色，则输出yes；否则，输出no.
End 2-COLORING 时间复杂度分析：在n个顶点和m条边的图上进行分析，算法的运行时间是?(m?n)
2． P185-186 10.16 团集问题的NP完全性是由可满足性问题归约到它证明的，给出
一个从顶点覆盖到团集的较简单的归约
法1：规约方法：设G=（V，E）是连通无向图，S?V是一个团集当且仅当V?S是G中的一个顶点覆盖。
证明：设e=(u,v)是G中的任意边，S?V是一个团集当且仅当u和v都在S中，即V?S是G中的一个顶点覆盖。
法2：证明：设G=（V，E）是连通无向图，S?V是G中的一个独立集，则S是G的一个团集，独立集∝poly团集。因为顶点覆盖∝poly独立集，根据定理10.3，顶点覆盖∝poly团集。
3． P185-186 10.26 用顶点覆盖问题规约到集合覆盖问题，证明集合覆盖问题是NP
完全问题。
证明：第一步是说明集合覆盖问题是NP的。因为一个不确定性算法可以从猜测一个集合X的子集族F开始，然后验证是否存在F中的k个子集的并是集合X。 第二步证明顶点覆盖问题可以在多项式时间内规约到集合覆盖问题。
设任意连通无向图G=(V,E)，集合X为G中所有与边相邻的顶点的集合，其子集族则是每个顶点与其相邻的顶点构成的子集。集合X是满足集合覆盖的当且仅当X的子集族中存在k个子集的并是X，当且仅当G中存在大小为k的顶点覆盖。 4． P215 12.16
证明：设{x1,x2,…,xn}是一个正实数集合。对于每一个实数xi，我们使它和二维平面中的点{ (x1,1),(xj,0) | j∈2,…,n }相联系，这样，所构造的n个点都位于三角形边上。如果我们用TRIANGULATION问题的任何算法求解构造的实例，输出将是根据它们的x坐标排序的构造点的表，遍历表并读出每点的第一个坐标，结果是排序好的
数。所以，排序问题规约到TRIANGULATION问题，排序问题是Ω(n logn)，TRIANGULATION问题也是Ω(n logn)。
5． P215 12.17
证明：设{x1,x2,…,xn}是一个升序排列的正实数集合，及实数x。对于实数x及每一个实数xi，我们使它和二维平面中的点{(x,0),(xi,0) | i∈1,…,n }相联系，这样，所构造的点都位于x轴上。如果我们用NEAREST POINT问题的任何算法求解，输出就是二分搜索要查找的数。所以，二分搜索问题规约到NEAREST POINT问题，二分搜索问题是Ω(logn)，NEAREST POINT问题也是Ω(logn)。
6． P215 12.18
证明：设{x1,x2,…,xn}是一个正实数集合，对于每一个实数xi，我们构造点(xi,0)与之对应，于是这些点在x轴上。如果我们用ALL NEAREST POINT问题的任何算法求解，输出将是每个点(xi,0)对应的最近点对(xi,0)，(xj,0)。所以，CLOSEST-PAIR问题规约到ALL NEAREST POINT问题，CLOSEST-PAIR问题是Ω(n logn)，ALL NEAREST POINT问题也是Ω(n logn)。
二. 随机算法
1． P241 14.2 假定你有一枚硬币，请设计一个有效的随机算法用来生成整数1,2...n
的随机排列，n为正整数，分析你的算法的时间复杂性。
基本思想：从空序列开始，逐个向序列添加1, 2, …, n。根据二分搜索的思想，并利用多次抛硬币，来随机确定每个添加的数在序列中的位置。
算法 RANDOMIZE2 输入：正整数n
输出：1, 2, …, n的一个随机排列。 A[1]=1 for i=2 to n
j=randombisearch(1, i-1)//在数组A中随机确定i的插入位置。 insert(A , j, i) //在数组A的j位置上插入值i。 end for
output A[1..n] end RONDOMIZE2
过程 randombisearch(low, high)
// 利用二分搜索在A[low..high+1]中随机确定值i的插入位置， // 并返回该位置。 if low>high then return low else
mid=??low?high? ?2?? k=random(1,2) //抛一次硬币。
if k=1 then high=mid-1 //插入位置在A[low..mid]中。 else low=mid+1 //插入位置在A[mid+1..high+1]中。
return randombisearch(low, high) end if
end randombisearch 时间复杂性：Θ(n2)
2． P241 14.5 在算法 RANDOMIZEDQUICKSORT的讨论中曾说过，为算法
QUICKSORT得到一个O（log n）期望时间的一种可能性，是通过排列输入元素使它们的次序变成随机的来获得的。描述一个O（n）时间算法，先随机排列下 算法思想：对预排序的数组进行随机排列，使该数组与原先相比显得无序。尽量避免QUICKSORT算法最坏情况的发生即n^2时间，使之更趋近于最佳情况nlogn时间。
算法PRE_DISPOSE
输入：n个元素的数组a[1?n] 输出：随机排列的数组a
for i=1 to n
P =random(n)//随机选择小于n的数 Q=random(n) //随机选择小于n的数 互换a[P]和a[Q] end for
end PRE_DISPOSE
3． P241 14.7 考虑对算法BINARYSERCH做如下修改见1.3节，在每次迭代中，随
机的选择剩下的位置来代替搜索区间减半
设元素存储在一维数组C中，第0个位置不放元素，若每次生成的随机数都是要查找的剩余元素的第一个且未找到要搜索的数，则时间复杂度计算公式如下：
1n?1??C(n)??C(i)?1?ni?0 ?C(0)?0?计算得到时间复杂度为O(logn)
4． 写出n皇后问题的如下随机算法：先在棋盘上随机放置m(m 然后用回溯法搜索其余皇后的位置。 算法 NQUEENS_RAN_ACCU 输入：正整数n,m，其中n表示棋盘纬度，m表示随机算法和回溯算法的处理的 划分， m 输出：若找到解，则输出n皇后问题的一个解x[1..n],否则输出无解 Flag_Random=true //随机查找时是否有解得标记 Flag_Accu=false//精确查找时是否有解得标记 k=1 x[m+1]=0//精确查找初始化 while k<=n and Flag_Random if k<=m//随机算法 j=0 for i=1 to n //寻找第k行所有可放置皇后的位置。 if place(k) then //若第k行的位置i可放置皇后, j++; temp[j]=i; //则存储该位置。 end if end for if j>0 then x[k]=temp[random(1, j)] //随机选取一个位置放皇后 else Flag_Random =false//表示找不到解 end if k++ else if k>m//回溯算法 while k>m and not Flag_Accu while x[k]< n and not Flag_Accu x[k]=x[k]+1 //试将第k行的皇后移到下一个位置。 if place(k) then //第k行的当前位置可放置皇后。 if k=n then Flag_Accu =true //x[m+1..n]是一个解 else //x[m+1..k]是精确解答时的部分解 k=k+1 //前进到下一行 x[k]=0 end if end if //否则，剪枝 end while k=k-1 //回溯 end while if k =m break; //退出整个循环 end if end while if Flag_Random and Flag_Accu then output x //输出一个解 else output “No solution” //输出无解 三. 近似算法 1． 对于装箱问题，分别写出近似算法FF和BF。 思路: 1.最先适配法(FF)：箱子编号为1, 2, ?, n，初始时各箱子为空。各项按u1, u2, ?, un的顺序装箱，装项ui时，将其装入序号最小的可容得下该项的箱子中（即装入满足l<= 1-si的序号最小的箱子中，其中l表示箱子的已填充容量）。 2.最佳适配法(BF)：箱子编号为1, 2, ?, n，初始时各箱子为空。各项按u1, u2, ?, un的顺序装箱，装项ui时，将其装入满足l<= 1-si并且使l值最大的箱子中。 算法FF 输入: n个项的集合u[1?n], n个箱子的容量l[1?n]，其中0<=u[i]<=1，l[i]=1. 输出: 装这n个项的最少箱子的个数k k=1;//箱子的个数 for i=1 to n//装项ui时，将其装入序号最小的可容得下该项的箱子中 j=1 flag=false; while j<=k and not flag//从序号最小的开始查找 if l[j]>u[i] then//找到可以放进去的箱子 l[j]=l[j]-u[i] flag=true; else j++//继续寻找 end if end while if not flag then//没有找到可以放进去的箱子 k++//开启新的箱子 l[k]=l[k]-u[i]; end if end for return k end FF 算法BF 输入: n个项的集合u[1?n], n个箱子的容量l[1?n]，其中0<=u[i]<=1，l[i]=1. 输出:装这n个项的最少箱子的个数k k=1;//箱子的个数 for i=1 to n//装项ui时，将其装入满足l<= 1-si的箱子中使l值最大的箱子中 if l[j]>u[i] then//找到l值最大的可以放进去的箱子 l[j]=l[j]-u[i] else k++//开启新的箱子 l[k]=l[k]-u[i]; end if sort(l[1?k])//对前k个箱子的l值从大到小排序 end for return k end BF 2． P255 15.10 V1 V2 如图： V4 V3 按照算法，先得到顶点的度数降序排列：V1、V2、V3、V4（度数均为2），先将V1添加到覆盖中，删除边{ V1 ，V4}和{ V1，V2}，接着添加V2，删除边{ V2，V3}，添加V3，删除边{ V3，V4}。故得覆盖{ V1，V2，V3}，而最佳覆盖为{ V1，V3}或{ V2，V4}。 3． P256 15.14 15.15（这两题的答案是学长给的） 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法设计练习题在线全文阅读。
相关推荐：