二维数组做参数--矩阵连乘问题 - 编程论坛

#2

aipb20072007-10-23 11:14

确实是参数越界了，上溢，下溢都存在。

你的m,s是定义的size = 6,那么实际取值就是 0 1 2 3 4 5

这与矩阵的对应就不是1，1对应。
比如m[0][5]表示1-6的矩阵连乘的最小代价

你自己检查算法中p的取值范围，应该注意+1
更好的办法是定义m,s的size=7，那么浪费m[0][i]m[i][0]不用，而直接与矩阵11对应。

算法是没有问题的。

#3

nuciewth2007-10-23 12:01

DP法,算法上没有错误.是这样.
求MatrixChain函数是没有错的.
还有参数并没有溢出,定义的行参最好不要把写成这样,你可以直接用**m,等二级指针来表示
最大的错误就是下面的递归没有出口
void Traceback(int i,int j,int **s)
{
if(i==j)cout<<"no-op"<<endl;//应该在这个条件里结束递归
Traceback(i,s[i][j],s);
Traceback(s[i][i]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<"and A"<<(s[i][j]+1)<<","<<j<<endl;
}

#4

aipb20072007-10-23 21:36

m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];

i是可以取到0的，所以p[0-1]越界。

还有，直接用**m形式的指针来引用2维数组是错的。

可以用int[][N]或者int (*)[N]

#5

diaoxue2007-10-25 08:46

我改了后调试没出错，但运行时出错

#6

jonc2007-11-10 10:18

就是数组越界
void MatrixChain(int p[],int n,int m[6][6],int s[6][6])
{
for(int i=0;i<n;i++)m[i][i]=0;
for(int r=1;r<n;r++)
for(int i=0;i<n-r+1;i++)
{
int j=i+r-1;
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];// 中上下都溢出
s[i][j]=i;
for(int k=i+1;k<j;k++)
{
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}

#7

diaoxue2007-11-10 17:05

回复：（diaoxue）我改了后调试没出错，但运行时出错

我写的好多关于数组的程序都溢出了
下标是从0开始吧有什么要注意的吗

#8

diaoxue2007-11-18 17:20

回复：（jonc）就是数组越界void MatrixChain(int p[]...

的确是越界了
我写的好多程序都是这样编译没错，运行就不行了
想了好久，还是不能解决
能否给点指点啊

#9

neverDie2007-11-18 19:42

说明你思路不清晰

#10

codelet2007-11-19 09:13

自己设几个断点，跟踪一下程序，就容易发现问题在哪了

#11

diaoxue2007-11-20 09:09

回复：（nuciewth）DP法,算法上没有错误.是这样.求Mat...

你说在那儿结束递归,我用return语句可以吧
我把参数改为从1开始可以吧
可是我改了后还不行
我改后的程序
#include<iostream.h>
void MatrixChain(int p[],int n,int m[6][6],int s[6][6]);
int Traceback(int i,int j,int s[6][6]);
int main()
{
int p[]={30,35,15,5,10,20,25};
int n=6;
int m[6][6];
int s[6][6];
MatrixChain(p,n,m,s);
int i=1,j=6;
Traceback(i,j,s);
return 0;
}
void MatrixChain(int p[],int n,int m[6][6],int s[6][6])
{
for(int i=1;i<=n;i++)m[i][i]=0;
for(int r=2;r<=n;r++)
for(int i=1;i<=n-r+1;i++)
{
int j=i+r-1;
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1;k<j;k++)
{
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
int Traceback(int i,int j,int s[6][6])
{
if(i==j)return 0;//cout<<"no-op"<<endl;
Traceback(i,s[i][j],s);
Traceback(s[i][i]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<"and A"<<(s[i][j]+1)<<","<<j<<endl;
}

[此贴子已经被作者于2007-11-20 9:11:57编辑过]

#12

zjl1382007-11-20 12:27

刚学矩阵,受教了

#13

aipb20072007-11-20 13:46

[CODE]/*
题目：矩阵链乘法
问题描述：
给定N个矩阵构成一个链<A1,A2,A3，…,An>，其中i=1，2，…n，矩阵Ai的维数为
Pi-1 * Pi，对乘积A1A2A3…An以一种最小化标量乘法次数的方式进行加全部括号。

from：Introduction to Algorithms Page 331
*/
#include <iostream>
using namespace std;
const int MAX = 101;
#define N 6
int dp[MAX][MAX]; //for storing best sub-slutions
//2d array use the part(i<=j) dp[i][j] to store minnimum time for multiply of Ai..Aj
//the rest part(i>j) dp[j][i] to store best divider of Ai..Aj
int p[N+1] = {30,35,15,5,10,20,25}; //matrix list
/* versin1
//recursive function to print the solution
void print(int (*)[MAX],int,int);
int main(){
//dynamic programming for the problem
//down-top approach

//use the length increasing to make the dp table
int i,j,l,k,t;
for (i = 1;i <= N;++i)
dp[i][i] = 0; //no cost if only 1 matrix (length is 1)

for (l = 2;l <= N;++l)
for (i = 1;i <= N-l+1;++i){
j = i+l-1;
for (k = i;k <= j-1;++k){
t = dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];
if (k == i || dp[i][j] > t){
dp[i][j] = t;
dp[j][i] = k;
}
}
}

//the the dp over and the problem is sloved

//print the answers

cout << "minimum multiply of the matrix list is : " << dp[1][N] << endl;
print(dp,N,1);

cout << endl;

//for testing
// for (int m = 1;m <= N;++m){
// for (int n = 1;n <= N;++n)
// cout << dp[m][n] << " ";
// cout << endl;
// }

system("pause");
}
*/
void print(int (*dp)[MAX],int j,int i){
if (j == i)
cout << "A" << i;
else{
cout << "(";
print(dp,dp[j][i],i);
print(dp,j,dp[j][i]+1);
cout << ")";
}
}
//use memo technology to solve problem of top-down approach
int memo_lookup(int (*dp)[MAX],int *p,int i,int j){
if (dp[i][j] >= 0)
return dp[i][j];
if (i == j)
dp[i][j] = 0;
else
for (int k = i,t;k < j;++k){
t = memo_lookup(dp,p,i,k)+memo_lookup(dp,p,k+1,j)+p[i-1]*p[k]*p[j];
if (dp[i][j] < 0 || t < dp[i][j])
dp[i][j] = t;
}
return dp[i][j];
}
int solution(int (*dp)[MAX],int *p,int i,int j){
for (int m1 = 1;m1 <= j;++m1)
for (int m2 = m1;m2 <= j;++m2)
dp[m1][m2] = -1;
return memo_lookup(dp,p,i,j);
}

int main(){

cout << "minimum multiply of the matrix list is : "
<< solution(dp,p,1,N) << endl;
system("pause");
}

/*
使用动态规划的两个要素：1）最优子结构；2）子问题独立重叠

*/ [/CODE]

学习笔记，注意注释代码，看懂了应该可以自行选择运行。