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

第8次作业答案
16.1-1

16.1-2

16.2-2

16.2-4

16.3-2
33D:\编程开发\VS2010\myProgram\经典算法大全\练手题1_整数划分\Interger_Partition\Interger_Partition
54D:\编程开发\VS2010\myProgram\经典算法大全\练手题1_整数划分\Interger_Partition\Interger_Partition

16.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,a2>or<a5,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=<i<n，如果出现a[0]+a[1]+…+a[i]>i,则说明A不独立，否则A独立。
伪代码：
inttemp=0;
for(i=0;i<n;i++)a[i]=0;******O(n)=O(|A|)
for(i=0;i<n;i++)a[di]++;******O(n)=O(|A|)
for(i=0;i<n;i++)******O(n)=O(|A|)
{
temp+=a[i];//temp就是a[0]+a[1]+…+a[i]
if（temp>i）//Ni(A)>i
A不独立；}
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个操作的平摊代价：

17.3-2
题目：

答案：
第一步：此题关键是定义势能函数,不管定义成什么首先要满足两个条件
对所有操作i，>=0且>=
比如令，j,k均为整数且取尽可能大，设势能函数=2k;
第二步：求平摊代价，公式是
按上面设置的势函数示例：
当k=0，=…=2
当k！=0,=…=3
显然，平摊代价为O(1)
17.3-4
题目：

答案：
结合课本p249，p250页对栈操作的分析很容易有下面结果

17.4-3
题目：

答案：
假设第i个操作是TABLE_DELETE,考虑装载因子=(第i次循环之后的表中的entry数)/(第i次循环后的表的大小)=

第12次参考答案
19.1.1
题目：

答案：
如果x不是根，则degree[sibling[x]]=degree[child[x]]=degree[x]-1
如果x是根，则sibling为二项堆中下一个二项树的根，因为二项堆中根链是按根的度数递增排序，因此degree[sibling[x]]>degree[x]
19.1.2
题目：

答案：
如果x是p[x]的最左子节点，则p[x]为根的子树由两个相同的二项树合并而成，以x为根的子树就是其中一个二项树，另一个以p[x]为根，所以degree[p[x]]=degree[x]+1;
如果x不是