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

Представление полиномов в виде кольцевых списков и выполнение базовых арифметических действий над ними. Реализация алгоритмов сложения, умножения и вычитания полиномов класса List на языке программирования Python 2.7. в интегрированной среде Python IDLE.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 11.01.2012
Размер файла 228,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

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

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

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

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

Выполнил:

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

ИВТ(б) - 391(2)

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

Проверил:

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

Мурманск 2012

Оглавление

  • Постановка задачи
  • Теория
  • Реализация
    • Подзадачи
    • Описание алгоритмов
  • Пример работы программы
  • Вывод
  • Список литературы
  • Приложение
  • Постановка задачи
  • Имеются две функции трех переменных вида:
  • F(x,y,z)=(Cxmynzk); m,n,k0.
  • Входная информация: текстовый файл, содержащий символьные описания функций, например,
  • F1(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.
  • 1. Распознать символьную информацию.
  • 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.

Подзадачи

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

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

Размещено на Allbest.ru


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.