Решение системы регулярных уравнений
Рассмотрение понятия регулярных выражений и множеств; их сокращенное обозначение. Представление алгоритма программы, предназначенной для решения системы линейных уравнений методом исключения Гаусса. Ознакомление с содержимым файлов input.txt и output.txt.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 08.02.2013 |
| Размер файла | 251,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Задание
Решение системы регулярных уравнений.
Во входном файле (с именем INPUT.TXT) задается размерность системы регулярных уравнений n (1 ? n ? 8) а затем - ее коэффициенты:
б10 б11 б12 … б1n
б20 б21 б22 … б2n
…………………
бn0 бn1 бn2 … бnn
Максимальная длина регулярного выражения для каждого коэффициента равна 3.
1. Короткая теория
Определение. Регулярные выражения в алфавите У и регулярные множества, которые они обозначают, определяются рекурсивно следующим образом:
1) - регулярное выражение, обозначающее регулярное множество ;
2) e - регулярное выражение, обозначающее регулярное множество {e};
3) если aУ, то a - регулярное выражение, обозначающее регулярное множество {a};
4) если p и q - регулярные выражения, обозначающие регулярные множества P и Q, то
а) (p+q) - регулярное выражение, обозначающее PQ;
б) pq - регулярное выражение, обозначающее PQ;
в) p* - регулярное выражение, обозначающее P*;
5) ничто другое не является регулярным выражением.
Принято обозначать p+ для сокращенного обозначения рр*. Расстановка приоритетов:
- * (итерация) - наивысший приоритет;
- конкатенация;
- + (объединение).
Например, 0 + 10* = (0 + (1 (0*))).
Таким образом, для каждого регулярного множества можно найти регулярное выражение, его обозначающее, и наоборот.
Введем леммы, обозначающие основные алгебраические свойства регулярных выражений. Пусть б, в и г регулярные выражения, тогда:
1) б + в = в + б
2) * = e
3) б + (в + г) = (б + в) + г
4) б(вг) = (бв)г
5) б (в + г) = бв + бг
6) (б + в)г = бг + вг
7) бe = eб = б
8) б = б =
9) б* = б+б*
10) (б*)* = б*
11) б+б = б
12) б+ = б
При работе с языками часто удобно пользоваться уравнениями, коэффициентами и неизвестными которых служат множества. Такие уравнения будем называть уравнениями с регулярными коэффициентами
X = aX + b,
где a и b - регулярные выражения. Можно проверить прямой подстановкой, что решением этого уравнения будет a*b:
aa*b + b = (aa* + e) b = a*b,
т.е. получаем одно и то же множество. Таким же образом можно установить и решение системы уравнений.
Определение. Систему уравнений с регулярными коэффициентами назовем стандартной системой с множеством неизвестных Д = {X1, X2, …, Xn}, если она имеет вид:
X1 = б10 + б11X1 + б12X2 + … + б1nXn
X2 = б20 + б21X1 + б22X2 + … + б2nXn
………………………………………
Xn = бn0 + бn1X1 + бn2X2 + … + бnnXn
где бij - регулярные выражения в алфавите, не пересекающемся с Д. Коэффициентами уравнения являются выражения бij.
Если бij = , то в уравнении для Xi нет числа, содержащего Xj. Аналогично, если бij = e, то в уравнении для Xi член, содержащий Xj, - это просто Xj. Иными словами, играет роль коэффициента 0, а e - роль коэффициента 1 в обычных системах линейных уравнений.
Алгоритм решения.
Вход. Стандартная система Q уравнений с регулярными коэффициентами в алфавите У и множеством неизвестных Д = = {X1, X2, …, Xn}.
Выход. Решение системы Q.
Метод: Аналог метода решения системы линейных уравнений методом исключения Гаусса.
Шаг 1. Положить i = 1.
Шаг 2. Если i = n, перейти к шагу 4. В противном случае с помощью тождеств леммы записать уравнения для Xi в виде
Xi = бXi + в,
где б - регулярное выражение в алфавите У, а в - регулярное выражение вида
в0 + вi+1Xi+1 + … + вnXn,
причем все вi - регулярные выражения в алфавите У. Затем в правых частях для уравнений Xi+1, …, Xn заменим Xi регулярным выражением б*в.
Шаг 3. Увеличить i на 1 и вернуться к шагу 2.
Шаг 4. Записать уравнение для Xn в виде Xn = бXn + в, где б и в - регулярные выражения в алфавите У. Перейти к шагу 5 (при этом i = n).
Шаг 5. Уравнение для Xi имеет вид Xi = бXi + в, где б и в - регулярные выражения в алфавите У. Записать на выходе Xi = = б*в, в уравнениях для Xi-1, …, X1 подставляя б*в вместо Xi.
Шаг 6. Если i = 1, остановиться, в противном случае уменьшить i на 1 и вернуться к шагу 5.
2. Результаты работы программы
Пример 1.
Содержимое input.txt:
Содержимое output.txt
Пример 2.
Содержимое input.txt:
регулярный выражение множество программа
Содержимое output.txt
Выводы
программа уравнение регулярный решение
В данной работе создана программа для решения системы регулярных уравнений. На вход программы из файла INPUT.TXT подается размерность системы регулярных уравнений и ее коэффициенты. Программа анализирует имеющуюся в текстовом файле систему и выдает в текстовый файл OUTPUT.TXT ее решение.
Список литературы
1. Епанешников А.М., Епанешников В.А. Программирование в среде Turbo Pascal 7.0. - М.: ДИАЛОГ-МИФИ, 1996
2. Фаронов В.В. Turbo Pascal 7.0. Начальный курс. - Нолидж, 1998. - 620 с.
3. Грызлов В.И., Грызлова Т.П. Турбо Паскаль 7.0. - М.: «ДМК», 2000. - 416 с.
4. Калайда В.Т. Теория вычислительных процессов и структур: Учеб. пособие. - Томск: ТМЦДО, 2007. - 269 с.
Приложение
Листинг программы
program lab3;
uses Crt;
type
IPtr = ^IStruct;
IStruct = record
kind: Char;
sim: Char;
Lf: IPtr;
Rg: IPtr;
end;
type
IVStruct = array [0..8] of IPtr;
type
StrArray = array [1..10] of string[20];
const
rQ = '*';
mQ = 'x';
cQ = '+';
var
N: Integer;
M1, M2: array [1..8] of IVStruct;
S, expr: string;
P, T: PChar;
sObj: IPtr;
i, j, k: Integer;
x, f, R: IVStruct;
function ICreate (kind: Char; sim: Char; Lf, Rg: IPtr): IPtr;
var
result_: IPtr;
begin
New (result_);
result_^.Lf:= Lf; result_^.Rg:= Rg; result_^.kind:= kind; result_^.sim:= sim;
ICreate:= result_;
end;
function sCreate (sim: Char): IPtr;
begin
sCreate:= ICreate (#0, sim, nil, nil);
end;
function operCreate (kind: Char; Lf, Rg: IPtr): IPtr;
begin
if (kind in [mQ, cQ]) and ((lf = nil) or (rg = nil)) then
begin
kind:= kind;
end;
operCreate:= ICreate (kind, #0, Lf, Rg);
end;
function isE (sObj: IPtr): Boolean;
begin
isE:= (sObj <> nil) and (sObj^.kind = #0) and (sObj^.sim in ['e', 'E']);
end;
function is0 (sObj: IPtr): Boolean;
begin
is0:= (sObj <> nil) and (sObj^.kind = #0) and (sObj^.sim = '0');
end;
function IVOf (const Expr: string): IPtr;
var
result_: IPtr;
begin
if Length(Expr) = 1 then
begin
result_:= sCreate (Expr[1]);
end else
if Length(Expr) = 2 then
begin
if Expr[2] = '*' then
result_:= ICreate (rQ, #0, sCreate (Expr[1]), nil)
else
result_:= ICreate (mQ, #0, sCreate (Expr[1]), sCreate (Expr[2]));
end else
if Length(Expr) = 3 then
begin
if Expr[2] = '+' then
result_:= ICreate (cQ, #0, sCreate (Expr[1]), sCreate (Expr[3]))
else if Expr[2] = '*' then
result_:= ICreate (mQ, #0, ICreate (rQ, #0, sCreate (Expr[1]), nil), sCreate (Expr[3]))
else if Expr[3] = '*' then
result_:= ICreate (mQ, #0, sCreate (Expr[1]), ICreate (rQ, #0, sCreate (Expr[2]), nil))
else if (Expr[1] = '(') and (Expr[3] = ')') then
result_:= sCreate (Expr[2])
else
result_:= ICreate (mQ, #0,
ICreate (mQ, #0,
sCreate (Expr[1]), sCreate (Expr[2])), sCreate (Expr[3]));
end else
begin
result_:= nil;
end;
IVOf:= result_;
end;
function sFormat (sObj: IPtr): string;
var
S1, S2: string;
result_:string;
begin
case sObj^.kind of
#0: result_:= sObj^.sim;
mQ:
begin
if Assigned (sObj^.Lf) and (sObj^.Lf^.kind = cQ) then {(a+)}
result_:= ' (' + sFormat (sObj^.Lf) + ')' + sFormat (sObj^.Rg)
else
if Assigned (sObj^.Rg) and (sObj^.Rg^.kind = cQ) then
result_:= sFormat (sObj^.Lf) + ' (' + sFormat (sObj^.Rg) + ')'
else
result_:= sFormat (sObj^.Lf) + sFormat (sObj^.Rg);
end;
cQ:
begin
S1:= sFormat (sObj^.Lf);
S2:= sFormat (sObj^.Rg);
result_:= S1 + '+' + S2;
end;
rQ:
begin
if Assigned (sObj^.Lf) and (sObj^.Lf^.kind = #0) then
result_:= sFormat (sObj^.Lf) + '*'
else
result_:= ' (' + sFormat (sObj^.Lf) + ')' + '*'
end;
else
result_:= «;
end;
sFormat:= result_;
end;
function IsSame (IV1, IV2: IPtr): Boolean;
var
result_: Boolean;
begin
if (IV1 = nil) and (IV2 = nil) then
result_:= True
else if Assigned(IV1) and Assigned(IV2) then
result_:= (IV1^.kind = IV2^.kind) and (IV1^.sim = IV2^.sim)
and IsSame (IV1^.Lf, IV2^.Lf) and IsSame (IV1^.Rg, IV2^.Rg)
else
result_:= False;
IsSame:= result_;
end;
function isAArep (sObj: IPtr; var Arep: IPtr): Boolean;
begin
if sObj = nil then
isAARep:= False
else
if sObj^.kind = mQ then
begin
if (sObj^.Rg^.kind = rQ) and IsSame (sObj^.Lf, sObj^.Rg^.Lf) then
begin
isAArep:= True;
Arep:= sObj^.Rg;
end
else
if (sObj^.rg <>nil) and (sObj^.lf<>nil) and
(sObj^.rg^.Lf <>nil) and (sObj^.rg^.Lf^.kind = rQ) and
IsSame (sObj^.rg^.Rg, sObj^.rg^.Lf^.Lf) then
begin
isAArep:= True;
Arep:= sObj^.rg;
end
else
if (sObj^.Lf^.kind = rQ) and IsSame (sObj^.Rg, sObj^.Lf^.Lf) then
begin
isAArep:= True;
Arep:= sObj^.lf;
end
else
isAArep:= False;
end
else
isAArep:= False;
end;
function isarep (a, sObj:IPtr):Boolean;
begin
if IsSame (a, sObj) then
begin
isarep:=True;
Exit;
end;
if sObj^.kind = mq then
begin
isarep:= isarep (a, sObj^.Lf) and isarep (a, sObj^.Rg);
Exit;
end;
isarep:= False;
end;
function Simple (sObj: IPtr): IPtr;
var
result_, T: IPtr;
s1, s2:string;
begin
result_:= sObj;
if sObj = nil then
begin
Simple:=result_;
Exit;
end;
if (sObj^.kind in [mQ, cQ]) and ((sObj^.Lf = nil) or (sObj^.Rg = nil)) then
begin
sObj:= sObj;
result_:= result_;
end;
sObj^.Lf:= Simple (sObj^.Lf);
sObj^.Rg:= Simple (sObj^.Rg);
s1:= sFormat(sObj);
s2:= sFormat (result_);
if (sObj^.kind in [mQ, cQ]) and ((sObj^.Lf = nil) or (sObj^.Rg = nil)) then
begin
sObj:= sObj;
result_:= result_;
end;
case sObj^.kind of
mQ: {x}
begin
if isE (sObj^.Lf) then result_:= sObj^.Rg {ae=a}
else if isE (sObj^.Rg) then result_:= sObj^.Lf {ea=a}
else if is0 (sObj^.Lf) or is0 (sObj^.Rg) then result_:= sCreate('0') {a0=0a=0}
else if (sObj^.Lf^.kind = rQ) and (sObj^.Rg^.kind = rQ) and {A* A* = A*}
IsSame (sObj^.Lf, sObj^.Rg) then result_:= sObj^.Lf
else if (sObj^.Rg^.kind=rQ) and IsSame (sObj^.Lf, sObj^.Rg^.Lf) then {aa*=a*a}
begin
t:=sObj^.Rg;
sObj^.Rg:=sObj^.Lf;
sObj^.Lf:=t;
result_:= sObj;
end
else if (sObj^.Rg^.kind=cQ) then {a (b+c) = ab+ac}
begin
result_:= operCreate (cQ,
operCreate (mq, sObj^.Lf, sObj^.Rg^.Lf),
operCreate (mq, sObj^.Lf, sObj^.Rg^.rg)
);
end
else if (sObj^.Lf^.kind=cQ) then {(a+b) c = ac+bc}
begin
result_:= operCreate (cQ,
operCreate (mq, sObj^.Lf^.Lf, sObj^.Rg),
operCreate (mq, sObj^.Lf^.rg, sObj^.Rg)
);
end
else if (sObj^.Lf^.kind = rQ) and (sObj^.Rg^.kind = mQ) and {!!!! A* (A*B) = (A*A) B= A*B}
(sObj^.Rg^.lf^.kind = rQ) and IsSame (sObj^.Lf^.lf, sObj^.Rg^.lf^.lf) then
begin
result_:= sObj^.rg;
end;
end;
cQ: {+}
begin
if is0 (sObj^.Lf) then result_:= sObj^.Rg {0+a=a}
else if is0 (sObj^.Rg) then result_:= sObj^.Lf {a+0=a}
else if IsSame (sObj^.Lf, sObj^.Rg) then result_:= sObj^.Lf {a+a = a}
else if (sObj^.Rg^.kind = rQ) and IsSame (sObj^.Lf, sObj^.Rg^.Lf) then
result_:= sObj^.Rg {A + A* = A*}
else if (sObj^.Lf^.kind = rQ) and IsSame (sObj^.Rg, sObj^.Lf^.Lf) then
result_:= sObj^.Lf {A* + A = A*}
else if (sObj^.Lf^.kind = rQ) and isE (sObj^.Rg) then result_:= sObj^.Lf {A* + 1 = A*}
else if (sObj^.Rg^.kind = rQ) and isE (sObj^.Lf) then result_:= sObj^.Rg {1 + A* = A*}
Размещено на Allbest.ru
...Подобные документы
Постановка задачи, математические и алгоритмические основы решения системы линейных алгебраических уравнений. Решение системы данных уравнений методом Гаусса с выбором главного элемента по столбцу. Функциональные модели и блок-схемы решения задачи.
курсовая работа [428,9 K], добавлен 25.01.2010Сущность и особенности языка программирования Си. Основные этапы алгоритма решения системы линейных алгебраических уравнений методом Гаусса, реализация программы для их расчета. Инструкции пользователя и программиста. Тестирование функции решения.
курсовая работа [153,9 K], добавлен 18.02.2013Системы линейных алгебраических уравнений. Матричный метод решения систем линейных уравнений. Решение задачи математическим методом. Блок-схема алгоритма и листинг программы. Расчет трудоемкости разработки программы. Расчет себестоимости и цены программы.
дипломная работа [144,8 K], добавлен 25.04.2012Сущность матричного метода. Разработка программы решения системы уравнений линейных алгебраических уравнений методом решения через обратную матрицу на языке программирования Delphi. Представление блок-схемы и графического интерфейса программного продукта.
курсовая работа [1,0 M], добавлен 27.09.2014Системы линейных алгебраических уравнений. Код программы для решения систем линейных алгебраических уравнений. Математические и алгоритмические основы решения задачи методом Гаусса. Программная реализация решения. Алгоритмы запоминания коэффициентов.
лабораторная работа [23,5 K], добавлен 23.09.2014Решение систем алгебраических линейных уравнений методом Крамера. Сущность метода прогонки. Программная реализация метода: блок-схема алгоритма, листинг программы. Проверка применимости данного способа решения для конкретной системы линейных уравнений.
курсовая работа [581,0 K], добавлен 15.06.2013Преобразование матрицы системы линейных алгебраических уравнений (СЛАУ) с помощью алгоритма Гаусса. Решение задачи методом простой итерации. Создание блок-схемы и текста программы для решения СЛАУ, реализованной на языке программирования Turbo Pascal.
курсовая работа [1,2 M], добавлен 15.06.2013Матричная форма записи системы линейных уравнений, последовательность ее решения методом исключений Гаусса. Алгоритмы прямого хода и запоминания коэффициентов. Решение задачи о сглаживании экспериментальных данных с помощью метода наименьших квадратов.
курсовая работа [610,7 K], добавлен 25.06.2012Применение итерационных методов численного решения системы линейных алгебраических уравнений при вычислении на ЭВМ. Математические и алгоритмические основы решения задачи, метод Гаусса. Функциональные модели и блок-схемы, программная реализация решения.
курсовая работа [527,5 K], добавлен 25.01.2010Метод Гаусса как прямой метод нахождения решений для систем системы линейных уравнений маленькой и средней размерности с помощью компьютерной техники. Редактор кода и исходный код основной программы в Delphi, блок-схема и графическое решение задачи.
контрольная работа [460,8 K], добавлен 15.06.2015Приведение системы линейных алгебраических уравнений к треугольному виду прямым ходом метода Гаусса. Применение обратного хода метода вращений. Создание алгоритма, блок-схемы и кода программы. Тестовый пример решения уравнения и его проверка в MathCad.
лабораторная работа [164,3 K], добавлен 02.10.2013Сущность метода Гаусса при решении систем линейных уравнений. Элементарные преобразования этого метода. Краткое описание среды визуальной разработки Delphi. Описание основных применяемых процедур и алгоритм роботы программы по решению уравнений.
курсовая работа [1,1 M], добавлен 29.08.2010Системы линейных алгебраических уравнений. Решение систем уравнений графическим способом. Разработка программного кода модуля, реализующего приближенное решение систем линейных уравнений графическим способом. Отладка программного модуля "Метод Гаусса".
курсовая работа [858,5 K], добавлен 01.12.2013Сферы использования компьютеров, сущность и языки программирования. Применение модифицированного метода Гаусса и расширенной матрицы для решения системы линейных алгебраических уравнений (СЛАУ). Разработка программы, системные требования для ее работы.
курсовая работа [657,1 K], добавлен 09.01.2014Проектирование приложения, позволяющего находить решение системы алгебраических линейных уравнений матричным методом. Выбор количества уравнений, заполнение значений коэффициентов системы уравнений и свободных членов, алгоритм решения линейных уравнений.
курсовая работа [939,4 K], добавлен 16.01.2014Решение системы линейных алгебраических уравнений методом Гаусса с выборкой ведущего элемента. Изучение особенности программной реализации алгоритма, составленной средствами разработки Microsoft Visual Studio. Проведение сложения и умножения двух матриц.
курсовая работа [702,6 K], добавлен 22.03.2015Решение системы линейных уравнений с матричными элементами и свободными членами с использованием метода Гаусса с выбором главного элемента, основанного на приведении матрицы системы к треугольному виду с помощью нахождения элементов главной диагонали.
лабораторная работа [71,1 K], добавлен 10.12.2014Понятия систем линейных уравнений и матриц. Решение общей системы линейных уравнений по методу Гаусса. Системные требования, методы установки, удаления и работы с программой. Методы защиты от неверного ввода данных. Тестирование и опытная эксплуатация.
курсовая работа [751,0 K], добавлен 25.02.2011Алгоритм решения систем линейных уравнений методом Гаусса, его этапы. Система уравнений для определения коэффициентов сплайна, представляющая собой частный случай систем линейных алгебраических уравнений. Программная реализация, тестовый пример.
курсовая работа [431,8 K], добавлен 15.06.2013Метод Гаусса-Зейделя как модификация метода Якоби, его сущность и применение. Разработка программы решения системы линейных алгебраических уравнений на языке VB, проверка правильности работы программы в MS Excel и математических пакетах MathCad и MatLab.
курсовая работа [325,5 K], добавлен 27.10.2013
