Решить систему уравнений программирование

Содержание

Метод Гаусса на Java
Теоретические сведения
Реализация
Вывод
Список использованной литературы:
Системы линейных уравнений методом Гаусса

Метод Гаусса на Java

Статья посвящена реализации алгоритма Гаусса для решения системы линейных алгебраических уравнений на языке Java.

Теоретические сведения

Рассмотрим математическую теорию. Система линейных уравнений может иметь одно решение, бесконечно много решений или же быть несовместной (не иметь решений). Не все методы решения СЛАУ могут справится с вторым случаем, когда система имеет бесконечно много решений. Например, метод Крамера и матричный метод не применимы, но метод Гаусса вполне можно использовать.

Алгоритм можно условно разделить на два этапа:

Реализация

Начнем с постановки задачи:

нам нужно создать программу, реализующую систему линейных уравнений в виде некоторой структуры данных, используя приемы обобщенного программирования. Система должна содержать коэффициенты производного типа от класса Number (т.е. Float, Integer, Double и т.д.)
Запрограммировать алгоритм, который получив на вход структуру данных системы образует нули ниже главной диагонали

package gauss; public interface Gauss>

Здесь все должно быть ясно, N некоторый наследник Number‘а, T — некоторый тип, реализующий данный интерфейс (рекурсивные дженерики). Метод addEquation(T item) позволяет прибавить каждый элемент уравнения item к каждому своему элементу. Остальные методы работают аналогично.

Теперь рассмотрим класс системы уравнений. Как видно в листинге ниже, он дженеризирован так же, как и интерфейс Gauss и содержит методы для удобного доступа к приватному списку содержащих в себе уравнений.

package gauss; import java.util.ArrayList; import java.util.List; public class LinearSystem> < private Listlist = new ArrayList(); public T get(int index) < return list.get(index); >public void push(T elem) < list.add(elem); >public int size() < return list.size(); >public N itemAt(int i, int j) < return list.get(i).at(j); >>

Теперь можно приступать к реализации «частного случая» структуры уравнения. Создадим класс MyEquation, реализующий наш интерфейс. Пусть наследником Number‘а будет ~~сверхточный~~ класс Float (на практике лучше брать Double). Обратите внимание, что в методе addEquation(MyEquation item) используется объект класса ListIterator, позволяющий изменять элементы перебираемого списка.

package gauss; import java.util.ArrayList; import java.util.List; import java.util.ListIterator; import java.util.Random; public class MyEquation implements Gauss  < private Listequation = new ArrayList(); public List getEquation() < return equation; >public void generate(int size) < if (size < 2) size = 2; this.equation.clear(); for (int i = 0; i < size; i++)< Random random = new Random(); this.equation.add((float) (random.nextInt()%10) + 1); >> @Override public int size() < return equation.size(); >@Override public void addEquation(MyEquation item) < ListIteratori = equation.listIterator(); ListIterator j = item.getEquation().listIterator(); for(; i.hasNext() && j.hasNext();) < Float a = i.next(); Float b = j.next(); i.set(a + b); >> @Override public void mul(Float coefficient) < for(ListIteratori = equation.listIterator(); i.hasNext();) < Float next = i.next(); i.set(next * coefficient); >> @Override public Float findCoefficient(Float a, Float b) < if (a == 0.0f) return 1.0f; return -b/a; >@Override public Float at(int index) < return equation.get(index); >>

Теперь имеем полноценную структуру данных, реализующую систему уравнений. Составим алгоритм который будет принимать некоторый объект, реализующий интерфейс Gauss, затем вызывая нужные методы приведет матрицу к нужному виду.

package gauss; public class Algorithm> < LinearSystemlist = null; public Algorithm(LinearSystem system) < list = system; >public void calculate() throws NullPointerException, ArithmeticException < if (list == null)< throw new NullPointerException("LinearSysteminstance equal null"); > if (!checkSystem(list)) < throw new ArithmeticException("Incorrect system for Gauss Method"); >for(int i = 0; i < list.size() - 1; i++)< for(int j = i + 1; j < list.size(); j++)< N k = list.get(j).findCoefficient(list.get(j).at(i), list.get(i).at(i)); list.get(j).mul(k); list.get(j).addEquation(list.get(i)); >> > private boolean checkSystem(LinearSystem system) < if (system.size() < 2) return false; for(int i = 0; i < system.size(); i++)< if (system.get(i).size() != (system.size() + 1))< return false; >> return true; > >

