算法设计与分析(作业三).doc

算法设计与分析
实验报告

学 院 信息科学与技术学院
专业班级 软件工程3班
学 号 20122668
姓 名 王建君
指导教师 尹治本

2014年10月

实验四 矩阵相乘次序
一、 问题提出
用动态规划算法解矩阵连乘问题。给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：
（1） 单个矩阵是完全加括号的；
（2） 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。
（3） 为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,An}（其中矩阵Ai的维数为pi-1×pi，i＝1,2,…,n），如何确定计算矩阵连乘积A1A2…An的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。
二、 求解思路
本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是：
1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m和**s，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另一张表存储最优断开位置。
2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。
三、算法复杂度
该算法时间复杂度最高为。
四、 实验源代码
#include<iostream>
using namespace std;
const int MAX = 100;
//p用来记录矩阵的行列，main函数中有说明 //m[i][j]用来记录第i个矩阵至第j个矩阵的最优解 //s[][]用来记录从哪里断开的才可得到该最优解
int p[MAX+1],m[MAX][MAX],s[MAX][MAX];
int n;//矩阵个数
int matrixChain()
{ for(int i=0;i<=n;i++)
m[i][i]=0;
for(int r=2;r<=n;r++)//对角线循环
for(int i=0;i<=n-r;i++)//行循环
{
int j = r+i-1;//列的控制 //找m[i][j]的最小值，先初始化一下，令k=i
m[i][j]=m[i+1][j]+p[i+1]*p[i]*p[j +1];
s[i][j]=i; //k从i+1到j-1循环找m[i][j]的最小值
for(int k = i+1;k<j;k++)
{
int temp=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
if(temp<m[i][j])
{
m[i][j]=temp; //s[][]用来记录在子序列i-j段中，在k位置处 //断开能得到最优解
s[i][j]=k;
}
}
}
return m[0][n-1];
} //根据s[][]记录的各个子段的最优解，将其输出
void traceback(int i,int j)
{
if(i==j)
{
cout<<'A'<<i;
return;
}
if(i<s[i][j])
cout<<'(';
traceback(i,s[i][j]);
if(i<s[i][j])
cout<<')';
if(s[i][j]+1<j)
cout<<'(';
traceback(s[i][j]+1,j);
if(s[i][j]+1<j)
cout<<')';
}
void traceback()
{
cout<<'(';
traceback(0,n-1);
cout<<')';
cout<<endl;
}
int main()
{
system("title 软件3班 王建君 20122668 动态规划求矩阵连乘次序");
cout<<"请输入矩阵的个数："<<endl;
cin>>n;
cout<<"输入矩阵（形如a*b,中间用空格隔开）:"<<endl;
for(int i=0;i<=n;i++)
cin>>p[i]; //测试数据可以设为8个矩阵分别为 //A1[10*15],A2[15*20],A3[20*5],A4[5*25],A5[25*20],A6[20*5],A7[5*23],A8[23,8] //则p[0-8]={10,15,20,5,25,20,5,23,8}
cout<<"输出结果如下："<<endl;
matrixChain();
traceback(0,n-1); //最终解值为m[0][n-1];
cout<<endl;
return 0;
}

五、 结果分析

测试数据可以设为8个矩阵分别为 /A0[10*15],A1[15*20],A2[20*5],A3[5*25],A4[25*20],A5[20*5],A6[5*23],A7[23,8] 则p[0-8]={10,15,20,5,25,20,5,23,8}，的最佳相乘次序为(A0(A1A2))(((A3A4)A5)(A6A7))。

实验五、找零问题
一、 问题提出
设有n种不同面值的硬币，各硬币的面值存于数组t[1:n]中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值t[1],t[2],…,t[i]时，可找出钱数M的最少硬币个数记为b[i][j]。若只用这些硬币面值，找不出钱数M时，记b[i][j]=∞。
二、 求解思路
令b[i,j]表示前i(1≤i≤m)种硬币，总额为j(0≤j≤n)的最小硬币数。目标为求b[m,n]。
由于对第i种硬币，存在可选1个或者不选两种可能，故容易建立递推关系：
b[i,j]＝min{ b[i-1,j], 1+b[i,j-vi]}, for 1≤i≤m, 0≤j≤n
显然，b[i,0]=0, 1≤i≤m
如果无解，令b[i,j]=+∞。特别的，如果i=1，令b[-1,j]=+∞；如果j-vi<0，b[i,j-vi]=+∞
三、 算法复杂度
n--钞票面额的个数 M--要找的钱数，子问题不重复计算，时间复杂度降低，时间复杂度O(nM)。
四、 实验源代码
#include <stdio.h>
#include <stdlib.h>
#define INFINITY 32767 //无穷大
#define MAX 100
/*b[i][j]==-1 子问题未计算，递归计算
b[i][j]!=-1 子问题已计算，直接取计算结果
另外,也可从b[i][j]算出各种面额的钞票数*/
int DynamicMemory(int t[], int i ,int j,int b[][MAX])
{
if(i==1)
{
if(j%t[1]==0)
b[i][j]=j/t[1];
else
b[i][j]=INFINITY;
return b[i][j];
}
else{
int x;
if(b[i-1][j]==-1)
x=DynamicMemory(t,i-1,j,b);
else
x=b[i-1][j];

if(j<t[i])
{
b[i][j]=x;
return x;
}
else
{
int y;

if(b[i][j-t[i]]==-1)
y=DynamicMemory(t,i,j-t[i],b);
else
y=b[i][j-t[i]];

b[i][j]=(x>y+1)?(y+1):x;
return b[i][j];
}
}
}
void main()
{
system("title 软件3班 王建君 20122668 动态规划实现找零问题");
int t[10],n,M;//n--钞票面额的个数 M--要找的钱数
t[0]=0;
printf("请输入钞票面额的种数:\n");
scanf("%d",&n);
printf("请依次输入%d种钞票的面额:\n",n);
for(int i=1;i<=n;i++)
scanf("%d",&t[i]);
printf("请输入要找零的钱的总数:\n");
scanf("%d",&M);
int b[MAX][MAX];
int p[MAX]={0};
for(i=0;i<MAX;i++)
for(int j=0;j<MAX;j++)
b[i][j]=-1;
int x=DynamicMemory(t,n,M,b);
if(x==INFINITY)
printf("无解!\n");
else{
printf("找零钞票总数：%d\n",x);
int r=M;
int k=n;
while(r>0)
if(r<t[k])
{
p[k]+=0;
k=k-1;
}
else if(b[k][r]==b[k][r-t[k]]+1)
{
p[k]+=1;
r=r-t[k];
}
else
{
p[k]+=0;
k=k-1;
}
for(k=n;k>=1;k--)
{
if(p[k]!=0)
printf("面额为%d的钞票数：%d\n",t[k],p[k]);
}
}
}

五、 结果分析