中科大 算法导论作业答案3

《中科大 算法导论作业答案3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第8次作业答案16.1-116.1-216.2-216.2-416.3-233D:编程开发VS2010myProgram经典算法大全练手题1_整数划分Interger_PartitionInterger_Partition54D:编程开发VS2010myProgram经典算法大全练手题1_整数划分Interger_PartitionInterger_Partition16.3-4第9次参考答案16.2-5贪心算法实现，证明不能少，参考答案：16.4-1证明中要三点：1.有穷非空集合2.遗传性3.交换性第10次作业参考答案16.5-1题目表格：ai12

2、34567di4243146wi10203040506070解答：解法1：使用引理16.12性质（2），按wi单调递减顺序逐次将任务添加至Nt（A），每次添加一个元素后，进行计算，{计算方法：Nt（A）中有i个任务时计算N0(A),…,Ni(A)，其中如果存在Nj(A)>j,则表示最近添加的元素是需要放弃的，从集合中删除}；最后将未放弃的元素按di递增排序，放弃的任务放在所有未放弃任务后面，放弃任务集合内部排序可随意。解法2：设所有n个时间空位都是空的。然后按罚款的单调递减顺序对各个子任务逐个作贪心选择。在考虑任务j时，如果有一个恰处于或前于dj的时间空位仍空着，则将任务j赋与

3、最近的这样的空位，并填入; 如果不存在这样的空位，表示放弃。答案（a1，a2是放弃的）：or划线部分按上表di递增的顺序排即可，答案不唯一16.5-2（直接给个计算例子说的不清不楚的请扣分）题目：本题的意思是在O(

4、A

5、)时间内确定性质2（性质2：对t=0，1，2，…，n，有Nt(A)<=t,Nt(A)表示A中期限不超过t的任务个数）是否成立。解答示例：思想：建立数组a[n],a[i]表示截至时间为i的任务个数，对0=i,则说明A不独立，否

6、则A独立。伪代码：inttemp=0;for(i=0;i

7、A

8、)for(i=0;i

9、A

10、)for(i=0;i

11、A

12、){temp+=a[i];//temp就是a[0]+a[1]+…+a[i]if（temp>i）//Ni(A)>iA不独立；}17.1-1（这题有歧义，不扣分）a)如果StackOperations包括PushPopMultiPush,答案是可以保持,解释和书上的PushPopMultiPop差不多.b)如果是Stack

13、Operations包括PushPopMultiPushMultiPop,答案就是不可以保持,因为MultiPush,MultiPop交替的话,平均就是O(K).17.1-2本题目只要证明可能性，只要说明一种情况下结论成立即可17.2-1第11次作业参考答案17.3-1题目：答案：备注：最后一句话展开：采用新的势函数后对i个操作的平摊代价：17.3-2题目：答案：第一步：此题关键是定义势能函数,不管定义成什么首先要满足两个条件对所有操作i，>=0且>=比如令，j,k均为整数且取尽可能大，设势能函数=2k;第二步：求平摊代价，公式是按上面设置的势函数示例：当k=0，=…=2当k！

14、=0,=…=3显然，平摊代价为O(1)17.3-4题目：答案：结合课本p249，p250页对栈操作的分析很容易有下面结果17.4-3题目：答案：假设第i个操作是TABLE_DELETE,考虑装载因子=(第i次循环之后的表中的entry数)/(第i次循环后的表的大小)=第12次参考答案19.1.1题目：答案：(1)如果x不是根，则degree[sibling[x]]=degree[child[x]]=degree[x]-1(2)如果x是根，则sibling为二项堆中下一个二项树的根，因为二项堆中根链是按根的度数递增排序，因此degree[sibling[x]]>degree[x]

15、19.1.2题目：答案：(1)如果x是p[x]的最左子节点，则p[x]为根的子树由两个相同的二项树合并而成，以x为根的子树就是其中一个二项树，另一个以p[x]为根，所以degree[p[x]]=degree[x]+1;(2)如果x不是p[x]的最左子节点，假设x是p[x]的子节点中自左至右的第i个孩子，则去掉p[x]前i-1个孩子，恰好转换成第一种情况，因而degree[p[x]]=degree[x]+1+（i-1）=degree[x]+i;综上,degree[p[x]]>degree[x]