《计算机常用算法与程序设计案例教程》习题解答 下载本文

a[i][j]=a[i][j-1]+r[i][j-1]; printf(\

所求左上角顶点到右下角顶点的最大路程即最优值为a(n,m)。

6-4 求解边数值三角形的最短路径

已知边数值三角形每两点间距离如图7-4所示,每一个点可向左或向右两个去向,求三角形顶点到底边的最短路径。

图7-4 三角形边数值数据

1) 算法设计

设边数值三角形为n行(不包含作为边终止点的三角形底边),每点为(i,j),i=1,2,……,n;j=1,2,……,i.从点(i,j)向左的边长记为l(i,j),点(i,j)向右的边长记为r(i,j)。记a(i,j)为点(i,j)到底边的最短路程。显然

a(i,j)=min(a(i+1,j)+l(i,j),a(i+1,j+1)+r(i,j)) st(i,j)={‘l’,’r’}

应用逆推求解,所求的顶点A到底边的最短路程为a(1,1). 2) 边数值三角形最短路径搜索C程序设计 // 边数值三角形最短路径搜索 #include \#include

void main()

{ int n,i,j,t,s;

int a[50][50],l[50][50],r[50][50];char st[50][50];

t=time()00;srand(t); // 随机数发生器初始化 printf(\请输入数字三角形的行数n:\ scanf(\

for(i=1;i

{for(j=1;j<=37-4*i;j++) printf(\

for(j=1;j<=i;j++) printf(\ for(j=1;j<=36-4*i;j++) printf(\

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

{l[i][j]=rand()/1000+1;printf(\ r[i][j]=rand()/1000+1;printf(\ printf(\

for(j=1;j<=37-4*(n+1);j++) printf(\ for(j=1;j<=n+1;j++) printf(\printf(\底边\\n\\n\

for(i=n;i>=1;i--) // 逆推求取最短路径 {for(j=1;j<=i;j++)

if(a[i+1][j]+l[i][j]

{a[i][j]=a[i+1][j+1]+r[i][j];st[i][j]='r';} }

printf(\最短路程为:%d\printf(\最短路径为:顶点A \for(j=1,i=1;i<=n;i++) if(st[i][j]=='l')

printf(\ else

{printf(\printf(\底边。\}

6-5 求解点数值矩阵最小路径

随机产生一个n行m列的整数矩阵,在整数矩阵中寻找从左上角至右下角,每步可向下(D)或向右(R)或斜向右下(O)的一条数值和最小的路径。

1) 算法设计

应用动态规划,即从右下角逐行反推至左上角。确定n,m后,随机产生的整数二维数组a(n,m)作矩阵输出,同时赋给部分和数组b(n,m)。这里数组b(i,j)为点(i,j)到右下角的最小数值和,stm(i,j)是点(i,j)向右(R)或向下(D)或向右下(O)的路标字符数组。

注意到最后一行与最后一列各数只有一个出口,于是由b(n,m)?开始向左逐个推出同行的b(n,j),(j=m-1,...,2,1);向上逐个推出同列的b(i,m),(i=n-1,...,2,1)。

b(i,j)与stc(i,j)(i=n-1,...,2,1,j=m-1,...,2,1))的值由同一列其下面的整数b(i+1,j)与同一行其右边的整数b(i,j+1)或其右下方的b(i+1,j+1)的值决定:

首先,作赋值 b(i,j)=yb+b(i+ 1, j + 1): stc(i, j) = \其中变量yb为原b(i,j)的值)。

然后,求 b(i+1,j) 与 b(i,j+1) 的最小值 min。

如果 b(i+1,j+1)>min ,说明前面为b(i,j)赋值不对,作修改: b(i,j)=yb+min

若min 为 b(i+1,j),则 stc(i,j)=\否则 stc(i,j)=\ 这样反推所得b(1,1)即为所求的最小路径数字和。

为了打印最小路径,利用c数组从上而下操作:先打印a(1,1),i=1,j=1. 若 stc(i,j)=\则j增1,即j=j+1,然后打印 \与右边整数a(i,j); 若 stc(i,j)=\则i增1,即i=i+1,然后打印 \与下面整数a(i,j);

若 stc(i,j)=\则i,j均增1,即i=i+1,j=j+1,然后打印 \与斜向右下整数a(i,j);

依此类推,直至打印到终点a(n,m)。

6-6 西瓜分堆

已知的n个西瓜的重量分别为整数,请把这堆西瓜分成两堆,每堆的个数不一定相等,使两堆西瓜重量之差为最小。

(1) 设计要点

两组数据之和不一定相等,不妨把较少的一堆称为第1堆。设n个整数b(i)之和为s,则第1堆数据之和s1≤[s/2],这里[x]为x的取整。

问题要求在满足s1≤[s/2]前提下求s1最大值maxc,这样两堆数据和之差的最小值为mind=s-2*maxc。

为了求s1的最大值,应用动态规划设计,按分每一个瓜为一个阶段,共分为n个阶段。每一个阶段都面临两个决策:选与不选该瓜到第1组。

1) 建立递推关系

设m(i,j)为第1堆距离c1=[s/2]还差重量为j,可取瓜编号范围为:i,i+1,…,n的最大装载重量值。则

当0≤j

不装入西瓜i,这时最大重量值为m(i+1, j);

装入西瓜i,这时已增加重量b(i),剩余重量为j?b(i),可以选择西瓜i+1,…,n来装,最大载重量值为m(i+1,j?b(i))+b(i)。我们期望的最大载重量值是两者中的最大者。于是有递推关系

0?j?b(i)?m(i?1,j)m(i,j)???max(m(i?1,j),m(i?1,j?b(i))?b(i)) j?b(i)

以上j与b(i)均为正整数,i=1,2,…,n,

所求最优值m(1,c1)即为s1的最大值maxc。因而得两组数据和之差的最小值为mind=s-2*maxc=s-2*m(1,c1)。

2) 递推计算最优值

for(j=0;j

for(j=b(n);j<=c1;j++) m(n,j)=b(n); // 首先计算m(n,j) for(i=n-1;i>=1;i--) // 逆推计算m(i,j) for(j=0;j<=c1;j++)

if(j>=b(i) && m(i+1,j)

m(i,j)=m(i+1,j); printf(\3) 构造最优解

构造最优解即给出所得最优值时的分瓜方案。

if(m(i,cb)>m(i+1,cb)) (其中cb为当前的剩余量,i=1,2, n?1) 第1堆分b(i); else 不分b(i);

if(m(1,c1)-sb=b(n)) 则第1堆分b(n)。 (2)求解两组数据和之差的最小值程序设计 // 求解两组数据和之差的最小值 #include #define N 40 void main()

{int n,c1,i,j,s,t,cb,sb,b[N],m[N][10*N]; printf(\ s=0;

for(i=1;i<=n;i++) // 输入n个西瓜重量整数 {printf(\请输入第%d个整数:\

scanf(\ } c1=s/2;

printf(\各个西瓜重量:\ for(i=1;i<=n;i++)

printf(\

printf(\总重量s=%d \\n\ for(j=0;j

m[n][j]=0;

for(j=b[n];j<=c1;j++)

m[n][j]=b[n]; // 首先计算m(n,j) for(i=n-1;i>=1;i--) // 逆推计算m(i,j) for(j=0;j<=c1;j++)

if(j>=b[i] && m[i+1][j]

else

m[i][j]=m[i+1][j]; // 得最优值m(1,c1) printf(\两堆之差最小值为:%d \\n\printf(\第1堆: \ cb=m[1][c1];

for(sb=0,i=1;i<=n-1;i++) // 构造最优解,输出第1堆的西瓜 if(m[i][cb]>m[i+1][cb]) {cb-=b[i];sb+=b[i]; printf(\

b[i]=0; // b(i)分后赋0,为输出第2堆作准备 }

if(m[1][c1]-sb==b[n])

{printf(\ sb+=b[n]; b[n]=0; }

printf(\ printf(\第2堆: \

for(sb=0,i=1;i<=n;i++) // 输出第2堆西瓜 if(b[i]>0) {sb+=b[i];

printf(\ }

printf(\}

6-7 应用递推实现动态规划求解序列的最小子段和 应用递推实现动态规划求解:给定n个整数(可能为负整数)组成的序列a1,a2,,an,求该序列形如?ak段和的最小值。

k?ij递推实现动态规划求解: 1) 动态规划算法设计

设q[j]为序列前j项之和的最小值,即 q[j]?min{?a[k]}1?i?jk?ij(1?j?n)

由q[j]的定义,得q[j]的递推关系:

q[j?1]?a[j]q[j?1]?0 q[j]????a[j]q[j?1]?0(1?j?n)

初始条件:

Q[0]=0 (没有项时,其值自然为0)。