(沙特版)习题参考答案(四章后)

1、醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:习题习题习题习题4.13A1A2A3A6A7A4A5A8A910111213141516171819醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:(b)元素最大交换次数元素最大交换次数元素最大交换次数元素最大交换次数?A9A5各各各各1次次次次?A4A3各各各各2次次次次?A2最多最多最多最多3次次次次?A1最多最多最多最多4次次次次最多共需最多共需最多共需最多共需16次元素交换次元素交换次元素交换次元素交换4.13另解另解另解另解?考虑第考虑第考虑第考虑第i个节点个节点个节点个节点，其子节点为其子节点为其子节点为其子节点为2i，则最多

2、可交换则最多可交换则最多可交换则最多可交换1次次次次?若子节点有子节点若子节点有子节点若子节点有子节点若子节点有子节点22i,则最多可交换则最多可交换则最多可交换则最多可交换2次次次次?若若若若.有子节点有子节点有子节点有子节点iiii2k,则最多可交换则最多可交换则最多可交换则最多可交换k次次次次?因?有因?有因?有因?有i2k19求出满足?述?等式的最大的求出满足?述?等式的最大的求出满足?述?等式的最大的求出满足?述?等式的最大的k值即可值即可值即可值即可。i=1时时时时,k=4;i=2时时时时,k=3;醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:i=3或或或或4时时时时,k=2

