算法分析课后习题解答Word格式文档下载.doc
《算法分析课后习题解答Word格式文档下载.doc》由会员分享，可在线阅读，更多相关《算法分析课后习题解答Word格式文档下载.doc（5页珍藏版）》请在冰点文库上搜索。
Gray码序列的后4个元素（23=8），分别为：
011，111，101，001
是n=2时Gray码四个元素反向后加1，
n=2时Gray码四个元素：
即：
可以看出，Gray码可以用分治策略，递归实现，2n的Gray码可以用2n-1的Gray码构成。
算法描述：
voidGray（typea[],intn）
{chara[];
if（n==1）{a[0]=’0’;
a[1]=’1’;
}
if（n>
1）
{Gray（a[],n-1）;
intk=2n-1-1;
//Gray码的个数，因为数组下标从0开始
inti=k;
for（intx=k;
x>
=0;
x--）
{chary=a[x];
a[x]=y+’0’;
a[i+1]=y+’1’;
i++;
}
}
3-7给定由n个英文单词组成的一段文章，……
设由n个单词组成的一段文章可以表示为A[1:
n]，它的“漂亮打印”方案记为B[1:
n]，构成该最优解的最小空格数（最优值）记为m[1][n]
（1）分析最优解的结构：
A[1:
n]的最优解B[1:
n]，必然在第k个单词处断开，那么A[1:
k]是“漂亮打印”，并且A[k+1:
n]也是“漂亮打印”。
故m[1][n]最小时有m[1][n]=m[1][k]+m[k+1][n]，m[1][k]是A[1:
k]的最小值，m[k+1][n]是A[k+1:
n]的最小值。
因此，原问题的最优解包含其子问题的最优解，具有最优子结构性质。
（2）建立递归关系：
第一行，row=1，最漂亮的打印字符数
最小空格数
第二行，row=2，最漂亮的打印字符数
最小空格数
那么，
设：
sum=i1+k2+……+in+n为文章中字符的总长度，其中i1,i2,……in分别为n个单词的长度，n为单词之间的空格数。
M是一行可以输出的字符数
该文章可能输出的行数约为：
sum/M+1（由于最后一行除外，故可能需处理的行数为sum/M行。
第sum/M行时，row=sum/M
最小空格数
1.当i=j时，A[i:
i]=A[i]，m[i][j]=0，表示一个单词，没有空格。
2.当i<
j时，利用最优子结构性质计算m[i][j]
若A[i:
j]的最优解在Ak和Ak+1处断开，i<
=k<
j，则
m[i][j]=min{m[i][k]+m[k+1][j]}，此时，k只有j-i中可能，k是使m[i][j]达到最小的那个位置。
从而m[i][j]可以递归地定义为：
m[i][j]=//上面两个式子
m[i][j]给出了最优值，即A[i:
j]的最小空格数
若将对应于m[i][j]的断开位置k记为s[i][j]，在计算出最优值m[i][j]后，可递归地由s[i][j]构造出相应的最优解
（3）计算最优值
算法：
voidf（intn,int**m,int**s,intsum,intM）
{for（inti=1;
i<
=n;
i++）m[i][j]=0;
for（introw=1;
row<
=sum/M;
row++）
{i=1;
for（intr=2;
r<
r++）
{j=i+r-1;
m[i][j]=row*M-j+row-（i1+i2+……ik）
if（m[i][j]<
0）break;
s[i][j]=j;
for（intk=i+1;
k<
j）;
k++）
{t=m[i][k]+m[k+1][j];
if（t<
m[i][j]）{m[i][j]=t;
s[i][j]=k;
}
};
x=j-1;
（4）构造最优解
算法描述：
voidT（int*B,int**s,intx）
{y=1;
do
b[y]=s[1][x];
x=b[y];
y=y+1;
while（x<
>
1）
do
printf（“%d,”,b[y]）;
y--;
while（y>
0）
}
4-26求极差M=max-min
解：
该问题采用贪心选择算法解决。
算法思想：
求max的步骤：
（1）对黑板上的n个正数从小到大排序
（2）取最小的两个数，进行a*b+1运算，将结果插入数列，再从小到大排序。
（3）重复步骤
（2），直到黑板上剩一个数为止，该数为最大值max。
求min的步骤：
（1）对黑板上的n个正数从大到小排序
（2）取最大的两个数，进行a*b+1运算，将结果插入数列，再从大到小排序。
（3）重复步骤
（2），直到黑板上剩一个数为止，该数为最大值min。
Voidmax-min（intn,intmax,intmin,type**x,type**y）
{MinHeap<
MinHeapNode<
Type>
x（1000）;
MaxHeap<
MaxHeapNode<
y（1000）;
While（true）
{
MinHeapNode<
x;
MaxHeapNode<
y;
a=x.DeleteMin（x）;
b=x.DeleteMin（x）;
Max=a*b+1
x.insert（max）;
c=y.DeleteMin（y）;
d=y.DeleteMin（y）;
Min=c*d+1
y.insert（min）;
catch（outofBounds）{break;
}
M=a-c
5-10最小重量机
该问题用回溯法求解。
1．问题的解空间：
部件：
n个1<
=I<
=n,供应商：
m个1<
=j<
=m
wij：
是从供应商j处构得的部件I的重量。
Cij：
是从供应商j处构得的部件I的价格。
当（C11+C12+……+Cnm）<
C时，求最小的（W11+W12+……+Wnm）
假设n=4m=2时，该问题的解空间树如下：
该树为n层的m叉树。
2．回溯法的基本思想：
按深度优先的方式搜索整个解空间树。
3．求约束函数和限界函数
（1）约束函数：
若大于总价格C，则该结点不可能有解，可剪去以这个结点为根的子树。
Constraint（c）：
计算（C11+C12+……+Cnm）<
C
（2）限界函数：
先找到一个解，在寻找下一个解时，判断扩展结点处的（W11+W12+……+Wnm）是否小于前一个解的（W11+W12+……+Wnm），若是，则继续扩展，否则，则该子树不能得到最优解，剪去以该结点为根的子树。
Bound（w）：
计算（W11+W12+……+Wnm）的最小值。
4．递归回溯算法
Voidweight-cost（t）
{if（I>
0）
if（cc<
bestc）bestc=c;
if（bestc<
c）
{if（cw<
bestw）bestw=cw;
return;
for（j=1;
j<
=m;
j++）
{if（cc+c[I][j]<
c）
cc+=c[I][j];
weight-cost（I+1）;
cc-=c[I][j];
}
intn,//部件数
m,//供应商树
type**w,//是从供应商j处构得的部件I的重量。
type**c,//是从供应商j处构得的部件I的价格。
c,//总价格
cc,//当前总价格
cw,//当前总重量
bestc,//当前最优价格
bestw;
//当前最优重量
main（）
{
n=4;
m=2;
c=1000;
cc=0;
cw=0;
bestc=0;
bestw=32767;
weight-cost
（1）;
升级会员 