std :: bad_alloc в гауссовом исключении, написанном на основе псевдокода - PullRequest
Новая
       10

std :: bad_alloc в гауссовом исключении, написанном на основе псевдокода

0 голосов
/ 14 ноября 2018

Я использовал этот псевдокод: 

 h := 1 /* Initialization of the pivot row */
 k := 1 /* Initialization of the pivot column */
 while h ≤ m and k ≤ n
   /* Find the k-th pivot: */
   i_max := argmax (i = h ... m, abs(A[i, k]))
   if A[i_max, k] = 0
     /* No pivot in this column, pass to next column */
     k := k+1
   else
      swap rows(h, i_max)
      /* Do for all rows below pivot: */
      for i = h + 1 ... m:
         f := A[i, k] / A[h, k]
         /* Fill with zeros the lower part of pivot column: */
         A[i, k]  := 0
         /* Do for all remaining elements in current row: */
         for j = k + 1 ... n:
            A[i, j] := A[i, j] - A[h, j] * f
      /* Increase pivot row and column */
      h := h+1 
      k := k+1

Чтобы написать этот код (исключение Гаусса): 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

typedef std::vector<std::vector<int>> matrix;
typedef long long ll;

void inverse_matrix(matrix &mat)
{
    ll h = 1, k =1;
    auto m = mat.size(), n = mat[0].size();


    while (h <= m && k <= n)
    {
        ll i_max = 0;
        for (ll i = h; i <= m; ++i)
        {
            i_max = std::fmax(i, std::abs(mat[i][k]));
        }

        if (mat[i_max][k] == 0)
        {
            ++k;
        }

        auto temp = mat[h];
        mat[h] = mat[i_max];
        mat[i_max] = temp;

        for (auto j = h + 1; j <= m; ++j)
        {
            auto f = mat[j][k] / mat[h][k];
            mat[j][k] = 0;

            for (auto v = k + 1; v <= n; ++v)
            {
                mat[j][v] = mat[j][v] - mat[h][j] * f;
            }
        }

        ++h;
        ++k;
    }
}

int main() {
    matrix mat = {{2, 2}, {4, 5}};
    inverse_matrix(mat);

    return 0;
}

Но я получаю эту ошибку:

завершение вызова после выброса экземпляра 'std :: bad_alloc' what (): std :: bad_alloc

Это приложение запросило среду выполнения, чтобы завершить его необычным способом.Пожалуйста, обратитесь в службу поддержки приложения для получения дополнительной информации.

Что не так?Я скопировал псевдокод на тройник.

1 Ответ

0 голосов
/ 14 ноября 2018

У вас есть несколько вопросов здесь.

Во-первых, вы неправильно скопировали код (например, строка 5 псевдокода - включая строку комментария).То, что вы должны искать, это индекс максимального значения, вместо этого вы сравниваете значение с индексом.Что еще хуже, вы делаете это таким образом, что в итоге сохраняется только окончательное сравнение, потому что вы перезаписываете все остальные результаты.

Во-вторых, псевдокод запускает индексы с 1-n, как вы знаете, C ++ не делает, вместо этого мы используем индексирование на основе 0.Что касается ошибки, std::bad_alloc указывает на то, что выделение не удалось, это, скорее всего, строка: auto temp = mat[h];, где h выходит за пределы из-за вашего подхода подсчета на основе 1.

Возможно, в качестве примечания, вы также можете заменить свой своп std::swap, это может немного улучшить производительность, так как оно, вероятно, позволит избежать копирования и полагаться на перемещение вместо этого.

...