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

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

Пояснительная записка к курсовой работе по дисциплине «Структуры и алгоритмы обработки данных»

Выполнил:

студент группы ИВТ (б) — 391(2)

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

Проверил:

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

Мурманск 2012

• Постановка задачи
• Теория
• Реализация
• Подзадачи
• Описание алгоритмов
• Пример работы программы
• Вывод
• Список литературы
• Приложение
• Постановка задачи
• Имеются две функции трех переменных вида:
• F (x, y, z)=(Cx^myⁿz^k); m, n, k0.
• Входная информация: текстовый файл, содержащий символьные описания функций, например,
• F1(x, y, z)=4*x³*y*z²−7*y*z+z⁴, F2(x, y, z)=x⁵*y⁵*z-9*x³*y*z+7*y*z-11*x.
• 1. Распознать символьную информацию.
• 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.

Подзадачи В данной задаче можно выделить несколько подзадач:

1. Построение кольцевых списков для полиномов.

2. Выполнение арифметических действий.

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

Алгоритм добавления узла:

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

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

Алгоритм сложения полиномов:

1. Создание нового списка S для хранения суммы. Список создается путем копирования, одного из слагаемых.

2. Последовательное добавление всех, отличных от головного, узлов другого слагаемого к списку S.

Алгоритм вычитания полиномов:

1. Создание нового списка R для хранения разности. Список создается путем копирования уменьшаемого полинома.

2. Последовательное добавление всех, отличных от головного, узлов вычитаемого полинома к списку R с изменением знака коэффициента каждого узла на противоположный.

Алгоритм умножения полиномов:

1. Создание нового списка M для хранения произведения.

2. Последовательное перемножение каждого узла первого множителя с каждым узлом второго (путем перемножения коэффициентов и сложения соответствующих степеней) и добавление каждого получившегося монома к списку M.

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

Вывод

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

В качестве языка программирования был выбран Python — высокоуровневый язык программирования с акцентом на производительность разработчика и читаемость кода. Python имеет логичную и удобную объектно-ориентированную модель, а также удобные высокоуровневые структуры данных (такие как списки и словари), что было использовано мной в этой работе.

Для хранения функций в памяти были выбраны кольцевые односвязные списки: самый удобный способ хранения разреженных полиномов. Список позволяет хранить в памяти только ненулевые значения, а также упрощает и ускоряет добавление и поиск элементов.

Эта структура сравнительно легко описывается и проста в использовании, что и было показано в данной работе.

Для упрощения процедуры добавления нового узла была выбрана структура с удаленным головным узлом.

Поставленная задача была полностью выполнена.

1. Зубов В. С. Справочник программиста. Базовые методы решения графовых задач и сортировки. М.: Информационно-издательский Дом «Филинъ», 1999. — 256 с.

2. Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. — 846 с. (2-е изд.: Уч.пос.-М.:Издательский дом «Вильямс», 2000. 832 с.)

Приложение

1. Описание структур

# Моном

class Obj:

def __init__(self, coeff, power, next=None):

self.coeff, self. power, self. next = coeff, power, next

# Полином

class List:

def __init__(self): # Конструктор класса

self.first = Obj (0, -1)

self.first.next = self. first

2. Добавление узла

# ———————————;

def Add (self, coeff, power): # Добавление в список

curr = self. first # ———————————;

while (curr.next.power <> -1):

if (power == curr.next.power):

curr.next.coeff += coeff

break

elif (sum (power) > sum (curr.next.power)):

curr.next = Obj (coeff, power, curr. next)

break

elif (sum (power) == sum (curr.next.power)):

if power > curr.next.power:

curr.next = Obj (coeff, power, curr. next)

break

curr = curr. next

if curr.next.power == -1:

curr.next = Obj (coeff, power, curr. next)

3. Сложение полиномов

# ———————————;

def Sum (A, B): # Сложение

# ———————————;

S = deepcopy (A)

obj = B.first.next

while (obj.power <> -1):

S.Add (obj.coeff, obj. power)

obj = obj. next

return S

4. Вычитание полиномов

# ———————————

def Sub (A, B): # Вычитание

# ———————————;

R = deepcopy (A)

obj = B.first.next

while (obj.power <> -1):

coeff = -obj.coeff

R.Add (coeff, obj. power)

obj = obj. next

return R

5. Умножение полиномов

# ———————————

def Mult (A, B): # Умножение

# ———————————

M = List ()

obj1 = A.first.next

while (obj1.power <> -1):

obj2 = B.first.next

while (obj2.power <> -1):

coeff = obj1. coeff * obj2. coeff

power = [0,0,0]

for p in xrange (3):

power[p] = obj1. power[p] + obj2. power[p]

M.Add (coeff, power)

obj2 = obj2. next

obj1 = obj1. next

return M