3. Формальная постановка задачи
Исходные данные
1) Полином P1(x), заданный в упорядоченном разреженном представлении, т. е. последовательность p1 (q1, q2, …, qn1), где qk = (ck, dk), причём ck и dk – целые, ck 0, dk 0.
2) Полином P2(x), заданный аналогичным образом, т. е. последовательность p2 (q1, q2, …, qn2).
3) Операция {+, – }.
Ограничения на исходные данные
В представлении каждого из полиномов ck и dk – целые стандартной точности, ck 0, dk 0 и ( k 1..max(n1, n2): abs(ck)*2 MaxIntType).
Результирующие (выходные) данные
Упорядоченное разреженное представление полинома P3(x) = P1(x) P2(x) для заданной операции , т. е. последовательность p3 (q1, q2, …, qm3), где 0 m3 m1 + m2.
Связь выходных данных с исходными данными
Опишем формально связь между выходной последовательностью p3 и двумя входными последовательностями p1, p2. Для этого используем следующие функции над последовательностями.
Пусть p = (q1, q2, …, qn) – непустая последовательность (n 0), тогда
First(p) = q1,
Rest(p) = (q2, q3, …, qn),
Prefix(q0, p) = (q0, q1, q2, …, qn).
Определим также функцию-индикатор пустой последовательности Null(p) if p=( ) then true else false. Кроме того, для упорядоченной пары чисел, представляющей моном q = (c, d), определим функции-селекторы coef(q) = c и deg(q) = d, а также функцию-конструктор упорядоченной пары pair(c, d) = (c, d).
Определим рекурсивную функцию сумма(p1, p2), результатом которой является упорядоченное разреженное представление суммы двух полиномов P1(x) + P2(x), а аргументами упорядоченные разреженные представления полиномов P1(x) и P2(x):
сумма(p1,p2)
if Null(p1) then p2
else if Null(p2) then p1
else {последовательности p1, p2 – обе не пусты }
[ Пусть d1=deg(First(p1)), d2=deg(First(p2)),
c1=coef(First(p1)), c2=coef(First(p2)),
тогда
if d1>d2 then Prefix(First(p1), сумма (Rest(p1),p2))
else if d1<d2 then Prefix(First(p2), сумма (p1, Rest(p2)))
else { d1=d2 }
if с1+с2=0
then сумма (Rest(p1),Rest(p2))
else Prefix( pair(c1+c2,d1), сумма (Rest(p1),Rest(p2)))
] {конец пусть-тогда}
Функция Разность(p1,p2) определяется как
Разность(p1,p2) сумма (p1, минус(p2)),
где в свою очередь функция минус(p) определена рекурсивно
минус(p) if Null(p) then p
else Prefix( pair(coef(First(p)),deg(First(p))), минус(Rest(p))).
4. Спецификация программы
Исходные данные (ИД)
Перечень и основные характеристики ИД:
num – номер наборов данных, натуральное; служит для формирования имен текстовых файлов входных данных inp1_XX.dat , inp2_XX.dat, выходных данных out_XX.dat и промежуточных данных prtcl_XX.dat. Здесь ХХ – это десятичная запись числа num, в случае необходимости дополненная нулем слева;
op – вариант операции над полиномами; op {+, –, минус};
последовательность, задающая первый полином p1 (q1, q2, …, qn1),
где qk = (ck, dk), причем ck и dk – целые стандартной точности, ck 0, dk 0;
если op минус, то последовательность, задающая аналогичным образом второй полином p2 (q1, q2, … , qn2).
Ограничения на исходные данные:
для num задан диапазон 1 num 99, ограничение сверху обусловлено требованием, что десятичная запись числа num должна содержать не более двух символов;
для коэффициентов мономов ck целые стандартной точности реализуются типом integer;
для показателей степеней мономов dk целые стандартной точности реализуются типом word.
Место и форма представления исходных данных:
num вводится с клавиатуры в процессе диалога, порядок ввода и форма представления описаны в сценарии диалога;
данные, задающие первый полином, вводятся из файла inp1_XX.dat; расположение данных в файле приведено н
c1 d1
…
ck dk
…
cn1 dn1
Расположение данных в файле inp1_XX.dat
данные, задающие второй полином, вводятся из файла inp2_XX.dat; расположение данных в файле аналогично приведенному на рисунке.
Функции программы по обработке исключительных ситуаций
Исполняющая система прекращает выполнение программы, выдавая диагностическое сообщение об ошибке в следующих случаях:
1) если значение num не принадлежит диапазону 1…99;
2) если невозможно открыть для чтения файлы inp1_XX.dat или inp2_XX.dat;
3) если невозможно открыть для записи файлы out_XX.dat или prtcl_XX.dat;
4) если значения коэффициентов мономов ck выходят за границы, определенные для типа integer;
5) если значения показателей степеней мономов dk выходят за границы, определенные для типа word.
Если пары (ck , dk) не упорядочены по убыванию dk, то программа выполняет действия по сортировке, выдает диагностическое сообщение о ходе процесса выполнения «Сортировка входных данных…» и продолжает работу.
Выходные данные
Состав выходных данных:
op – вариант операции над полиномами; op {+, –, минус};
последовательность, задающая первый полином p1 (q1, q2, …, qn1);
если op минус, то последовательность, задающая второй полином p2 (q1, q2, …, qn2);
последовательность p3 (q1, q2, …, qn3), представляющая результат операции op над полиномами p1 и p2.
Место и форма представления выходных данных. Выходные данные выводятся на экран и в файлы out_XX.dat и prtcl_XX.dat, где ХХ – это десятичная запись задаваемого пользователем числа num, в случае необходимости дополненная нулем слева.
1) Если op = +, то на экран выводится сообщение: «Определение суммы двух полиномов»;
2) если op = –, то на экран выводится сообщение: «Определение разности двух полиномов»;
3) если op = минус, то на экран выводится сообщение: «Выполнение операции изменения знака полинома»;
4) каждый полином P(x;n) выводится на экран и в файлы в следующей форме (макет вывода полинома на примере первого полинома, вводимого из файла inp1_XX.dat):
Макет вывода полинома
P(x ;dd ) |
= |
Sddddd * x ^ dd |
+ |
dn1 |
|
cn1 dn1 |
|
|
|
… |
|
|
|
Sddddd * x ^ dd |
+ |
|
|
ck dk |
|
|
|
… |
|
|
|
Sddddd * x ^ dd |
|
|
|
c1 d1 |
|
Здесь S – позиция для знака отрицательного числа, d – десятичная позиция для коэффициентов ck и показателей степеней dk мономов.
Сценарий диалога
Общая схема диалога:
1. Вывод заголовка на экран и в файл prtcl_XX.dat:
ПРОГРАММА
для изменения знака полинома или определения суммы или разности двух полиномов
(Исходные данные вводятся из текстовых файлов, результаты выводятся в текстовые файлы)
2. Сцена 1 (выбор варианта исходных данных, выбор варианта операции над полиномами).
3. Сцена 2 (ввод, анализ упорядоченности и вывод параметров первого полинома).
4. Если выбрана операция определения суммы или разности полиномов, то Сцена 3 (ввод, анализ упорядоченности и вывод параметров второго полинома).
5. Сцена 4 (вывод параметров результирующего полинома).
Описание сцен диалога. Описание сцены 1 приведено в табл. П.1.
Таблица П.1
Алгоритм ведения диалога |
Сообщения пользователю и его реакция |
Вывод запроса |
Выберите вариант исходных данных (1…99). |
Ввод num |
??<Enter> |
Вывод запроса
|
Выберите вариант операции над полиномами: 1 – определение суммы; 2 – определение разности; 3 – изменение знака полинома. |
Ввод варианта операции над полиномами |
?<Enter> |
ЕСЛИ вариант 1 ТО вывод сообщения 2 |
Текст сообщения: Определение суммы двух полиномов |
ЕСЛИ вариант 2 ТО вывод сообщения 3 |
Текст сообщения: Определение разности двух полиномов |
ЕСЛИ вариант 3 ТО вывод сообщения 4 |
Текст сообщения: Выполнение операции изменения знака полинома |
Описание сцены 2 приведено в табл. П.2.
Таблица П.2
Алгоритм ведения диалога |
Сообщения пользователю и его реакция |
Ввод параметров первого полинома из файла inp1_XX.dat |
[Формат файла – см. рисунок] |
ЕСЛИ введенные параметры не упорядочены по убыванию степеней мономов ТО выдача сообщения 5 |
Текст сообщения: Сортировка входных данных… |
Вывод параметров первого полинома после упорядочения |
[Вывод полинома по макету вывода полинома на экран и в файлы] |
Описание сцены 3 аналогично описанию сцены 2 для второго полинома. Описание сцены 4 приведено в табл. П.3.
Таблица П.3
Алгоритм ведения диалога |
Сообщения пользователю и его реакция |
Вывод заголовка (копия в файл prtcl_XX.dat) |
РЕЗУЛЬТАТ |
Вывод полинома (копия в файлы out_XX.dat и prtcl_XX.dat) |
[Вывод полинома по макету вывода полинома] |
Отметим, что в прямоугольные рамки заключены поля данных, вводимых пользователем.