北邮算法与数据结构习题参考答案.pdfVIP

北邮算法与数据结构习题参考

答案

作业参考答案

一、（带头结点）多项式乘法C=A×B：

voidPolyAdd(listC,listR)//R为单个结点

{

p=C;

while((！p-next)(p-next-expR-exp))p=p-next;

if((p-next)||(p-next-expR-exp))

{R-next=p-next;p-next=R;}else

{p-next-inf+=R-inf;deleteR;

if(!p-next-inf)

{R=p-next;p-next=R-next;deleteR;}

}

}

voidPolyMul(listA,listB,listC)

{

C=newstructnode;C-next=NULL;q=B-next;

While(q)

{

p=A-next;

while(p)

{

r=newstructnode;r-exp=p-exp+q-exp;

r-inf=p-inf*q-inf;PolyAdd(C,r);

p=p-next;

}

q=q-next;

}

}

二、梵塔的移动次数：

已知移动次数迭代公式为：M(n)=2M(n-1)+1

初值为：M(0)=0

则：M(n)=2(2M(n-2)+1)+1

=4M(n-2)+3

=8M(n-3)+7

ii

=2M(n-i)+2–1

nn

若n=i,则M(n-n)=0,故：M(n)=2M(n-n)+2–1

n

=2–1

2

n

所以，梵塔的移动次数为2–1次。

三、简化的背包问题：

voidPack(intm,inti,intt)//初始值为:11t

{

for(k=i;k=n;k++)

{

solution[m]=weight[k];

if(t==weight[k])

{

for(j=1;j=m;j++)coutsolution[j];

coutendl;

}elseif(tweight[k])Pack(m+1,k+1,t-weight[k]);