Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 52, средняя оценка - 4.83
Nuclear_Razor
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 104
Записей в блоге: 1
Завершенные тесты: 1
#1

Улучшение алгоритма вычисления определителя матрицы, порядка n>3 - C++

22.07.2012, 06:21. Просмотров 6568. Ответов 8
Метки нет (Все метки)

Всем доброго времени суток, я достаточно долго искал шаблон кода для вычисления определителя квадратной матрицы, нашел на просторах рунета более-менее нормальный алгоритм, все считает верно для матрицы размерностей n=1,2,3; Но уже при 4-ом порядке считает абсолютно неправильно.

Шаблон программы:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int det (int a[10][10], int razm)   //Нахождение определителя
//int a[10][10]; int I=0; - массив и размерность (I-строки) указаны в главной функции
{
int l;
int d;
double sum11=1,sum12=0, sum21=1, sum22=0;
//Находим детерминант
if(razm==1)
{
        return a[0][0];
}
    if(razm==2)
    {
 
            return (a[0][0]*a[1][1]-a[0][1]*a[1][0]);
    
    }
        for (int i=0;i<razm;i++)
        {
                sum11=1; l=2*razm-1-i;sum21=1;
        for (int j=0;j<razm;j++)
        {
            sum21*=a[j][l%razm];
            l--;
            sum11*=a[j][(j+i)%(razm)];
        }
        sum22+=sum21;
        sum12+=sum11;
    }
    d=sum12-sum22;
return d;
}
Честно говоря, я не учусь на программиста, а только на физика), но мне бы хотелось довести до ума мою программу, основная программа производит вычисление СЛАУ методом Гаусса, корни находит верно, но нужен алгоритм, доступный и понятный, без всяких указателей (я ими не умею практически пользоваться).

P.S. Встречал много отзывов о неправильности использования рекурсии для нахождения детерминанта? С чем это может быть связано?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.07.2012, 06:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Улучшение алгоритма вычисления определителя матрицы, порядка n>3 (C++):

Оптимизация алгоритма вычисления определителя матрицы - C++
Здравствуйте! Написал я давеча программку, которая считает определитель. Только вот беда - он не считает определители матриц выше 10...

Код вычисления определителя матрицы до 10-го порядка - C++
Мне очень нужен код программы для вычисления определителя матрицы до 10-го порядка.

Нахождение определителя матрицы n-го порядка без рекурсии - C++
Здравствуйте, мне на дом дали задачу на С++ написать программу которая находит определитель матрицы n го порядка, я довольно быстро её...

Рекурсивный метод вычисления определителя матрицы - C++
суть в том, что не получается реализовать рекурсивный метод Determinant в классе Matrix. #include &lt;iostream&gt; using namespace std; ...

Написать функцию для вычисления определителя матрицы - C++
Нужна функция для вычисления ОПРЕДЕЛИТЕЛЯ матрицы, аргументами которой будет количество строк в матрице N и сама матрица. п.с. или ссылку...

Создать функцию для вычисления определителя матрицы 2х2 - C++
Создать функцию для вычисления определителя матрицы 2х2. (в C++) HELP ME PLEASE

8
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 06:58 #2
Честно говоря, я не учусь на программиста, а только на физика), но мне бы хотелось довести до ума мою программу, основная программа производит вычисление СЛАУ методом Гаусса, корни находит верно, но нужен алгоритм, доступный и понятный, без всяких указателей (я ими не умею практически пользоваться).

P.S. Встречал много отзывов о неправильности использования рекурсии для нахождения детерминанта? С чем это может быть связано?
Насколько мне известно, основная проблема возникает в исключении строк и слобцов. Т.е, если у тебя матрица 5х5, ты взял некоторую строку и идешь по ней с целью получить 5 матрив 4х4 с умножением на соответствующий элемент. Так вот, эти 4х4-матрицы получаются путем исключения строки и столбца. Некоторые это забывают или просто не знают, как сделать.
p.s Замечу так же, что алгоритм, который я описал хоть и верен, но работать будет дольше всего возможного, ибо для 100х100 матрицы мы получим 100 матриц 99х99, а от каждой из 99х99 получим ещё по 99 98х98, и того за два шага уже 9900 матриц. К матрице 2х2 у нас будет ну очень много всего:<
1
Nuclear_Razor
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 104
Записей в блоге: 1
Завершенные тесты: 1
22.07.2012, 07:08  [ТС] #3
nexen, получается, что мне придется использовать совершенно другой алгоритм для n>3 && n<10 ? Я где-то видел на этом форуме алгоритм вычисления определителя методом Гаусса, но он был настолько наворочен, что я вообще не понял о чем там речь .
0
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 07:24 #4
Nuclear_Razor, если я правильно помню, то алгоритм Гаусса заключается в том, чтобы привести одну строку/столбец к виду вектора, где только один элемент не 0, благодоря чему из матрицы 100х100 получается матрица 99х99 умноженная на некоторое Aij, при этом матрица 99х99 одна.

