Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Вопросы начинающих программистов
Перезагрузить страницу Решение системы регулярных уравнений
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
ABBA@12 ABBA@12 вне форума
Member
 
Сообщений: 33
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.03.2009
Thumbs down 28.04.2010, 00:54

Здравствуйте, помогите пожалуйста решить контрольную!!!! Заранее спасибо... Этот сайт-моя последняя надежда!

Решение системы регулярных уравнений
1 ВХОДНЫЕ ДАННЫЕ
Во входном файле (с именем 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) — регулярное выражение, обозначающее PQ;
б) pq — регулярное выражение, обозначающее PQ;
в) 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.

ВЫХОДНЫЕ ДАННЫЕ
В выходной файл (с именем OUTPUT.TXT) необходимо вывести:
1) Полное решение системы регулярных уравнений.
2) Упрощенное решение.
Упрощенное решение получается, если применить к полу-ченному решению леммы 1—12.
Ответить с цитированием
  (#2 (permalink)) Старый
Зирк Зирк вне форума
Member
 
Сообщений: 1,337
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 14.04.2005
По умолчанию 28.04.2010, 00:57

я бы понял, если бы алгоритм был непонятен, не всем дано понимать математику(я например нуль в ней), но вот вся теория, с алгоритмом, бери да кодируй.
Ответить с цитированием
  (#3 (permalink)) Старый
ABBA@12 ABBA@12 вне форума
Member
 
Сообщений: 33
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.03.2009
По умолчанию 28.04.2010, 01:55

Цитата:
я бы понял, если бы алгоритм был непонятен, не всем дано понимать математику(я например нуль в ней), но вот вся теория, с алгоритмом, бери да кодируй.
Все дело во времени. Сейчас изучаю книгу "Компиляторы. Принципы, технологии, инструменты." А. Ахо, Р. Сети, Д. Ульман. Заданее и принцип стал более понятен, но вот проблемы с самим написание кода, так как в языках плаваю "топориком".
Ответить с цитированием
  (#4 (permalink)) Старый
Зирк Зирк вне форума
Member
 
Сообщений: 1,337
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 14.04.2005
По умолчанию 28.04.2010, 11:26

А зачем ты такие книги читаешь? Как поможет решить проблему чтение этой книги? Никак.
Читай самоучители по С или Паскалю. Лучше по С.
Ответить с цитированием
  (#5 (permalink)) Старый
ABBA@12 ABBA@12 вне форума
Member
 
Сообщений: 33
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.03.2009
По умолчанию 28.04.2010, 23:37

Цитата:
А зачем ты такие книги читаешь? Как поможет решить проблему чтение этой книги? Никак.
Читай самоучители по С или Паскалю. Лучше по С.
Читаю, потому что порекомендовали люди, и в методичке - это использованная литература. Самоучитель тоже под рукой, но там один примитив - опыта маловато использовать в такой задаче.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Jonano Jonano вне форума
Специалист
 
Аватар для Jonano
 
Сообщений: 3,541
Сказал(а) спасибо: 2
Поблагодарили 14 раз(а) в 14 сообщениях
Регистрация: 19.04.2005
По умолчанию 07.05.2010, 00:56

Цитата:
Читаю, потому что порекомендовали люди, и в методичке - это использованная литература. Самоучитель тоже под рукой, но там один примитив - опыта маловато использовать в такой задаче.
Все с примитива начинали. И только с него.
Ответить с цитированием
  (#7 (permalink)) Старый
Marooned Marooned вне форума
Новичок
 
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.09.2011
По умолчанию 05.09.2011, 18:09

Доброго здоровья всем !
Пришлось столкнуться с этой же самой задачей. Прошу откликнуться автора темы, или того, кто реально может помочь. Вникать в эту мудрёную теорию регулярных уравнений уже нет ни времени, ни сил.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Решение системы дифференциальных уравнений в среде VisualBasic goog Вопросы начинающих программистов 0 14.12.2010 22:24
Решение эллиптических уравнений методом переменных направлений puzi blin4ik Вопросы начинающих программистов 1 03.12.2010 12:27
Решение дифф.уравнений явным и неявным методами Эйлера ogionw С/С++ 7 17.05.2010 14:04
Численное решение нелинейных уравнений user'199 Visual C++ 0 22.01.2009 20:10
Решение системы линейных уравнений произвольной размерности z556 Prolog 4 20.04.2007 01:12
Решение нелинейных уравнений ~l)eni$~ Вопросы начинающих программистов 15 19.05.2006 01:06
Решение систем линейных уравнений методом простой итеррации MiHanick Pascal 4 04.05.2005 20:14
Решение системы алгебраических уравнений методом Монте-Карло Bill O'skurskiy Алгоритмы 2 06.07.2004 15:22
Как решить системы уравнений в Prolog Anonymous Prolog 34 29.12.2003 00:10
Метод Лагранжа для системы уравнений Anonymous Prolog 4 26.12.2003 23:09



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов