七桥问题答案图解

.

.

习题1

1.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（LeonhardEuler，1707—1783）

提出并解决了该问题。七桥问题是这样描述的：

一个人是否能在一次步行中穿越哥尼斯堡（现在

叫加里宁格勒，在波罗的岸）城中全部的七座桥

后回到起点，且每座桥只经过一次，图1.7是这

条河以及河上的两个岛和七座桥的草图。请将该

问题的数据模型抽象出来，并判断此问题是否有

解。

七桥问题属于一笔画问题。

输入：一个起点

输出：相同的点

1，一次步行

2，经过七座桥，且每次只经历过一次

3，回到起点

该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个

奇点的图形。

2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。

请用伪代码描述这个版本的欧几里德算法

1.r=m-n

2.循环直到r=0

2.1m=n

2.2n=r

2.3r=m-n

3输出m

3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码

和C++描述。

//采用分治法

//对数组先进行快速排序

//在依次比较相邻的差

图1.7七桥问题

北区

东区

岛区

南区

.

.

#include

usingnamespacestd;

intpartions(intb[],intlow,inthigh)

{

intprvotkey=b[low];

b[0]=b[low];

while(low

{

while(low=prvotkey)

--high;

b[low]=b[high];

while(low

++low;

b[high]=b[low];

}

b[low]=b[0];

returnlow;

}

voidqsort(intl[],intlow,inthigh)

{

intprvotloc;

if(low

{

prvotloc=partions(l,low,high);//将第一次排序的结果作为枢轴

qsort(l,low,prvotloc-1);//递归调用排序由low到prvotloc-1

qsort(l,prvotloc+1,high);//递归调用排序由prvotloc+1到high

}

}

voidquicksort(intl[],intn)

{

qsort(l,1,n);//第一个作为枢轴，从第一个排到第n个

}

intmain()

{

inta[11]={0,2,32,43,23,45,36,57,14,27,39};

intvalue=0;//将最小差的值赋值给value

for(intb=1;b<11;b++)

cout<

.

.

cout<

quicksort(a,11);

for(inti=0;i!=9;++i)

{

if((a[i+1]-a[i])<=(a[i+2]-a[i+1]))

value=a[i+1]-a[i];

el

value=a[i+2]-a[i+1];

}

cout<

return0;

}

4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的

元素，并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述。

#include

usingnamespacestd;

intmain()

{

inta[]={1,2,3,6,4,9,0};

intmid_value=0;//将“既不是最大也不是最小的元素”的值赋值给它

for(inti=0;i!=4;++i)

{

if(a[i+1]>a[i]&&a[i+1]

{

mid_value=a[i+1];

cout<

break;

}

elif(a[i+1]a[i+2])

{

mid_value=a[i+1];

cout<

break;

}

}//for

.

.

return0;

}

5.编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。

#include

usingnamespacestd;

intmain()

{

doublevalue=0;

for(intn=1;n<=10000;++n)

{

value=value*10+1;

if(value%2013==0)

{

cout<<"n至少为:"<

break;

}

}//for

return0;

}

6.计算π值的问题能精确求解吗？编写程序，求解满足给定精度要求的π值

#include

usingnamespacestd;

intmain()

{

doublea,b;

doublearctan(doublex);//声明

a=16.0*arctan(1/5.0);

b=4.0*arctan(1/239);

cout<<"PI="<

return0；

}

doublearctan(doublex)

{

inti=0;

doubler=0,e,f,sqr;//定义四个变量初

.

.

sqr=x*x;

e=x;

while(e/i>1e-15)//定义精度围

{

f=e/i;//f是每次r需要叠加的方程

r=(i%4==1)?r+f:r-f;

e=e*sqr;//e每次乘于x的平方

i+=2;//i每次加2

}//while

returnr;

}

7.圣经上说：神6天创造天地万有，第7日安歇。为什么是6天呢？任何一个自然数的

因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真

因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此6是完美数。神6天

创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数

#include

usingnamespacestd;

intmain()

{

intvalue,k=1;

cin>>value;

for(inti=2;i!=value;++i)

{

while(value%i==0)

{

k+=i;//k为该自然数所有因子之和

value=value/i;

}

}//for

if(k==value)

cout<<"该自然数是完美数"<

el

cout<<"该自然数不是完美数"<

return0;

}

8.有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，

.

.

并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必

须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟，乙过桥要用

2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢

那个人的速度，问题是他们全部过桥最少要用多长时间？

由于甲过桥时间最短，那么每次传递手电的工作应有甲完成

甲每次分别带着乙丙丁过桥

例如：

第一趟：甲，乙过桥且甲回来

第二趟：甲，丙过桥且甲回来

第一趟：甲，丁过桥

一共用时19小时

9．欧几里德游戏：开始的时候，白板上有两个不相等的正整数，两个玩家交替行动，每

次行动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这个数

字必须是新的，也就是说，和白板上的任何一个已有的数字都不相同，当一方再也写不出新

数字时，他就输了。请问，你是选择先行动还是后行动？为什么？

设最初两个数较大的为a,较小的为b，两个数的最大公约数为factor。

则最终能出现的数包括:factor,factor*2,factor*3,...,factor*(a/factor)=a.一共

a/factor个。

如果a/factor是奇数，就选择先行动；否则就后行动。

习题4

1.分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的

个数有关，试说明这几个参数与分治法时间复杂性之间的关系。

2.证明：如果分治法的合并可以在线性时间完成，则当子问题的规模之和小于原问题

的规模时，算法的时间复杂性可达到O(n)。

O(N)=2*O(N/2)+x

O(N)+x=2*O(N/2)+2*x

a*O(N)+x=a*(2*O(N/2)+x)+x=2*a*O(N/2)+(a+1)*x

由此可知，时间复杂度可达到O(n);

3.分治策略一定导致递归吗？如果是，请解释原因。如果不是，给出一个不包含递归的

分治例子，并阐述这种分治和包含递归的分治的主要不同。

.

.

不一定导致递归。

如非递归的二叉树中序遍历。

这种分治方法与递归的二叉树中序遍历主要区别是：应用了栈这个数据结构。

4.对于待排序序列(5,3,1,9)，分别画出归并排序和快速排序的递归运行轨迹。

归并排序：

第一趟：（5,3）（1,9）；

第二趟：（3,5,1,9）；

第三趟：（1,3,5,9）；

快速排序：

第一趟：5（,3,1,9）；//5为哨兵，比较9和5

第二趟：5（1,3,,9）；//比较1和5，将1挪到相应位置；

第三趟：5（1,3,,9）;//比较3和5；

第四趟：（1,3,5,9）;

5.设计分治算法求一个数组中的最大元素，并分析时间性能。

//简单的分治问题

//将数组均衡的分为“前”，“后”两部分

//分别求出这两部分最大值，然后再比较这两个最大值

#include

usingnamespacestd;

externconstintn=6;//声明

intmain()

{

inta[n]={0,6,1,2,3,5};//初始化

intmid=n/2;

intnum_max1=0,num_max2=0;

for(inti=0;i<=n/2;++i)//前半部分

{

if(a[i]>num_max1)

num_max1=a[i];

}

for(intj=n/2+1;j

{

if(a[j]>num_max2)

num_max2=a[j];

}

if(num_max1>=num_max2)

cout<<"数组中的最大元素："<

el

.

.

cout<<"数组中的最大元素："<

return0;

}

时间复杂度：O（n）

6.设计分治算法，实现将数组A[n]中所有元素循环左移k个位置,要求时间复杂性为

O(n)，空间复杂性为O(1)。例如，对abcdefgh循环左移3位得到defghabc。

//采用分治法

//将数组分为0-k-1和k-n-1两块

//将这两块分别左移

//然后再合并左移

#include

usingnamespacestd;

voidLeftRever(char*a,intbegin,intend)

{

for(inti=0;i<(end-begin+1)/2;i++)//交换移动

{

inttemp=a[begin+i];

a[begin+i]=a[end-i];

a[end-i]=temp;

}

}

voidConver(char*a,intn,intk)

{

LeftRever(a,0,k-1);

LeftRever(a,k,n-1);

LeftRever(a,0,n-1);

for(inti=0;i

cout<

cout<

}

intmain()

{

chara[7]={'a','b','c','d','e','f','g'};

Conver(a,7,3);

.

.

return0;

}

7.设计递归算法生成n个元素的所有排列对象。

#include

usingnamespacestd;

intdata[100];

//在m个数中输出n个排列数（n<=m）

voidDPpl(intnum,intm,intn,intdepth)

{

if(depth==n)

{

for(inti=0;i

cout<

cout<

}

for(intj=0;j

{

if((num&(1<

{data[depth]=j+1;

DPpl(num+(1<

}

}//for

}

intmain()

{

DPpl(0,5,1,0);

DPpl(0,5,2,0);

DPpl(0,5,3,0);

DPpl(0,5,4,0);

DPpl(0,5,5,0);

return0;

}

8.设计分治算法求解一维空间上n个点的最近对问题。

参见4.4.1最近对问题的算法分析及算法实现

9.在有序序列(r1,r2,…,rn)中，存在序号i（1≤i≤n），使得ri=i。请设计一个分

治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n)。

//在有序数组中

.

.

//采用二分法查找符合条件的元素

#include

usingnamespacestd;

voidFindnum(int*a,intn)

{

intlow=0;

inthigh=n-1;

while(low<=high)

{

intmid=(low+high)/2;

if(a[mid]==mid)

{

cout<<"这个数是："<

break;

}

elif(a[mid]>mid)

high=mid-1;

el

low=mid+1;

}

}

intmain()

{

inta[7]={1,0,2,5,6,7,9};

Findnum(a,7);

return0;

}

时间复杂度为O(log2n)。

10.在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时

间复杂性。

//先对序列进行快速排序

//再进行一次遍历

//输出众数的重复次数

#include

.

.

usingnamespacestd;

intpartions(intb[],intlow,inthigh)

{

intprvotkey=b[low];

b[0]=b[low];

while(low

{

while(low=prvotkey)

--high;

b[low]=b[high];

while(low

++low;

b[high]=b[low];

}

b[low]=b[0];

returnlow;

}

voidqsort(intl[],intlow,inthigh)

{

intprvotloc;

if(low

{

prvotloc=partions(l,low,high);//将第一次排序的结果作为枢轴

qsort(l,low,prvotloc-1);//递归调用排序由low到prvotloc-1

qsort(l,prvotloc+1,high);//递归调用排序由prvotloc+1到high

}

}

voidquicksort(intl[],intn)

{

qsort(l,1,n);//第一个作为枢轴，从第一个排到第n个

}

intmain()

{

inta[10]={1,2,3,5,3,3,3,2,5,1};

inti=0;

intcount=0;

intmax=0;//max表示出现的次数

.

.

qsort(a,0,10);

while(i<10)

{

intj;

j=i+1;

if(a[i]=a[j]&&i<10)

{

count++;

i++;

}

if(count>max)

{

max=count;

count=0;

}

}//while

cout<<"重复次数："<

return0;

}

时间复杂度nlog(n)

11.设M是一个n×n的整数矩阵，其中每一行（从左到右）和每一列（从上到下）的元

素都按升序排列。设计分治算法确定一个给定的整数x是否在M中，并分析算法的时间复杂

性。

12.设S是n（n为偶数）个不等的正整数的集合，要求将集合S划分为子集S1和S2，

使得|S1|=|S2|=n/2，且两个子集元素之和的差达到最大。

//先用快速排序进行一趟排序

//如果s1（大的数集）的的个数大于n/2

//将（i<=n/2-low-1）个最小的数排到后面

//如果s1（大的数集）的的个数小于n/2

//将s2（小的数集）n/2-low-1排到前面

//将排好的数组的前n/2个数赋值给s1

//将排好的数组的后n/2个数赋值给s2

#include

usingnamespacestd;

constintn=8;

voidpartions(inta[],intlow,inthigh)

.

.

{

//进行一趟快排

intprvotkey=a[low];

a[0]=a[low];

while(low

{

while(low

--high;

a[low]=a[high];

while(low=prvotkey)

++low;

a[high]=a[low];

}

a[low]=prvotkey;

//如果s1（大的数集）的的个数大于n/2

if(low>=n/2)

{

for(inti=0;i<=n/2-low-1;++i)

{

for(intj=0;j

{

if(a[j]

{

inttemp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}//for

}

}//if

//如果s1（大的数集）的的个数小于n/2

el

for(inti=0;i<=n/2-low-1;++i)

{

for(intk=n-1;k

{

if(a[k]>a[k-1])

{

inttemp1=a[k];

a[k]=a[k-1];

a[k-1]=temp1;

}

.

.

}//for

}

}

intmain()

{

inta[n]={1,3,5,9,6,0,-11,-8};

partions(a,0,n-1);

for(inti=0;i

{

if(i<4)

{

cout<<"属于子集s1的："<

cout<

}

el

{

cout<<"属于子集s2的："<

cout<

}

}

return0;

}

13.设a1,a2,…,an是集合{1,2,…,n}的一个排列，如果iaj，则序偶(ai,

aj)称为该排列的一个逆序。例如，2,3,1有两个逆序：(3,1)和(2,1)。设计算法统计

给定排列中含有逆序的个数。

//用归并进行排序

//当一个子集的一个数大于第二个子集的一个数，为逆序，即a[i]>a[j]

//则逆序数为end-j+1;

#include

usingnamespacestd;

intcount;

voidMerge(inta[],inta1[],intbegin,intmid,intend)//合并子序列

{

inti=begin,j=mid+1,k=end;

.

.

while(i<=mid&&j<=end)

{

if(a[i]<=a[j])

a1[k++]=a[i++];//取a[i]和a[j]中较小者放入r1[k]

el

{

a1[k++]=a[j++];

count+=(end-j+1);

}

}

while(i<=mid)

a1[k++]=a[i++];

while(j<=end)

a1[k++]=a[j++];

}

voidMergeSort(inta[],intbegin,intend)

{

intmid,a1[1000];

if(begin==end)

return;

el

{

mid=(begin+end)/2;

MergeSort(a,begin,mid);

MergeSort(a,mid+1,end);

Merge(a,a1,begin,mid,end);

}

}

intmain()

{

inta[6]={6,5,4,3,2,1};

count=0;

MergeSort(a,0,6);

cout<

return0;

}

14.循环赛日程安排问题。设有n=2k个选手要进行网球循环赛，要求设计一个满足以下

要求的比赛日程表：

（1）每个选手必须与其他n-1个选手各赛一次；

（2）每个选手一天只能赛一次。

.

.

采用分治方法。

将2^k选手分为2^k-1两组，采用递归方法，继续进行分组，直到只剩下2个选手时，然

后进行比赛，回溯就可以指定比赛日程表了

15.格雷码是一个长度为2n的序列，序列中无相同元素，且每个元素都是长度为n的

二进制位串，相邻元素恰好只有1位不同。例如长度为23的格雷码为(000,001,011,010,

110,111,101,100)。设计分治算法对任意的n值构造相应的格雷码。

//构造格雷码

#include

usingnamespacestd;

intn;

chara[100];

voidgelei(intk)

{

if(k==n)

{

cout<

return;

}

gelei(k+1);

a[k]='0'?'1':'0';//取反

gelei(k+1);

}

intmain()

{

while(cin>>n&&n!=0)

{

memt(a,'0',sizeof(a));//初始化，全部置零

a[n]='0';

gelei(0);

cout<

}

return0;

}

16.矩阵乘法。两个n×n的矩阵X和Y的乘积得到另外一个n×n的矩阵Z，且Zij

满足（1≤i,j≤n），这个公式给出了运行时间为O(n3)的算法。可以用分

治法解决矩阵乘法问题，将矩阵X和Y都划分成四个n/2×n/2的子块，从而X和Y的乘积可

.

.

以用这些子块进行表达，即XY从而得到分治算法：先递归地计算8个规模为n/2的矩阵乘积AE、BG、AF、BH、CE、DG、

CF、DH，然后再花费O(n2)的时间完成加法运算即可。请设计分治算法实现矩阵乘法，并分

析时间性能。能否再改进这个分治算法？

习题5

1.下面这个折半查找算确吗？如果正确，请给出算法的正确性证明，如果不正确，请说明

产生错误的原因。

intBinSearch(intr[],intn,intk)

{

intlow=0,high=n-1;

intmid;

while(low<=high)

{

mid=(low+high)/2;

if(k

elif(k>r[mid])low=mid;

elreturnmid;

}

return0;

}

错误。

正确算法：

intBinSearch1(intr[],intn,intk)

{

intlow=0,high=n-1;

intmid;

while(low<=high)

{

mid=(low+high)/2;

if(k

elif(k>r[mid])low=mid+1;

elreturnmid;

}

return0;

}

.

.

2.请写出折半查找的递归算法，并分析时间性能。

//折半查找的递归实现

#include

usingnamespacestd;

intdigui_arch(inta[],intlow,inthigh,intx)

{

if(low>high)

return0;

intmid=(low+high)/2;

if(a[mid]==x)

returnmid;

elif(a[mid]

digui_arch(a,low,mid-1,x);

el

digui_arch(a,mid+1,high,x);

}

intmain()

{

inta[6]={0,1,2,9,5,3};

intresult=digui_arch(a,0,5,5);

cout<

return0;

}

3.修改折半查找算法使之能够进行围查找。所谓围查找是要找出在给定值a和b之间的所

有元素（a≤b）

修改第二题算法并实现：

//折半查找算法使之能够进行围查找

#include

usingnamespacestd;

//折半进行围查找函数：

voiddigui_arch(intmin,intmax,inta[],intlow,inthigh)

.

.

{

intmid;

mid=(low+high)/2;

if(a[mid]

digui_arch(min,max,a,mid,high);

elif(a[mid]>max)

digui_arch(min,max,a,low,mid);

el

{

for(inti=mid;a[i]>=min&&i>=low;i--)

cout<

cout<

for(intj=mid+1;a[j]<=max&&j<=high;j++)

cout<

cout<

}

}

voidmain()

{

intr[6],min,max;

cout<<"请输入数组元素："<

for(inti=0;i<6;i++)

cin>>r[i];

cout<<"请输入查找围最小值min和最大值max："<<"";

cin>>min>>max;

digui_arch(min,max,r,0,5);

cout<

}

4.求两个正整数m和n的最小公倍数。（提示：m和n的最小公倍数lcm(m,n)与m和

n的最大公约数gcd(m,n)之间有如下关系：lcm(m,n)=m×n/gcd(m,n)）

//求两个数的最小公倍数

#include

usingnamespacestd;

intmain(void)

{

inta,b;

.

.

inti=1;

cin>>a>>b;

while((i%a!=0)||(i%b!=0))

++i;

cout<<"a,b最小公倍数为："<

return0;

}

(该算法比较直接，要使其改进，可用欧几里得算法求得两个数的最大公约数，然后套用上

面的公式再求最小公倍数)

5.插入法调整堆。已知（k1,k2,…,kn）是堆，设计算法将（k1,k2,…,kn,kn+1）

调整为堆（假设调整为大根堆）。

参照：

voidSiftHeap(intr[],intk,intn)

{

inti,j,temp;

i=k;j=2*i+1;//置i为要筛的结点，j为i的左孩

子

while(j

{

if(j

if(r[i]>r[j])//根结点已经大于左右孩子中的较大

者

break;

el{

temp=r[i];r[i]=r[j];r[j]=temp;//将被筛结点与结点j交换

i=j;j=2*i+1;//被筛结点位于原来结点j的位置

}

}

}

进行调堆！

6.设计算法实现在大根堆中删除一个元素，要求算法的时间复杂性为O(log2n)。

//将要删除的a[k]与最后一个元素a[n-1]交换

//然后进行调堆

voidde_SiftHeap(intr[],intk,intn)

{

inti,j,temp,temp1;

i=k;j=2*i+1;

if(i<0||i>n-1)

.

.

returnerror;

elif(i==n-1)

free(a[i]);

el//置i为要筛的结点，j为i的左孩子

while(j

{

temp1=a[i];//将a[n-1]与a[k]交换；

a[i]=a[n-1];

a[n-1]=temp1;

if(j

if(r[i]>r[j])//根结点已经大于左右孩子中的较大

者

break;

el{

temp=r[i];r[i]=r[j];r[j]=temp;//将被筛结点与结点j交换

i=j;j=2*i+1;//被筛结点位于原来结点j的位置

}

}

}

7.计算两个正整数n和m的乘积有一个很有名的算法

称为俄式乘法，其思想是利用了一个规模是n的解和一个

规模是n/2的解之间的关系：n×m＝n/2×2m（当n是偶数）

或：n×m＝(n-1)/2×2m＋m（当n是奇数），并以1×m＝m作

为算法结束的条件。例如，图5.15给出了利用俄式乘法计

算50×65的例子。据说十九世纪的俄国农夫使用该算法并

因此得名，这个算法也使得乘法的硬件实现速度非常快，

因为只使用移位就可以完成二进制数的折半和加倍。请设

计算法实现俄式乘法。

//俄式乘法

#include

usingnamespacestd;

intfun(intm,intn)

{

intsum=0;

inttemp=n;

while(m!=1)

{

if(m%2==0)//如果n是偶数

{

n=n*2;

nm

5065

25130130

12260

6520

310401040

120802080

3250

图5.15俄式乘法

+

.

.

m=m/2;

}

el//如果n是奇数

{

n=n*2;

sum+=temp;

m=(m-1)/2;

}

temp=n;//记录倒数第二个n的值

}

returnsum+n;

}

intmain()

{

inta,b;

while(cin>>a>>b)

{

cout<

}

}

8.拿子游戏。考虑下面这个游戏：桌子上有一堆火柴，游戏开始时共有n根火柴，两

个玩家轮流拿走1，2，3或4根火柴，拿走最后一根火柴的玩家为获胜方。请为先走的玩家

设计一个制胜的策略（如果该策略存在）。

如果桌上有小于4根的火柴，先手必胜，如果是5根，先手必输；依次类推，同理15、

20、25…….都是必输状态；所有每次把对手逼到15、20、25…….等必输状态，就可以获

胜。

9.竞赛树是一棵完全二叉树，它反映了一系列“淘汰赛”的结果：叶子代表参加比赛

的n个选手，每个部结点代表由该结点的孩子结点所代表的选手中的胜者，显然，树的根结

点就代表了淘汰赛的冠军。请回答下列问题：

（1）这一系列的淘汰赛中比赛的总场数是多少？

（2）设计一个高效的算法，它能够利用比赛中产生的信息确定亚军。

（1）因为n人进行淘汰赛，要淘汰n-1人，所有要进行n-1场比赛。

（2）

10.在120枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但

不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，最坏情况下，

能不能只比较5次就检测出这枚假币？

.

.

将120枚平均分为三组，记为：A，B，C；先将A,B比较，如果A,B重量不同（假如B比A

重），再将B与C比较，如果B，C相同，则A有假币；如果B,C不同，再将A,C比较，如果

A,C相同，则B有假币；如果A,C不同，则B有假币；如果A,B相同，则C有假币；

习题6

1.动态规划法为什么都需要填表？如何设计表格的结构？

在填写表格过程中，不仅可以使问题更加清晰，更重要的是可以确定问题的存储结构；

设计表格，以自底向上的方式计算各个子问题的解并填表。

2.对于图6.26所示多段图，用动态规划法求从顶点0到顶点12的最短路径，写出求

解过程。

将该多段图分为四段；

首先求解初始子问题，可直接获得：

d(0,1)=c01＝5(0→1)

d(0,2)=c02＝3(0→1)

再求解下一个阶段的子问题，有：

d(0,3)=d(0,1)+c13=6(1→3)

d(0,4)=min{d(0,1)+c14,d(0,2)+c24}=8(1→4)

。。。。。。。。（以此类推）

最短路径为：0→1→3→8→11→12

3．用动态规划法求如下0/1背包问题的最优解：有5个物品，其重量分别为(3,2,1,

4,5)，价值分别为(25,20,15,40,50)，背包容量为6。写出求解过程。

(x1,x2,x3,x4,x5)→(1,1,1,0,0)(过程略)

4.用动态规划法求两个字符串A="xzyzzyx"和B="zxyyzxz"的最长公共子序列。写出求

解过程。

略

8

8

3

5

1

0

2

3

4

10

11

12

图6.26第2题图

5

6

7

8

9

1

3

6

7

6

8

3

5

3

3

4

6

3

5

5

2

6

4

3

.

.

5.给定模式"grammer"和文本"grameer"，写出动态规划法求解K-近似匹配的过程。

略

6.对于最优二叉查找树的动态规划算法，设计一个线性时间算法，从二维表R中生成

最优二叉查找树。

ann函数A(m,n)的递归定义如下：



















0,0))1,(,1(

0,0)1,1(

01

),(

nmnmAmA

nmmA

mn

nmA

设计动态规划算法计算A(m,n)，要求算法的空间复杂性为O(m)。

//求ackman函数

//使用栈

#include

usingnamespacestd;

longackman(longm,longn)

{

longstack[10000];

intpos=1;

stack[0]=m;stack[1]=n;

while(pos)

{

n=stack[pos--];

m=stack[pos];

if(m==0)

stack[pos]=n+1;

if(m!=0&&n==0)

{

stack[pos++]=m-1;

stack[pos]=1;

}

if(m!=0&&n!=0)

{

stack[pos++]=m-1;

stack[pos++]=m;

stack[pos]=n-1;

.

.

}

}

returnstack[0];

}

intmain(intargc,char*argv[])

{

longm,n;

cin>>m>>n;

cout<

cout<

return0;

}

8.考虑下面的货币兑付问题：在面值为(v1,v2,…,vn)的n种货币中，需要支付y值

的货币，应如何支付才能使货币支付的数最少，即满足yvx

n

i

ii



1

，且使



n

i

i

x

1

最小（xi是

非负整数）。设计动态规划算法求解货币兑付问题，并分析时间性能和空间性能。

#include

#defineN100000

#defineM20

inta[N][M];

intvalue[M];

usingnamespacestd;

intmain()

{

while(true)

{

inti,j,k;

intx,y,z;

cout<<"输入货币种类的个数："<

cin>>x;

cout<<"从小到大输入货币的价值，其中第一个必须为一："<

for(i=1;i<=x;i++)//x为货币种类的个数

{

cout<<"value["<

.

.

cin>>y;

value[i]=y;

}

cout<<"输入要兑换的钱的价值："<

cin>>z;//z为钱

for(j=0;j<=z;j++)

a[j][0]=0;

for(k=0;k<=x;k++)

a[0][k]=0;

for(i=1;i<=z;i++)

{

for(j=1;j<=x;j++)

{

if(value[j]==i)

a[i][j]=1;

elif(value[j]>i)

a[i][j]=a[i][j-1];

el

a[i][j]=a[i-value[j]][j]+1;//相当于把乘法换成加法，即碰到一

个钱数于兑换货币自身价值时，返回到

钱数减去该货币值的地方，其值再加1//

}//for

}

cout<<"兑换的最小货币个数是："<

}//while

return0;

}