Ну так для n>3 больше нет "общей формулы". Для n=2 есть формула перекрестного умножения. У вас это :
C++
1
 return (a[0][0]*a[1][1]-a[0][1]*a[1][0]);
Для n=3 есть метод треугольников или диагоналей/прямых (по-разному называют).
Для n>3 уже нужно приводить к виду n=2 или n=3. Проще всего к n=3, а там уже треугольником, но n=2 тоже нужно прописать по причине того, что матрица изначально может быть 2х2
1
Nuclear_Razor
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 104
Записей в блоге: 1
Завершенные тесты: 1
22.07.2012, 07:40  [ТС] #5
nexen, для n=3, данный алгоритм считает все правильно , есть еще другой код:

Инициализация матрицы:

C++
1
2
3
4
5
6
7
8
9
10
a = (double *) malloc(m * n * sizeof(double));
printf("Введите элементы матрицы:\n");
for (i = 0; i < m; ++i) 
{
for (j = 0; j < n; ++j) 
{
// Вводим элемент с индексами i, j
scanf("%lf", (a+i*n + j));
}
}
Код вычисления определителя:

C++
1
2
3
4
5
6
7
8
if (m == n) 
{
// Для квадратной матрицы вычисляем и печатаем
// ее определитель
det = 1.0;
for (i = 0; i < m; ++i) {
det *= *(a+i*n + i);
}
Было бы не плохо это перевести на язык обычных массивов, этот шаблон я из книжки одной взял.
Хотя бы тут определитель правильно вычисляется, но вот перенести в мой код никак не удается .
0
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 08:38 #6
Nuclear_Razor, если честно, не понимаю, как это :
C++
1
2
3
4
det = 1.0;
for (i = 0; i < m; ++i) {
det *= *(a+i*n + i);
}
вычисляет определитель

Не по теме:

Наверное мне нужно выспаться

0
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2012, 08:52 #7
Цитата Сообщение от Nuclear_Razor Посмотреть сообщение
Код вычисления определителя:

C++
1
2
3
4
5
6
7
8
if (m == n) 
{
// Для квадратной матрицы вычисляем и печатаем
// ее определитель
det = 1.0;
for (i = 0; i < m; ++i) {
det *= *(a+i*n + i);
}
Очень даже правильно, НО только для матриц, приведенных к ступенчатому виду. Здесь перемножаются диагональные элементы матрицы. Для произвольной квадратной матрицы алгоритм неверен.
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 09:00 #8
Thinker, вот как, даже не подумал. Тогда да, это как раз и есть Гаусс. Вот только алгоритм приведения к ступенчатому виду будет.. кхм.. более масшатбный что ли.
0
Nuclear_Razor
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 104
Записей в блоге: 1
Завершенные тесты: 1
23.07.2012, 01:56  [ТС] #9
Получается, что мне придется искать алгоритмы для приведения матриц к ступенчатому виду? А потом тестировать на этом алгоритме:

C++
1
2
3
4
5
6
7
8
if (m == n) 
{
// Для квадратной матрицы вычисляем и печатаем
// ее определитель
det = 1.0;
for (i = 0; i < m; ++i) {
det *= *(a+i*n + i);
}
Да, кстати, пытался разобрать с aglib, туча-тучная). По-моему с помощью предложенных там библиотек, все сделать получится труднее, нежели использовать стандартные библиотеки.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2012, 01:56
Привет! Вот еще темы с ответами:

Улучшение алгоритма записи строк - C++
В общем код полностью рабочий. В функции fill_start_file происходит запись в файл с условием, что строка не должна быть больше 80 символов....

Улучшение алгоритма подсчета строк, букв, слов - C++
Данный алгоритм, компилируется. Однако есть недочеты: 1. Не всегда верно считает буквы. Почему не очень понимаю. 2. Два спейса...

Вычисления матрицы любого порядка - C++
Есть какой либо алгоритм или формула для вычисления матрицы любого порядка? Или же для каждого порядка писать отдельный код?

Подстроение алгоритма определителя - C++
Доброго времени суток уважаемые форумчане! Мне уже надоело искать нормальный и рабочий алгоритм для вычисления определителя. Есть два кода:...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Yandex
Объявления
23.07.2012, 01:56
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru