1

Тема: Есть вопрос

Хочу уточнить код алгоритма "Вычисление определителя матрицы методом Гаусса", а именно:

    
for (int j=i+1; j<=n; ++j)
        a[i][j] /= a[i][i];

Тогда как в самом начале алгоритма указано:

vector < vector<double> > a (n, vector<double> (n));

.

IMHO вышеприведенный цикл следует заменить на следующий:

    
for (int j=i+1; j<n; ++j)
        a[i][j] /= a[i][i];

т. к. происходит выход за границы массива при j==n.

2

Re: Есть вопрос

Спасибо, совершенно верно.

Такое произошло, потому что код был взят из статьи "Метод Гаусса решения системы линейных уравнений", в которой матрица была Nx(N+1). При вычислении определителя же, конечно, матрица квадратная.

3

Re: Есть вопрос

В статье "Алгоритм Левита нахождения кратчайших путей от заданной вершины до всех остальных вершин за O (N M)" различаются название статьи и то, что непосредственно указано в заголовке браузера.

4

Re: Есть вопрос

AlexErofeev
Исправил. Вообще этот алгоритм висит у меня "under investigation". Конечно, за линейное время он точно не работает. Но есть подозрение, что и за время N M тоже, т.е., возможно, есть тесты, на которых он работает экспоненциально. Как найду время, постараюсь решить этот вопрос.

Правда, это не отменяет того, как хорошо он отрабатывает на практике, особенно в задаче максимального потока минимальной стоимости.

5

Re: Есть вопрос

Привет! Я нашел 2 опечатки в статье "Задача 2-SAT":


1. "Если comp[x] < comp[!x], то переменной x выбираем значение true, иначе - false."

Должен быть знак >.


2. "int ans = comp[ i ] > com[i^1] ? i : i^1;"

не com[i^1] а comp[i^1]

6

Re: Есть вопрос

Victor Barionov
спасибо, fixed

7

Re: Есть вопрос

нашел еще одну неточность. Сорри, что пишу сюда -- зарегистрироваться лень, а куда писать такие вещие не нашел.

Так вот, в статье "Алгоритм Евклида нахождения НОД (наибольшего общего делителя)" внизу написан такой код:

int lcm (int a, int b) {
    return a * b / gcd (a, b);
}

Думаю, что надежнее писать не
a * b / gcd(a, b)

а

a / gcd(a, b) * b

Это поможет избежать переполнения в некоторых случаях.