Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/13: Рейтинг темы: голосов - 13, средняя оценка - 5.00
 Аватар для Fixer_84
1505 / 968 / 812
Регистрация: 30.04.2016
Сообщений: 3,334
1

Метод решения СЛАУ

19.06.2017, 19:01. Показов 2653. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте! Вот задача с E-Olymp (сложность 91%). Есть решение, но ни один тест не пройден, хотя полностью совпадает с онлайн-сервисами. Суть - решить систему линейных алгебраических уравнений (СЛАУ). Во многих тестах превышен лимит памяти. Так как в условии сказано ровно одно решение, решил использовать метод Крамера. Что я делаю не так? Хотя бы направьте в нужном направлении.

Условие:

Система линейных уравнений

Жюри потребовалось решить систему линейных уравнений.

Помогите им в этом - напишите программу, решающую эту систему.

Входные данные:

Первая строка входного файла содержит одно число n (1 ≤ n ≤ 100). Каждая из следующих n строк содержит описание очередного уравнения - n+1 чисел ai1, ai2, ..., ain, bi. Все эти числа вещественные. Гарантируется, что система имеет ровно одно решение.

Выходные данные:

В выходной файл выведите числа x1, x2, ..., xn как можно точнее.

Лимит времени 1 секунда

Лимит использования памяти 64 MiB

Входные данные:

2
1 1 3
1 -1.5 0.5

Выходные данные:

2.0000 0.999999999999999

Как вывести как можно точнее?

Мой код:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <cmath>
#include <fstream>
 
using namespace std;
 
double DetValue(double** A, int N)
{
    int p, h, k;
    double det = 0;
    double** B = new double*[N];
    for (int i = 0; i < N; i++)
    {
        B[i] = new double[N];
    }
    if (N == 1)
        return A[0][0];
    else if (N == 2)
    {
        det = (A[0][0] * A[1][1] - A[0][1] * A[1][0]);
        return det;
    }
    else
    {
        for (int p = 0; p < N; p++)
        {
            h = k = 0;
            for (int i = 1; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    if (j == p)
                        continue;
                    B[h][k] = A[i][j];
                    k++;
                    if (k == N - 1)
                    {
                        h++;
                        k = 0;
                    }
                }
            }
            det = det + A[0][p] * pow(-1, p) * DetValue(B, N - 1);
        }
    }
    for (int i = 0; i < N; i++)
    {
        delete [] B[i];
    }
    delete [] B;
    return det;
}
 
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N;
    double tmp, det, dTemp;
    fin >> N;
    double** A = new double*[N];
    for (int i = 0; i < N; i++)
    {
        A[i] = new double[N];
    }
    double*** B = new double**[N];
    for (int i = 0; i < N; i++)
    {
        B[i] = new double*[N];
        for (int j = 0; j < N; j++)
            B[i][j] = new double[N];
    }
    double* X = new double[N];
    double* root = new double[N];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            fin >> A[i][j];
        }
        fin >> X[i];
    }
    for (int k = 0; k < N; k++)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                B[k][i][j] = A[i][j];
            }
        }
    }
    for (int k = 0; k < N; k++)
    {
        for (int i = 0; i < N; i++)
        {
            B[k][i][k] = X[i];
        }
    }
    dTemp = DetValue(A, N);
    for (int i = 0; i < N; i++)
    {
        root[i] = DetValue(B[i], N) / dTemp;
        fout << root[i] << " ";
    }
    fout.close();
    fin.close();
    for (int i = 0; i < N; i++)
    {
        delete [] A[i];
    }
    delete [] A;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            delete [] B[i][j];
        }
        delete [] B[i];
    }
    delete [] B;
    delete [] X;
    delete [] root;
    system("pause");
    return 0;
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
19.06.2017, 19:01
Ответы с готовыми решениями:

Матричный метод решения СЛАУ
Здравствуйте уважаемые програмисты, не могу осилить данный метод, и в нете инфы очень мало, может у...

Метод Гаусса (подстановки) решения СЛАУ
Всем доброго времени суток, написал я одну недопрограмму, потому как сделал её наполовину. Не...

Метод Холецкого для решения Слау
Ты не мог бы выложить программу?

Метод Зейделя для решения слау
Пытаюсь реализовать метод Зейделя, подсмотрев реализацию в Википедии, написала функцию Itera(). Она...

4
 Аватар для palva