Алгоритм простой, найти нужный коэффициент, домножить на него i-ю строку (i=0..n-1), и прибавить ее к j-й строке (j=i..n). Заметьте, алгоритм не знает как именно реализуются методы findCoefficient, mul и addEquation, это придает коду бОльшую гибкость, т.к. при потребности изменить способы манипуляции уравнениями (строками), будут изменены только реализации трех вышеупомянутых методов, а главный алгоритм останется нетронутым.

Почти все. Осталось запустить это все в методе main:

import gauss.Algorithm; import gauss.MyEquation; import gauss.LinearSystem; public class Main < private static final int DEFAULT_EQUATIONS_NUMBER = 2; private static final int DEFAULT_VARIABLES_NUMBER = 2; public static void main(String args[])< LinearSystemlist = generateSystem(); printSystem(list); int i, j; Algorithm alg = new Algorithm(list); try< alg.calculate(); >catch (NullPointerException e)< System.out.println(e.getMessage()); System.exit(0); >catch (ArithmeticException e) < System.out.println(e.getMessage()); System.exit(0); >Float [] x = new Float[DEFAULT_EQUATIONS_NUMBER]; for(i = list.size() - 1; i >= 0; i--) < Float sum = 0.0f; for(j = list.size() - 1; j >i; j--) < sum += list.itemAt(i, j) * x[j]; >x[i] = (list.itemAt(i, list.size()) - sum) / list.itemAt(i, j); > printSystem(list); printVector(x); > public static LinearSystem generateSystem() < LinearSystemlist = new LinearSystem(); int i; for (i = 0; i < DEFAULT_EQUATIONS_NUMBER; i++)< MyEquation eq = new MyEquation(); eq.generate(DEFAULT_VARIABLES_NUMBER + 1); list.push(eq); >return list; > public static void printSystem(LinearSystem system) < for (int i = 0; i < system.size(); i++)< MyEquation temp = system.get(i); String s = ""; for (int j = 0; j < temp.size(); j++)< s += String.format("%f; %s", system.itemAt(i, j), "\t"); >System.out.println(s); >System.out.println(""); > public static void printVector(Float [] x)< String s = ""; for (int i = 0; i < x.length; i++)< s += String.format("x%d = %f; ", i, x[i]); >System.out.println(s); > >

Запустим это чудо, что бы проверить корректность работы…

Это все. Исходники можно скачать на github’е.

Вывод

Метод Гаусса не очень поддается обобщенному программированию (как видите обратный ход выполнен отдельно), однако вышла своеобразная реализация которая, надеюсь, поможет кому то лучше разобраться в искусстве использования интерфейсов и дженериков.

Список использованной литературы:

Источник

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

День(ночь, утро, вечер) добрый(-ая, -ое)
вопрос про метод Гаусса, как его реализовать на С++.
что-то совсем запутался.

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

#include using namespace std; int main() { int i, j, n, m; //создаем массив cout  "введи число уравнений: "; cin >> n; cout  "введи число неизвестных: "; cin >> m; m+=1; int **matrix = new int *[n]; for (i=0; in; i++) matrix[i] = new int [m]; //инициализируем cout  "vvedi element"  endl; for (i = 0; in; i++) for (j = 0; jm; j++) cin >> matrix[i][j]; //выводим массив cout  "matrix: "  endl; for (i=0; in; i++) { for (j=0; jm; j++) cout  matrix[i][j]  " "; cout  endl; } cout  endl; //Метод Гаусса //Прямой ход, приведение к верхнетреугольному виду /*Обратный ход, методом исключения неизвестных в обратном порядке решаем уравнения */ //Выводим решения delete[] matrix; return 0; }

на форуме нашел подобную тему, но там со статическим массивом( нужно с динамическим)
вот как там реализовано:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

