Арифметические операции с функциями трех переменных

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО РЫБОЛОВСТВУ ПО РЫБОЛОВСТВУ

ФГБОУ ВПО «МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Пояснительная записка к курсовой работе

по дисциплине «Структуры и алгоритмы обработки данных»

Выполнил:

студент группы

ИВТ(б) - 391(2)

Глинский В.В.

Проверил:

преподаватель Зубова Ю. В.

Мурманск 2012

Оглавление

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

Теория

Реализация

Подзадачи

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

Пример работы программы

Вывод

Список литературы

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

Имеются две функции трех переменных вида:

(x,y,z)=S(Cx^myⁿz^k); 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 и степенями переменных i₁, i₂, …, i_n.

Полином называется разреженным, если большинство из его элементов равны нулю.

Связный однонаправленный список - структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну ссылку («связку») на следующий узел списка.

Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Последний элемент кольцевого списка содержит указатель на первый.

Опишем два способа представления однонаправленного кольцевого списка:

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 (ссылка на следующий элемент списка).

Для примера, одночлен «-2x³z» будет храниться в виде:

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