Министерство образования и науки Российской Федерации

Государственное образовательное учреждение высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского»

Факультет вычислительной математики и кибернетики

ОТЧЕТ

по лабораторной работе № 4

«Аналитические преобразования полиномов

от нескольких переменных»

Выполнил: студент группы 8210

__________________Баранов А.М. Проверил:

__________________Сидоров С.В.

Нижний Новгород

2011 г.

Оглавление

Аннотация 3

Введение 3

Постановка задачи 3

Руководство пользователя 4

Руководство программиста 6

Описание структуры хранения данных 6

Описание программы 7

Описание алгоритма 7

Заключение 10

Литература 11

Приложение (исходный код программы) 12

Аннотация

В данной работе рассматриваются вопросы реализации некоторых базовых аналитических преобразований и операций над полиномами от нескольких переменных.

Для хранения полиномов используются однонаправленные динамические списки.

Введение

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

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

Постановка задачи

Лабораторная работа предполагает программную реализацию системы аналитических преобразований полиномов от трех переменных. Требуется реализовать следующие операции в аналитическом представлении исходных данных и результатов:

• ввод полиномов;

• вывод полиномов;

• удаление полиномов;

• приведение полиномов

• сложение полиномов;

• Вычитание полиномов;

• Производная от полинома;

• Умножение полиномов

Например, пусть имеется два полинома: P(x,y,z)=x⁷y²z+3x²z-6y²-3z⁹ и Q(x,y,z)=-7x²z+6y²+5. В результате выполнения операции сложения должен быть получен полином R(x,y,z)=x⁷y²z-4x²z-3z⁹+5.

Программа должна обеспечивать диалоговый интерфейс с пользователем обеспечивающий ввод исходных данных из заранее подготовленного файла с заданным именем.

Руководство пользователя

После запуска исполняемого файла программы вы увидите главное окно программы (рис. 1).

Рис. 1. Главное окно программы.

Основные операции.

Операция сложения/вычитания/умножения полиномов:

• Выбирается пункт меню 1/2/4;

• Вводится имя файла с первым полиномом;

• Выводится исходный неприведенный полином;

• Выводится приведенный полином;

• Вводится имя файла со вторым полиномом;

• Выводится исходный неприведенный полином;

• Выводится приведенный полином;

• Выводится результат в приведенном виде.

Рис. 2. Выполнение операции сложения.

Рис.3. Результат операции вычитания.

Рис.4. Результат операции умножения.

Операция вычисления производной:

• Выбирается пункт меню 3;

• Вводится имя файла с полиномом;

• Выводится исходный неприведенный полином;

• Выводится приведенный полином;

• Выводится результат в приведенном виде.

Рис.5.Результат вычисления производной.

Руководство программиста Описание структуры хранения данных

При манипуляции разреженными полиномами эффективной структурой хранения являются списки.

В качестве структуры хранения данных полинома был выбран однонаправленный динамический список. Каждый узел содержит два элемента содержащие атрибуты монома

elem - коэфффициент монома

pol – свертка монома

под сверткой монома имеется в виду вычисляемое целое число без знака вычисляемое в соответствии со следующими правилами

• фиксируется старшинство переменных.

• Будем считать, что x - самая старшая переменная, затем следует y, затем z.

• Для каждого монома определим его "свернутую степень" (индекс).

• Для монома xAyBzC+n. индекс равен A*1000+B*100+C*10+n (по условию задачи A, B и C не выше 9).

• Старшим считается моном с большей свернутой степенью.

Свертка монома служит в дальнейшем ключом для идентификации монома

Кроме этого в каждый узел входит ссылка на следующий элемент списка

Для хранения промежуточного результата синтаксического разбора исходной строки используется массив Mpars

unsigned int Mpars[500];

node *Bfirst, *Blast ;

node *BRes; //Указатель на найденное звено списка.

node *Afirst, *Alast ;

node *ARes; //Указатель на найденное звено списка.

struct node {

int elem;

unsigned int pol;

node *next;

};

Для хранения полинома класс Spisok

class Spisok

{

private:

int N_monom;

public:

Spisok() {phead = new (node); (*phead).next=NULL;} //Конструктор.

~Spisok() { delete phead; } //Деструктор.

void Initial(node **first, node **last);

int Empty(node *first);

void Add(node **last,int elem, unsigned int pol);

void Show(node *first);

int Poisk_Eqv (node *first,unsigned int pol,node **last);

int Poisk_Less (node *first,int el,node **last);

void Izm (node *Res, int el,unsigned int pol);

void DelAll(node *first, node **last);

void AddLess (node **Res, int el,unsigned int pol);

int Next (node *first,int el,node **last);

void Del1 ();

};