for (i=0; iN; i++) { tmp=matrix[i][i]; for (j=N;j>=i;j--) matrix[i][j]/=tmp; for (j=i+1;jN;j++) { tmp=matrix[j][i]; for (k=N;k>=i;k--) matrix[j][k]-=tmp*matrix[i][k]; } } /*обратный ход*/ xx[N-1] = matrix[N-1][N]; for (i=N-2; i>=0; i--) { xx[i] = matrix[i][N]; for (j=i+1;jN;j++) xx[i]-=matrix[i][j]*xx[j]; }

пробовал это совсестить с тем что я написал, не работает. при выводе решений пишет одни нули.

Добавлено через 8 часов 0 минут
сделал вот так:

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

#include using namespace std; int main() { int i, j, n, m; //создаем массив cout  "введи число уравнений: "; cin >> n; cout  "введи число неизвестных: "; cin >> m; m+=1; int **matrix = new int *[n]; for (i=0; in; i++) matrix[i] = new int [m]; //инициализируем cout  "vvedi element"  endl; for (i = 0; in; i++) for (j = 0; jm; j++) cin >> matrix[i][j]; //выводим массив cout  "matrix: "  endl; for (i=0; in; i++) { for (j=0; jm; j++) cout  matrix[i][j]  " "; cout  endl; } cout  endl; //Метод Гаусса float tmp, xx[m]; int k; for (i=0; in; i++) { tmp=matrix[i][i]; for (j=n;j>=i;j--) matrix[i][j]/=tmp; for (j=i+1;jn;j++) { tmp=matrix[j][i]; for (k=n;k>=i;k--) matrix[j][k]-=tmp*matrix[i][k]; } } /*обратный ход*/ xx[n-1] = matrix[n-1][n]; for (i=n-2; i>=0; i--) { xx[i] = matrix[i][n]; for (j=i+1;jn;j++) xx[i]-=matrix[i][j]*xx[j]; } for (i=0; in; i++) cout  xx[i]  " "; cout  endl; delete[] matrix; return 0; }

ответ выводится не верный.
где неправильно.

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

#include #include #include #include #define N 3 #define N1 N+1 using namespace std; float matrix[N][N1]={{2,-1,3,2}, {1,-2,1,3}, {3,-1,3,4}}; float epsilon=0.001; void ShowMatrix(void) { cout  "SLAU:"  endl; int i,j; for (i=0 ;iN; i++) { for (j=0; jN; j++) printf("%+3.3f*x%d",matrix[i][j],i+1); printf("=%3.3f\n",matrix[i][N]); } } int main() { float tmp, xx[N1]; short int i, j, k; ShowMatrix(); /*Метод Гаусса*/ /*прямой ход*/ for (i=0; iN; i++) { tmp=matrix[i][i]; for (j=N;j>=i;j--) matrix[i][j]/=tmp; for (j=i+1;jN;j++) { tmp=matrix[j][i]; for (k=N;k>=i;k--) matrix[j][k]-=tmp*matrix[i][k]; } } /*обратный ход*/ xx[N-1] = matrix[N-1][N]; for (i=N-2; i>=0; i--) { xx[i] = matrix[i][N]; for (j=i+1;jN;j++) xx[i]-=matrix[i][j]*xx[j]; } /*вывод решения*/ printf("\nMetod Gaussa:\n"); for (i=0; iN; i++) printf("x%d=%3.3f\n", i+1, xx[i]); return 0; }

Системы линейных уравнений методом Гаусса
Прошу помочь с составлением программы, позволяющей решать системы линейных уравнений методом Гаусса.

Решение системы линейных уравнений методом Гаусса
Всем привет! Ребята, пожалуйста помогите мне с решением системы линейных уравнений с помощью метода.

Решение системы линейных уравнений методом Гаусса
необходимо решить данную задачу в visual studio c++, если можно с комментариями, в консольном.

Решение системы линейных уравнений методом Гаусса
помогите найти ошибку, выводит результат, но не точный. Например в системе 10 9 19 9 8 17.

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

Добавлено через 58 минут
все, разобрался. Вот рабочий код:

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