3、;i=59时时时时,k=1;因?最多交换因?最多交换因?最多交换因?最多交换4+3+22+15=16次次次次醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:6.5用分治法求数组用分治法求数组用分治法求数组用分治法求数组A1n元素和元素和元素和元素和，算法的?作空间是多少算法的?作空间是多少算法的?作空间是多少算法的?作空间是多少？输入输入输入输入?数组数组数组数组A1n输出输出输出输出?数组的所有元素之和数组的所有元素之和数组的所有元素之和数组的所有元素之和Aii=1nSUM(low,high)1.ifhigh=lowthen2.returnAlow3.else4.mid(low+high

4、)/25.s1SUM(low,mid)6.s2SUM(mid+1,high)7.returns1+s28.endif醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:?作空间?作空间?作空间?作空间?mid(logn),s14.AlowAhigh5.while(lowhigh6.AhighAlow7.8.Alowx/这时这时这时这时,low=high醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:7.3动态规划法计算?式系数动态规划法计算?式系数动态规划法计算?式系数动态规划法计算?式系数knC，并分析其时间复杂度并分析其时间复杂度并分析其时间复杂度并分析其时间复杂度。1.fori1to

5、n2.Ci,01;Ci,i13.endfor4.fori2ton5.forj1toi-1/min(k,i-1)/例如计算例如计算例如计算例如计算C6,26.Ci,jCi-1,j-1+Ci-1,j7.end8.endfor9.returnCn.k复杂度分析复杂度分析复杂度分析复杂度分析?212(1)(1)2nnijiicnncicci=i-1n-121(n)或或或或醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:212(1)nnijickcckn=kO(nk)8.5硬币的面值为硬币的面值为硬币的面值为硬币的面值为1,2,4,8,.,2k,要兑换的值要兑换的值要兑换的值要兑换的值n2k+1，用

6、贪心算法解用贪心算法解用贪心算法解用贪心算法解这个问题这个问题这个问题这个问题，要求算法复杂度为要求算法复杂度为要求算法复杂度为要求算法复杂度为O(logn)输入输入输入输入?k+1个?同硬币的面值个?同硬币的面值个?同硬币的面值个?同硬币的面值，其中包括单?币其中包括单?币其中包括单?币其中包括单?币?面值为面值为面值为面值为1?输出输出输出输出?若要兑换的值若要兑换的值若要兑换的值若要兑换的值n，给出各个面值硬币的数目给出各个面值硬币的数目给出各个面值硬币的数目给出各个面值硬币的数目num0k1.将将将将k+1个?同的面值按递增?序排列个?同的面值按递增?序排列个?同的面值按递增?序排列个

7、?同的面值按递增?序排列，记为记为记为记为Value0.k2.num0k03.forjkdownto04.numjn/Valuej5.nn-numj成成成成Valuej醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:6.endfor7.returnnum0k醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:8.16修改修改修改修改Dijkstra算法算法算法算法，使它找出最短路径和它的长度使它找出最短路径和它的长度使它找出最短路径和它的长度使它找出最短路径和它的长度。1.X=1;YV-1;10;pre10;2.fory2ton3.ify相邻于相邻于相邻于相邻于1thenylength1,

8、y4.elsey5.endif6.endfor7.forj1ton-18.?yY,使得使得使得使得y为最小的为最小的为最小的为最小的9.XXy10.YY-y11.for?条边?条边?条边?条边(y,w)12.ifwYandy+lengthy,wwthen13.wy+lengthy,w14.prewy醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:14.endif15.endfor16.endfor输出最短路径输出最短路径输出最短路径输出最短路径voidPrintPath(intnode)/输出格式为输出格式为输出格式为输出格式为1nodeif(node=1)print(“1”);elseP

9、rintPath(prenode);/先递归再输出先递归再输出先递归再输出先递归再输出print(“”,node);醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:13.2考虑考虑考虑考虑3着色问题着色问题着色问题着色问题，给出一个算法判断一张图给出一个算法判断一张图给出一个算法判断一张图给出一个算法判断一张图G=(V,E)的的的的3着色向着色向着色向着色向?c1n是否是合法的是否是合法的是否是合法的是否是合法的。输入输入输入输入?图图图图G=(V,E)，向?向?向?向?c1n输出输出输出输出?flag=true若合法着色若合法着色若合法着色若合法着色?否则否则否则否则flag=false

10、2.fori1ton3.ifci04.for(i,j)E5.ifcj0andcj=ci6.returnfalse;7.endif8.endfor9.endif10.endfor11.returntrue醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:13.3考虑考虑考虑考虑3着色问题着色问题着色问题着色问题，给出一个算法判断一张图给出一个算法判断一张图给出一个算法判断一张图给出一个算法判断一张图G=(V,E)的的的的3着色向着色向着色向着色向?c1k是否是是否是是否是是否是部分的部分的部分的部分的。输入输入输入输入?图图图图G=(V,E)，向?向?向?向?c1k输出输出输出输出?true若

11、着色是部分的若着色是部分的若着色是部分的若着色是部分的?否则输出否则输出否则输出否则输出false2.fori1tok3.ifci04.for(i,j)E5.ifjkandcj0andcj=ci6.returnfalse;7.endif8.endfor9.endif10.endfor11.returntrue醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:13.10设计一个回溯算法来生?数字设计一个回溯算法来生?数字设计一个回溯算法来生?数字设计一个回溯算法来生?数字1,2,n的所有排列的所有排列的所有排列的所有排列。输入输入输入输入?数字数字数字数字1,2,n输出输出输出输出?数字数字数

12、字数字1,2,n的所有排列的所有排列的所有排列的所有排列c1,n向?向?向?向?1.fork1ton2.ck03.endfor5.k16.whilek17.whileckn-18.ckck+19.ifc为合法的为合法的为合法的为合法的thenoutputc(andgoto12)10.elseifc为部分解为部分解为部分解为部分解thenkk+111.endwhile12.ck013.kk-1醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:14.endwhile14.7对?分查找算法进行随机化对?分查找算法进行随机化对?分查找算法进行随机化对?分查找算法进行随机化，即?次迭?时即?次迭?时即

13、?次迭?时即?次迭?时，随机选择剩?的随机选择剩?的随机选择剩?的随机选择剩?的?置?替搜索空间?半?置?替搜索空间?半?置?替搜索空间?半?置?替搜索空间?半，假设在假设在假设在假设在low?high之间?个?置被选中的之间?个?置被选中的之间?个?置被选中的之间?个?置被选中的概率都是相同的概率都是相同的概率都是相同的概率都是相同的。比较这种随机化算法?分查找的表现比较这种随机化算法?分查找的表现比较这种随机化算法?分查找的表现比较这种随机化算法?分查找的表现。输入输入输入输入?n个元素的升序数组个元素的升序数组个元素的升序数组个元素的升序数组A1n和元素和元素和元素和元素x输出输出输出输

14、出?若若若若x=Aj,1jn,则输出则输出则输出则输出j,否则输出否则输出否则输出否则输出01.low1;highn;j02.while(lowhigh)and(j=0)3.mid(low+high)/2/midrandom(low,high)4.ifx=Amidthenjmid5.elseifxm2.解解解解?算法设计如?算法设计如?算法设计如?算法设计如?:1.k12.whilekm3.rrandom(1,n)4.ik-15.whilei1andrAi6.ii-17.endwhile8.ifi=09.Akr10.kk+111.endif12.endwhile醉雪醉雪醉雪醉雪-风随心动风随心

15、动风随心动风随心动:复杂度分析如?复杂度分析如?复杂度分析如?复杂度分析如?:?次随机生?一个新元素?次随机生?一个新元素?次随机生?一个新元素?次随机生?一个新元素r，要查找要查找要查找要查找r是否已?出现在已?选定的数字中是否已?出现在已?选定的数字中是否已?出现在已?选定的数字中是否已?出现在已?选定的数字中。设生?第设生?第设生?第设生?第i个有效随机数时个有效随机数时个有效随机数时个有效随机数时，平均要产生平均要产生平均要产生平均要产生E(Xi)次次次次,则复杂度则复杂度则复杂度则复杂度121111(,)0()1().(1)()(1)()(1)(1)mmkkmkmkTnmEXEXmE

16、XkEXnknknknk=+=容易证明容易证明容易证明容易证明，醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:111111(,)(1)1(1)12mmkkmkkkTnmnnnnnnmmknmnmkm=+且有且有且有且有111111(,)(1)1121mmkkmkkkTnmnnnnnnmmknnk=因为因为因为因为m2n,则则则则22()(,)()mTnmm，于是于是于是于是2(,)()Tnmm=醉雪醉雪醉雪醉雪-风随心动风随心动风随心动风随心动:14.16另解另解另解另解?算法设计思路如?算法设计思路如?算法设计思路如?算法设计思路如?:生?一个生?一个生?一个生?一个1,n之间的随机数之间的随机数之间的随机数之间的随机数r，互换互换互换互换Xn和和和和Xr?再生?一个再生?一个再生?一个再生?一个1,n-1之间的随机数之间的随机数之间的随机数之间的随机数r，互换互换互换互换Xn-1和和和和Xr?再生?一个再生?一个再生?一个再生?一个1,n-m+1之间的随机数之间的随机数之间的随机数之间的随机数r，互换互换互换互换Xn-m+1和和和和Xr?返回返回返回