Арифметические операции с функциями трех переменных
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО РЫБОЛОВСТВУ ПО РЫБОЛОВСТВУ
ФГБОУ ВПО МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Пояснительная записка к курсовой работе
по диiиплине Структуры и алгоритмы обработки данных
Выполнил:
студент группы
ИВТ(б) - 391(2)
Глинский В.В.
Проверил:
преподаватель Зубова Ю. В.
Мурманск 2012
Оглавление
Постановка задачи
Теория
Реализация
Подзадачи
Описание алгоритмов
Пример работы программы
Вывод
Список литературы
Приложение
Постановка задачи
Имеются две функции трех переменных вида:
(x,y,z)=S(Cxmynzk); m,n,k0.
Входная информация: текстовый файл, содержащий символьные описания функций, например,
(x,y,z)=4*x^3*y*z^2-7*y*z+z^4, F2(x,y,z)=x^5*y^5*z-9*x^3*y*z+7*y*z-11*x.
. Распознать символьную информацию.
2. Реализовать алгоритмы сложения, умножения и вычитания полиномов.
Для представления полиномов использовать кольцевые списки.
Выходную информацию оформить аналогично входной.
Теория
Многочлен (или полином) от n переменных - это конечная формальная сумма вида
,
где есть набор из целых неотрицательных чисел.
Многочлен вида называется одночленом или мономом полинома.
Каждый моном характеризуется коэффициентом c и степенями переменных i1, i2, тАж, in.
Полином называется разреженным, если большинство из его элементов равны нулю.
Связный однонаправленный список - структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну ссылку (связку) на следующий узел списка.
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Последний элемент кольцевого списка содержит указатель на первый.
Опишем два способа представления однонаправленного кольцевого списка:
1.Кольцевой список с удаленным заглавным звеном
Пустой кольцевой список с удаленным заглавным звеном представим так:
2.Кольцевой список с включенным заглавным звеном
Пустой кольцевой список с включенным заглавным звеном представим так:
Реализация
язык программирование полином арифметический
Для выполнения задания мною были выбраны язык программирования Python 2.7 и интегрированная среда разработки Python IDLE.
Для представления полиномов создан класс List (циклический список с выделенным головным элементом).
Имеет одно поле - List.first (ссылка на головной узел) и 2 метода: List.Add (процедура добавления узла) и List.Print (метод собирает полином в виде строки и возвращает эту строку).
Для представления мономов создан класс Obj.
Имеет три поля: Obj.coeff (хранит коэффициент одночлена; число с плавающей запятой), Obj.power (хранит степени каждой из трех переменных; список вида [a, b, c]) и Obj.next (ссылка на следующий элемент списка).
Для примера, одночлен -2x3z будет храниться в виде:
coeff = -2; power = [3, 0, 1].
В качестве головного узла используется узел с коэффициентом 0 и степенью -1.
Подзадачи
В данной задаче можно выделить несколько подзадач:
.Построение кольцевых списков для полиномов.
.Выполнение арифметических действий.
Описание алгоритмов
Алгоритм добавления узла:
.Проход по списку, начиная от заглавного узла, пока не найдется узел с суммарной степенью, меньшей либо равной суммарной степени добавляемого монома, или пока снова не будет достигнут заглавный узел.
.Включение нового узла в список путем переопределения ссылок, либо добавление коэффициента добавляемого монома к коэффициенту уже добавленного, при совпадении степеней всех переменных.
Алгоритм сложения полиномов:
.Создание нового списка S для хранения суммы. Список создается путем копирования, одного из слагаемых.
.Последовательное добавление всех, отличных от головного, узлов другого слагаемого к списку S.
Алгоритм вычитания полиномов:
.Создание нового списка R для хранения разности. Список создается путем копирования уменьшаемого полинома.
.Последовательное добавление всех, отличных от головного, узлов вычитаемого полинома к списку R с изменением знака коэффициента каждого узла на противоположный.
Алгоритм умножения полиномов:
.Создание нового списка M для хранения произведения.
.Последовательное перемножение каждого узла первого множителя с каждым узлом второго (путем перемножения коэффициентов и сложения соответствующих степеней) и добавление каждого получившегося монома к списку M.
Пример работы программы
Вывод
В ходе выполнения данной курсовой работы мною была реализована задача представления полиномов в виде кольцевых списков и выполнение базовых арифметических действий над ними.
В качестве языка программирования был выбран Python - высокоуровневый язык программирования с акцентом на производительность разработчика и читаемость кода. Python имеет логичную и удобную объектно-ориентированную модель, а также удобные высокоуровневые структуры данных (такие как списки и словари), что было использовано мной в этой работе.
Для хранения функций в памяти были выбраны кольцевые односвязные списки: самый удобный