#include #include #include using namespace std; int main() { int i, j, n, m; //создаем массив cout  "введи число уравнений: "; cin >> n; cout  "введи число неизвестных: "; cin >> m; m+=1; float **matrix = new float *[n]; for (i=0; in; i++) matrix[i] = new float [m]; //инициализируем for (i = 0; in; i++) for (j = 0; jm; j++) { cout  "Элемент "  "["  i+1  " , "  j+1  "]: " ; cin >> matrix[i][j]; } //выводим массив cout  "matrix: "  endl; for (i=0; in; i++) { for (j=0; jm; j++) cout  matrix[i][j]  " "; cout  endl; } cout  endl; //Метод Гаусса //Прямой ход, приведение к верхнетреугольному виду float tmp, xx[m]; int k; for (i=0; in; i++) { tmp=matrix[i][i]; for (j=n;j>=i;j--) matrix[i][j]/=tmp; for (j=i+1;jn;j++) { tmp=matrix[j][i]; for (k=n;k>=i;k--) matrix[j][k]-=tmp*matrix[i][k]; } } /*обратный ход*/ xx[n-1] = matrix[n-1][n]; for (i=n-2; i>=0; i--) { xx[i] = matrix[i][n]; for (j=i+1;jn;j++) xx[i]-=matrix[i][j]*xx[j]; } //Выводим решения for (i=0; in; i++) cout  xx[i]  " "; cout  endl; delete[] matrix; return 0; }

Сообщение от KPN

KPN, Возникла проблема с константным выражением и памятью. Подскажите, пожалуйста, как ее решить. Фото в комментарии выше

Сообщение от StasBerkutov

xx ты объявляешь как статический. Компилятор для статического массива выделяет место в памяти где хранится сам код поэтому он должен знать его размер до начала компиляции. Отсюда следует, что m должно быть константой:

const m = 100; // 100 -- размер массива float xx[m];

Место под динамический массив выделяется в куче(heap). То есть его можно создавать во время выполнения программы. В native C++(родной) объявляют его через указатель:

arrayfloat, 2>^ xx2 = gcnew arrayfloat, 2>(100, 100); //двухмерный arrayfloat>^ xx = gcnew arrayfloat>(100); //одномерный

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

#include #include using namespace std; class Matr { private: int size; double **mas; double *mas1; public: Matr() { size = 0; mas = NULL; mas1 = NULL; } Matr(int l) { size = l; mas = new double*[l]; for (int i = 0;i  l;i++) mas[i] = new double[l]; mas1 = new double[l]; } void Add() { for (int i = 0;i  size;i++) for (int j = 0;j  size;j++) mas[i][j] = rand() % 9; for (int i = 0;i  size;i++) mas1[i] = rand() % 10; } void Print() { for (int i = 0;i  size;i++) { for (int j = 0;j  size;j++) { printf("%4.f", mas[i][j]); } cout  <" "; printf("%4.f", mas1[i]); cout  ; /*cout  cout } } void Koff() { double temp; for (int k = 1; k  size; k++) { for (int j = k; j  size; j++) { temp = mas[j][k - 1] / mas[k - 1][k - 1]; for (int i = 0; i  size; i++) { mas[j][i] = mas[j][i] - temp * mas[k - 1][i]; } mas1[j] = mas1[j] - temp * mas1[k - 1]; } } } void Gaus() { double sum=0; double *x = new double[size]; for (int i = 0;i  size;i++) x[i] = 0; for (int i = size-1;i >= 0;i--) { x[i] = (mas1[i] - sum) / mas[i][i]; sum = 0; if (i > 0) { for (int j = size - 1;j >= i;j--) sum = sum + x[j] * mas[i - 1][j]; //2:24 a.m. 30.03.2016 } } for (int i = 0;i  size;i++) cout <"x"+1<"=" [i]<" "; } ~Matr() { for (int i = 0;i  size;i++) delete mas[i]; delete mas; } }; int main() { Matr a(10); a.Add(); a.Print(); a.Koff(); cout    ; a.Print(); cout    ; a.Gaus(); }

Источник