c++ - 基于伪代码编写的高斯消除中的 std::bad_alloc
问题描述
我使用了这个伪代码:
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
此应用程序已请求运行时以不寻常的方式终止它。请联系应用程序的支持团队以获取更多信息。
怎么了?我将伪代码复制到发球台上。
解决方案
你这里有几个问题。
首先,您没有正确复制代码(例如,伪代码的第 5 行 - 包括注释行)。您应该寻找的是最大值的索引,而不是将该值与索引进行比较。更糟糕的是,您这样做的方式最终只会存储最终比较,因为您会覆盖所有其他结果。
其次,伪代码运行从 1 到 n 的索引,正如你知道的 C++ 没有,而是我们使用基于 0 的索引。至于错误, std::bad_alloc
表明分配失败,这很可能是行: ,由于您的基于 1 的计数方法auto temp = mat[h];
,其中超出范围。h
也许作为旁注,您也可以将您的交换替换为std::swap
,这可能会稍微提高性能,因为它可能会避免复制并依赖于移动。
推荐阅读
- r - 如何将cross()函数与mutate()和case_when()结合起来,根据一个条件对多列中的值进行变异?
- javascript - TypeError:Test.findAll 不是函数调用 Mongoose Schema
- tkinter - 我无法通过 pip 安装 tkinter,错误:没有匹配的分布
- python - 如何使用 Tkinter 遍历标签中的列表?
- python - 如何在 Python 中比较两 (2) 个不相等的数据帧并将元素从一个分配到另一个?
- c# - 如何对 Asp.Net Core Mvc 控制器进行 GET Ajax 调用
- javascript - 鼠标指针无法检测到元素以触发 onClick()
- html - 如何使动态 HTML 表格数据(使用 jQuery 创建)可点击?
- javascript - discord.js 玩家姓名和分数请求问题
- java - 矩阵乘法算法复杂度