在C++程序崩潰中使用動態編程的矩陣鏈乘法？

我寫了下面的C++程序來實現使用動態編程實現MCM。但是下面的程序崩潰了。我的代碼有什麼問題？在C++程序崩潰中使用動態編程的矩陣鏈乘法？

#include<iostream> 
#include<cstdlib> 
#define SZ 10 
using namespace std; 

int table[SZ][SZ]; 
int P[] = {2,3,3,5}; 

int MCM(int i, int j) 
{ 
    if(i==j) return 0; 

    else 
    { 
     int min = INT_MAX; 

     for(int k=i;k<=j;k++) 
     { 
      if(table[i][k]==0) 
       table[i][k] = MCM(i,k); 
      if(table[k+1][j]==0) 
       table[k+1][j] = MCM(k+1,j); 
      int sum = table[i][k] + table[k+1][j] + P[i-1]*P[j]*P[k]; 
      if(sum<min) 
       min = sum; 
     } 
     return min; 
    } 
} 

int main() 
{ 
    int size = sizeof(P)/sizeof(P[0]); 
    printf("Minimum number of mutiplications is %d",MCM(0,size-1)); 
    return 0; 
}

來源

2014-09-30 Akash Rana

是否有任何錯誤消息顯示？ – 2014-09-30 12:24:32

@BobJarvis沒有程序只是崩潰。 – 2014-09-30 12:25:14

這是學習如何使用調試器的好時機。 – 2014-09-30 12:25:20

哦，我有什麼不對這個它只是一個小的失誤

就應該在第17行應該在條件結束

k<j

，而不是循環在

k<=j

程序編譯並運行成功

#include<iostream> 
#include<cstdlib> 
#define SZ 10 
using namespace std; 

int table[SZ][SZ]; 
int P[] = {1, 2, 3, 4, 3}; 

int MCM(int i, int j) 
{ 
    if(i==j) return 0; 

    else 
    { 
     int min = INT_MAX; 

     for(int k=i;k<j;k++) // bug was here: for(int k=i;k<=j;k++) 
     { 
      if(table[i][k]==0) 
       table[i][k] = MCM(i,k); 
      if(table[k+1][j]==0) 
       table[k+1][j] = MCM(k+1,j); 
      int sum = table[i][k] + table[k+1][j] + P[i-1]*P[j]*P[k]; 
      if(sum<min) 
       min = sum; 
     } 
     return min; 
    } 
} 

int main() 
{ 
    int size = sizeof(P)/sizeof(P[0]); 
    printf("Minimum number of mutiplications is %d",MCM(1,size-1)); 
    return 0; 
}

來源

2014-09-30 12:43:27

首次MCM（0，大小-1）被調用時，參數i = 0，但你減去1，並使用所得-1訪問[-1]（上線23）p 。這可能會導致崩潰。

來源

2014-09-30 12:27:37

修復之後，程序崩潰，我認爲功能的參數有問題，但我無法弄清楚。 – 2014-09-30 12:33:45

您的代碼將無限循環。此外，你犯了一些錯誤：

你從未在表中分配過最佳值（當你發現最小總和時，你沒有存儲它）。因此，每次你檢查表時[i] [j] == 0，這是真的
K的你的循環可以等於j和你正在使用K + 1，這是一個錯誤

無論如何，我認爲你的代碼的正確的版本應該是這樣的：

#include<iostream> 
#include<cstdlib> 
#define SZ 10 
using namespace std; 

int table[SZ][SZ]; 
int P[] = {1,2,3,4}; 

int MCM(int i, int j) 
{ 
    if(i==j) return 0; 

    else 
    { 
     int min = INT_MAX; 

     for(int k=i;k<j;k++) 
     { 
      if(table[i][k]==0) 
       table[i][k] = MCM(i,k); 
      if(table[k+1][j]==0) 
       table[k+1][j] = MCM(k+1,j); 
      int sum = table[i][k] + table[k+1][j] + P[i]*P[j]*P[k]; 
      if(sum<min) 
       min = sum; 
     } 
     table[i][j] = min; 
     return min; 
    }

}

int main() 
{ 
    int size = sizeof(P)/sizeof(P[0]); 
    printf("Minimum number of mutiplications is %d",MCM(0,size-1)); 
    return 0; 
}

來源

2014-09-30 12:50:46 MSH

在C++程序崩潰中使用動態編程的矩陣鏈乘法？

回答

相關問題