-1

在过去的两个小时里，我一直被这个小虫子困住，现在我绝望了。非常感谢任何帮助！

该算法用于为Longest Common Subsequence两个序列之间的问题制作矩阵。并且该矩阵被用作动态规划方法中的参考表。粘贴相关代码

#include <vector>
#include <cstdio>
#include <math.h>

using namespace std;
int main()
{
  vector<int> A, B;
  A.push_back(0);
  A.push_back(15);
  A.push_back(20);
  B.push_back(0);
  B.push_back(20);
  B.push_back(15);

  int a = 2;
  int b = 2;
  int matrix[a][b];
  memset(matrix, 0, sizeof(int)*a*b);

  for (int i = 0; i <= a; ++i)
  {
    for (int j = 0; j <= b; ++j)
    {
      if (i == 0 || j == 0)
      {
        matrix[i][j] = 0;
      } else 
      {
        if (A[i] == B[j])
        {
          matrix[i][j] = matrix[i - 1][j - 1] + 1;
          printf("matrix at row %i column %i: %i\n", i, j, matrix[i][j]);
        } else
        {
          matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1]);
        }
      }
    }
  }
  printf("matrix at row 1 column 2: %i\n", matrix[1][2]);
  printf("matrix at row 2 column 1: %i\n", matrix[2][1]);
}

如果我编译并运行它

g++ -Wall soquestion1.cpp -o soquestion1
./soquestion1

我明白了

matrix at row 1 column 2: 1
matrix at row 2 column 1: 1
matrix at row 1 column 2: 0     #WTHHHHHH, who changed my matrix!?
matrix at row 2 column 1: 1

感谢您阅读那么远。

4

2 回答 2

2 
for (int i = 0; i <= a; ++i)
  {
    for (int j = 0; j <= b; ++j)
    {

这是你的问题。你越界了，导致……“某事”。

让它<a和<b，你应该没问题。此外，您正在访问矩阵本身，并没有真正阅读那里的内容。您是否检查过结果应该是什么？

  printf("matrix at row 1 column 2: %i\n", matrix[1][2]);
  printf("matrix at row 2 column 1: %i\n", matrix[2][1]);

它应该是matrix[0][1]和matrix[1][0]

注意：预期结果应该是 0 和 0

于 2013-09-06T21:47:25.730 回答
1

你的代码有点乱。我清理了一些。

#include <algorithm>
#include <cstdio>

int main()
{
  int A[] = { 0, 15, 20 };
  int B[] = { 0, 20, 15 };

  const size_t MatrixDim = 3;
  int matrix[MatrixDim][MatrixDim] = { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 } }; 
  // or memset(matrix, 0, sizeof(matrix));

  // only operate on dimensions 1 and 2, leave 0,j and i,0 elements as 0. 
  for (size_t i = 1; i < MatrixDim; ++i)
  {
    for (size_t j = 1; j < MatrixDim; ++j)
    {
      if (A[i] == B[j])
      {
        matrix[i][j] = matrix[i - 1][j - 1] + 1;
        printf("a. matrix at row %i column %i: %i\n", i, j, matrix[i][j]);
      }
      else
      {
        matrix[i][j] = std::max(matrix[i - 1][j], matrix[i][j - 1]);
        printf("b. matrix at row %i column %i: %i\n", i, j, matrix[i][j]);
      }
    }
  }

  for (size_t i = 0; i < MatrixDim; ++i) {
    for (size_t j = 0; j < MatrixDim; ++j) {
      printf("%02d ", matrix[i][j]);
    }
    printf("\n");
  }
}

现场演示：http: //ideone.com/vGk4oB

输出：

a. matrix at row 1 column 2: 1
a. matrix at row 2 column 1: 1
b. matrix at row 2 column 2: 1
00 00 00 
00 00 01 
00 01 01
于 2013-09-06T22:40:50.617 回答