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

第8次作业答案16.1-116.1-216.2-216.2-416.3-254D:\编程开发\VS2010\myProgram\经典算法大全\练手题1_整数划分\Interger_Partition\Interger_Partition33D:\编程开发\VS2010\myProgram\经典算法大全\练手题1_整数划分\Interger_Partition\Interger_Partition16.3-4第9次参考答案16.2-5贪心算法实现，证明不能少，参考答案：16.4-1证明中要三点：1.有穷非空集合2.遗传性3.交换性第10次作业参考答案16.5-1题目表格：ai1234567di4243146wi10203040506070解答：解法1：使用引理16.12性质（2），按wi单调递减顺序逐次将任务添加至Nt（A），每次添加一个元素后，进行计算，{计算方法：Nt（A）中有i个任务时计算N0(A),…,Ni(A)，其中如果存在Nj(A)j,则表示最近添加的元素是需要放弃的，从集合中删除}；最后将未放弃的元素按di递增排序，放弃的任务放在所有未放弃任务后面，放弃任务集合内部排序可随意。解法2：设所有n个时间空位都是空的。然后按罚款的单调递减顺序对各个子任务逐个作贪心选择。在考虑任务j时，如果有一个恰处于或前于dj的时间空位仍空着，则将任务j赋与最近的这样的空位，并填入;如果不存在这样的空位，表示放弃。答案（a1，a2是放弃的）：a5,a4,a6,a3,a7,a1,a2ora5,a4,a6,a3,a7,a2,a1划线部分按上表di递增的顺序排即可，答案不唯一16.5-2（直接给个计算例子说的不清不楚的请扣分）题目：本题的意思是在O(|A|)时间内确定性质2（性质2：对t=0，1，2，…，n，有Nt(A)=t,Nt(A)表示A中期限不超过t的任务个数）是否成立。解答示例：思想：建立数组a[n],a[i]表示截至时间为i的任务个数，对0=in，如果出现a[0]+a[1]+…+a[i]i,则说明A不独立，否则A独立。伪代码：inttemp=0;for(i=0;in;i++)a[i]=0;******O(n)=O(|A|)for(i=0;in;i++)a[di]++;******O(n)=O(|A|)for(i=0;in;i++)******O(n)=O(|A|){temp+=a[i];//temp就是a[0]+a[1]+…+a[i]if（tempi）//Ni(A)iA不独立；}17.1-1（这题有歧义，不扣分）a)如果StackOperations包括PushPopMultiPush,答案是可以保持,解释和书上的PushPopMultiPop差不多.b)如果是StackOperations包括PushPopMultiPushMultiPop,答案就是不可以保持,因为MultiPush,MultiPop交替的话,平均就是O(K).17.1-2本题目只要证明可能性，只要说明一种情况下结论成立即可17.2-1第11次作业参考答案17.3-1题目：答案：备注：最后一句话展开：采用新的势函数后对i个操作的平摊代价：)1()())1(())(()()(1''^'DiDickDikDicDDcciiiiii17.3-2题目：答案：第一步：此题关键是定义势能函数,不管定义成什么首先要满足两个条件对所有操作i，)(Di=0且)(Di=)(0D比如令kj2i，j,k均为整数且取尽可能大，设势能函数)(Di=2k;第二步：求平摊代价，公式是)1()(^DiDiccii按上面设置的势函数示例：当k=0，^ic=…=2当k！=0,^ic=…=3显然，平摊代价为O(1)17.3-4题目：答案：结合课本p249，p250页对栈操作的分析很容易有下面结果17.4-3题目：答案：假设第i个操作是TABLE_DELETE,考虑装载因子:i=(第i次循环之后的表中的entry数)/(第i次循环后的表的大小)=/iinumsize第12次参考答案19.1.1题目：答案：(1)如果x不是根，则degree[sibling[x]]=degree[child[x]]=degree[x]-1(2)如果x是根，则sibling为二项堆中下一个二项树的根，因为二项堆中根链是按根的度数递增排序，因此degree[sibling[x]]degree[x]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]19.2.2题目：19.2.3题目：19.2.519.2.6第13次作业参考答案20.2-1题目：解答：20.2-3题目：解答：20.3-1题目：答案：20.3-2题目：答案：第14次作业参考答案这一次请大家自己看书处理