4256 / 2952 / 688
Регистрация: 08.06.2007
Сообщений: 9,860
Записей в блоге: 4
19.06.2017, 19:15 2
Используйте метод Гаусса с выбором главного элемента. Формулы Крамера имеют значение для теории, но потребляют очень много вычислительных ресурсов.
1
1718 / 567 / 187
Регистрация: 12.03.2016
Сообщений: 2,169
19.06.2017, 19:40 3
Цитата Сообщение от palva Посмотреть сообщение
но потребляют очень много вычислительных ресурсов.
palva, в данном случае ресурсы это
Цитата Сообщение от Fixer_84 Посмотреть сообщение
pow(-1, p)
Цитата Сообщение от Fixer_84 Посмотреть сообщение
double*** B = new double**[N];
И это только на первый взгляд.
Если так подходить к алгоритмам, то и другие методы не помогут.
1
 Аватар для Fixer_84
1505 / 968 / 812
Регистрация: 30.04.2016
Сообщений: 3,334
19.06.2017, 19:47  [ТС] 4
мановар, спасибо за ваше замечание. Нужно было построить массив матриц для реализации метода, поэтому решил использовать трехмерный массив.

Добавлено через 2 минуты
palva, спасибо. Метод Гаусса правда работает намного быстрее.
0
1718 / 567 / 187
Регистрация: 12.03.2016
Сообщений: 2,169
19.06.2017, 19:57 5
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Метод Гаусса правда работает намного быстрее.
Метод Крамера при большом количестве неизвестных стараются не использовать и заменяют другими методами. Но у них могут быть свои ограничения, смотрите не попадите на них.
1
19.06.2017, 19:57
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
19.06.2017, 19:57
Помогаю со студенческими работами здесь

Метод Гаусса для решения СЛАУ
Здравствуйте! У меня есть алгоритм решения СЛАУ методом Гаусса, но почему-то он не работает((( Я...

Метод Гаусса для решения СЛАУ
Добрый день! Реализовал метод Гаусса для решения СЛАУ. Но проблема с получением ответа. Второй и...

Метод простых итераций для решения СЛАУ
Здравствуйте. Попытался сделать программу для решения СЛАУ методом простых итераций. Не работает....

Метод простых итераций для решения СЛАУ
Всем добрый вечер! Столкнулся с заданием на тему решения СЛАУ методом простых итераций и Зейделя. ...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
[Golang] 121. Best Time to Buy and Sell Stock
alhaos 28.01.2025
В этой задаче мы получаем слайс целых чисел, которые означают цену акции в разные моменты времени, и должны вернуть максимально возможную прибыль от купли продажи акции. / / . . .
Проектирование и моделирование
hw_wired 28.01.2025
Введение в моделирование Моделирование представляет собой один из фундаментальных методов научного познания, который позволяет изучать объекты и явления через создание их упрощенных аналогов. В. . .
Алгоритмы и исполнители
hw_wired 28.01.2025
Введение в алгоритмы В современном мире информационных технологий алгоритмы играют основополагающую роль в решении различных задач и автоматизации процессов. Алгоритм представляет собой точную. . .
Хранение информации
hw_wired 28.01.2025
Введение: Роль систем хранения информации в современном мире В современную эпоху цифровых технологий эффективное хранение информации становится одним из ключевых факторов успешного развития любой. . .
Обработка числовой информации
hw_wired 28.01.2025
Введение в обработку числовой информации В современном мире обработка числовой информации стала неотъемлемой частью как профессиональной деятельности, так и повседневной жизни. Электронные таблицы. . .
Мультимедиа
hw_wired 28.01.2025
Введение в мультимедийные технологии В современном мире мультимедийные технологии стали неотъемлемой частью нашей жизни, проникнув во все сферы человеческой деятельности. Термин "мультимедиа". . .
Обработка текстовой информации
hw_wired 28.01.2025
Введение в обработку текстовой информации В современном мире обработка текстовой информации играет фундаментальную роль в различных сферах человеческой деятельности. Текстовые редакторы стали. . .
Обработка графической информации
hw_wired 28.01.2025
Введение в компьютерную графику Компьютерная графика стала неотъемлемой частью современного цифрового мира, пройдя впечатляющий путь развития от простейших черно-белых изображений до сложных. . .
Python в Алгоритмике: Решение задач
hw_wired 28.01.2025
Введение в Python и Алгоритмику В современном мире программирование стало неотъемлемой частью образования и профессионального развития. Python зарекомендовал себя как один из самых популярных и. . .
Компьютер как универсальное устройство для работы с информацией
hw_wired 28.01.2025
Введение в устройство компьютера Компьютер представляет собой универсальное электронное устройство, предназначенное для автоматической обработки информации. В современном мире компьютер стал. . .
Информация и информационные процессы
hw_wired 28.01.2025
Понятие информации и ее виды В современном мире информация является одним из фундаментальных понятий, пронизывающих все сферы человеческой деятельности. Под информацией понимают любые сведения об. . .
Алгоритмика
hw_wired 28.01.2025
Введение: Основы алгоритмики и её роль в информатике В современном мире программирование и алгоритмическое мышление стали неотъемлемой частью образования и профессиональной деятельности. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru