^«ТЕРМИНАЛ»"1!
Ш КОМПЬЮТЕРНЫЙ КЛУБ ШКОЛЬНИКОВ Щ
Елькин Сергей, (МАИ ''Искатель"),
г.Симферополь
Программный комплекс "POLYLISTER"
для обработки многочленов, представленных
в виде списков
В некоторых случаях для представления многочленов целесообразно ис-
пользовать динамически связанные с помощью указателей структуры данных.
Рассмотрим многочлены от одной переменной вида
anxn + anejxn~1 + ... + а0х°, (1)
в которых большинство коэффициентов равны нулю. Многочлены с большин-
ством нулевых коэффициентов называются разреженными.
Рассмотрим случаи, когда представление многочленов вида (1) с помощью
массивов неэффективно, так как требует дополнительной памяти для хране-
ния нулевых коэффициентов и дополнительного времени для упорядочивания
коэффициентов по степеням X.
Если задать многочлен х~9 + 2 в виде массива, то потребуется 10 элемен-
тов памяти для хранения коэффициентов, из них только два ненулевых.
Чтобы привести к канонической форме (с приведением подобных и упоря-
дочиванием) заданный в виде массива многочлен
хЗ + 2х~5 — хЗ,
или сложить многочлены хЗ — 2х~2 и хТ — хЗ + 5, потребуется как до-
полнительная память для хранения нулевых коэффициентов, так и дополни-
тельное время для сортировки.
Для многочленов больших степеней хранение многочленов в виде масси-
вов может оказаться вообще невозможным.
Альтернативным способом представления многочленов в памяти ЭВМ яв-
ляются динамические связанные структуры.
Для представления многочленов вида (1) будем использовать однонаправ-
ленный список. В сравнении с представлением многочленов в виде массивов
это дает экономию памяти, отводимой для нулевых коэффициентов; обеспе-
чивает быстрое выполнение операции приведения подобных членов при вы-
полнении арифметических действий (удаление одно члена с нулевым коэффи-
циентом) и простоту редактирования представления многочлена с сохранени-
ем упорядоченности его коэффициентов по степеням X.
Высокая эффективность указанных действий объясняется простотой опера-
ций поиска, вставки, удаления и слияния, выполняемых над списками. Эти пре-
имущества компенсируют недостатки, связанные с выделением дополнитель-
ной памяти для указателей.
Для эффективной обработки многочленов создан комплекс программ
"PolyLister", написанный на ПАСКАЛЕ, и выполняющий следующие функции:
A. Преобразование внешнего представления многочлена в списковое с
приведением подобных членов и упорядочиванием.
B. Выполнение арифметических операций над списковыми представления-
ми многочленов.
C. Визуализация преобразований над списками.
D. Преобразование спискового представления многочлена во внешнее.
Ниже приводится специальная демонстрационная программа "MONOMIAL
ADDING", которая иллюстрирует следующие возможности программного
комплекса "PolyLister":
1. Поиск элемента с ключом Expori, равным показателю степени одночле-
на.
2. Сложение коэффициентов подобных одночленов.
3. Включение нового элемента в список.
4. Удаление элемента списка, если при сложении коэффициентов резуль-
тат равен нулю.
5. Визуализацию используемого списка.
Используемые в программе процедуры описаны в таблице и импортиру-
ются из файла IMPORTA.LST.
В программе используются следующие глобальные переменные:
List — указатель на вход в список
Num — количество элементов списка (одночленов)
Coeff — коэффициент одночлена
Ехроп — степень одночлена
Таблица
# Имя Список параметров Описание действия
1. FUNCTION Search (Ехроп: Integer): Reference; Поиск элемента списка, предше-
ствующего элементу с ключом
Ехроп
2. PROCEDURE Insert (Ref: Reference; Вставка элемента списка,
Coeff, Ехроп: следующего за элементом
Integer); с указателем Ref
3. PROCEDURE Delete (Ref: Reference); Удаление элемента списка,
следующего за элементом
с указателем Ref
4. PROCEDURE Add_Mono (Ref: Reference; Сложение двух подобных
Coeff: Integer); одночленов от одной
переменной
•
Кроме процедур, выполняющих операции над списками, в демонстрацион-
ной программе используются процедуры:
Visit-Card - задание окон и вывод запроса;
Accept-Monomial - ввод одночлена;
Vis-Polynomial - вывод многочлена.
Пример работы демонстрационной программы проиллюстрирован на рис.
1-8.
В процессе обработки многочленов выполняется визуализация списков.
Текст демонстрационной программы на ПАСКАЛЕ
PROGRAM POLYLISTER (INPUN, OUTPUT);
Uses Crt;
TYPE
Reference + "Node;
Node + RECORD
Coeff, Expon : integer ;
Link : Reference ;
END;
{.................GLOBAL VARIABLES..................}
VAR Lisn : Reference ;
Num : Integer ;
Coeff,
Expon : Integer ;
{-.........................................................>
($1 importa.lst }
{.........MONOMIAL ADDING DEMO PROGRAM.....)
VAR
PrQ : Reference ;
BEGIN
Num : = О ;
List : = nil;
Visit_Card;
REPEAT
Accept_Monomial ;
P: = Search (Expon);
if P = Nil
Then
Q : = List
Else
Q : = P'.Link;
if (Q".Expon < > Expon) and (Coeff < > 0.0)
Then
Insert (P,Coeff,Expon)
Else
Add_Mono (P,Coeff);
VisPolinomial;
UNTIL FALSE
END.
Комментарий специалиста
Комплекс < <PolyLister> > — это пример использования теории инфор-
мационных структур для эффективного машинного представления и обработ-
ки математических объектов.
Важно, что при этом пользователю предоставляется возможность, приме-
няя визуализацию, изучить как математический, так и алгоритмический аспекты
решаемой задачи.
< <PolyLister > > построен так, что с его помощью можно не только ре-
шать простые задачи на аналитические преобразования многочленов (напри-
мер, приведение подобных), но и изучать в ходе решения задачи важнейшие
операции над списками : упорядочение вставками, удаление, поиск.
Иными словами, < <PolyLister > > относится к визуальным моделирую-
щим программам. Основное свойство программ этого класса состоит в том,
что решение задачи сочетается с графической демонстрацией динамики ис-
пользуемых структур данных и существа применяемого алгоритма.
Режим визуализации полезен как для пользователей-новичков, так и для
опытных разработчиков.
При создании большой программной системы визуализация необходима на
всех этапах ее жизненного цикла.
Прокомментируем рисунки 1-8, иллюстрирующие работу комплекса
< <PolyLister> >.
Рис. 1. Демонстрируется окно
ввода одночлена и окно выво-
да многочлена
Рис. 2. Демонстрируется слу-
чай приведения подобных с об-
разованием нулевого члена,
когда выполняется визуализа-
ция процесса удаления соот-
ветствующего элемента списка
Рис. 3. Показано состояние
списка до удаления элемента
Рис. 4. Выделен удаляемый
элемент списка
Рис. S. Показана команда, фор-
мирующая новое значение
ссылки
Рис. 6. Показано завершение
процесса удаления одночлена
с нулевым коэффициентом
Рис. 7. Показана команда
Dispose, восстанавливающая
память, занятую удаленным
элементом
Рис. 8. Показано заключитель-
ное состояние процесса удале-
ния элемента списка
И.А.Переход
