Арифметические операции с функциями трех переменных
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО РЫБОЛОВСТВУ
ПО РЫБОЛОВСТВУ
ФГБОУ ВПО «МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ
ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Пояснительная записка к курсовой
работе
по дисциплине «Структуры и алгоритмы
обработки данных»
Выполнил:
студент группы
ИВТ(б) - 391(2)
Глинский В.В.
Проверил:
преподаватель Зубова Ю. В.
Мурманск 2012
Оглавление
Постановка задачи
Теория
Реализация
Подзадачи
Описание алгоритмов
Пример работы программы
Вывод
Список литературы
Постановка задачи
Имеются две функции трех переменных вида:
(x,y,z)=S(Cxmynzk);
m,n,k³0.
Входная информация: текстовый файл, содержащий символьные описания
функций, например,
(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 имеет логичную и удобную объектно-ориентированную
модель, а также удобные высокоуровневые структуры данных (такие как списки и
словари), что было использовано мной в этой работе.
Для хранения функций в памяти были выбраны кольцевые односвязные списки:
самый удобный способ хранения разреженных полиномов. Список позволяет хранить в
памяти только ненулевые значения, а также упрощает и ускоряет добавление и
поиск элементов.
Эта структура сравнительно легко описывается и проста в использовании,
что и было показано в данной работе.
Для упрощения процедуры добавления нового узла была выбрана структура с
удаленным головным узлом.
Поставленная задача была полностью выполнена.
Список литературы
1. Зубов
В.С. Справочник программиста. Базовые методы решения графовых задач и
сортировки. М.: Информационно-издательский Дом “Филинъ”, 1999. - 256 с.
. Кнут
Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир,
1978. - 846 с. (2-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.- 832 с.)
Приложение
. Описание структур
# Моном
class Obj:__init__(self, coeff, power, next=None):.coeff, self.power,
self.next = coeff, power, next
. Добавление узла
# ----------------------- Add(self, coeff, power): # Добавление в список
curr = self.first # -----------------------(curr.next.power
<> -1):(power == curr.next.power):.next.coeff += coeff(sum(power) >
sum(curr.next.power)):.next = Obj(coeff,power,curr.next)(sum(power) ==
sum(curr.next.power)):power > curr.next.power:.next = Obj(coeff,power,curr.next)=
curr.nextcurr.next.power == -1:.next = Obj(coeff,power,curr.next)
. Сложение полиномов
# -----------------------Sum(A,B): # Сложение
# -----------------------= deepcopy(A)=
B.first.next(obj.power <> -1):.Add(obj.coeff, obj.power)= obj.nextS
4. Вычитание полиномов
# ----------------------Sub(A,B): # Вычитание
# -----------------------= deepcopy(A)=
B.first.next(obj.power <> -1):= -obj.coeff.Add(coeff, obj.power)=
obj.nextR
. Умножение полиномов
# ----------------------Mult(A,B): # Умножение
# ----------------------= List()= A.first.next(obj1.power
<> -1):= B.first.next(obj2.power <> -1):= obj1.coeff * obj2.coeff=
[0,0,0]p in xrange(3):[p] = obj1.power[p] + obj2.power[p].Add(coeff,power)=
obj2.next= obj1.nextM