Создание программного продукта для подсчета выражения

Министерство образования и науки Украины
Национальный технический университет
«Харьковский политехнический институт»



Кафедра КМММ




ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К КУРСОВОЙ РАБОТЕ
по дисциплине “Программирование”

%название курсовой%



Выполнил
ст. гр. ИФ53а




Руководитель,
доц. каф. КМММ






2014
РЕФЕРАТ


Пояснительная записка: 22 с.+2стр. оглавления, 4 рис., 0 табл., 0 приложения, 5 источников.
Объектом данной курсовой работы является раздел программирования – длинная арифметика.
Цель курсовой работы – создание программного продукта для подсчета выражения, т.н. «длинных чисел». Программа спроектирована и реализована на языке программирования С++, с использования его объектно-ориентированной части.
В результате была реализована программа, считающая длинный пример.
Ограничения:
• показатель степени должен быть натуральным числом или 0;
ПРОГРАММА, ПЕРЕВОД В ОБРАТНУЮ ПОЛЬСКУЮ НОТАЦИЮ, ПОДСЧЕТ В ПОЛЬСКОЙ НОТАЦИИ, АЛГОРИТМЫ ДЛИННОЙ АРИФМЕТИКИ 







СОДЕРЖАНИЕ


ВВЕДЕНИЕ 4
1. ОБЗОР МАТЕМАТИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ 6
1.1 Способы извлечения квадратного корня 6
1.1.1.Арифметический метод 6
1.1.2.Способ извлечения столбиком 7
1.2 Способы вычисления тригонометрических функций 9
2. ПОСТАНОВКА ЗАДАЧИ 10
3. ОПИСАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ 11
3.1 Алгоритм перевода в ОПЗ 11
3.2 Алгоритм подсчета в ОПЗ 12
3.3 Алгоритм отлова ошибок 13
3.4 Алгоритм арифметических и тригонометрических действий 14
3.4.1.Сумма двух длинных чисел 14
3.4.2.Разность двух длинных чисел 15
3.4.3.Произведение двух длинных чисел 15
3.4.4.Деление длинных чисел 15
3.4.5.Извлечение квадратного корня 16
3.4.6.Тригонометрические функции 18
3.4.7.Факториал числа 18
3.4.8.Остальные функции 19
4. ОПИСАНИЕ ПРОГРАММЫ 20
4.1 Общие сведения 20
4.2 Назначение и логическая структура 20
4.3 Пользовательский интерфейс 22
4.3.1.Арифметические операции. 22
4.3.2.Тригонометрические функции. 23
4.3.3.Факториал, модуль, степень 23
ВЫВОД 25
СПИСОК ЛИТЕРАТУРЫ 26

ВВЕДЕНИЕ
Игровой искусственный интеллект
Игровой искусственный интеллект (англ. Game artificial intelligence) — набор программных методик, которые используются в компьютерных играх для создания иллюзии интеллекта в поведении персонажей, управляемых компьютером. Игровой ИИ, помимо методов традиционного искусственного интеллекта, включает также алгоритмы теории управления, робототехники, компьютерной графики и информатики в целом.
Реализация ИИ сильно влияет на геймплей, системные требования и бюджет игры, и разработчики балансируют между этими требованиями, стараясь сделать интересный и нетребовательный к ресурсам ИИ малой ценой. Поэтому подход к игровому ИИ серьёзно отличается от подхода к традиционному ИИ — широко применяются разного рода упрощения, обманы и эмуляции. Например: с одной стороны, в шутерах от первого лица безошибочное движение и мгновенное прицеливание, присущее ботам, не оставляет ни единого шанса человеку, так что эти способности искусственно снижаются. С другой стороны — боты должны делать засады, действовать командой и т. д., для этого применяются «костыли» в виде контрольных точек, расставленных на уровне.
Эвристические алгоритмы игрового искусственного интеллекта используются в широком разнообразии во многих отраслях внутри игры. Самое очевидное применение игрового ИИ проявляется в контролировании неигровых персонажей, хотя скриптинг тоже является очень распространённым способом контроля. Поиск пути является другим широко распространённым применением игрового ИИ, — он особенно проявляется в стратегиях реального времени. Поиск пути является методом для определения того, как неигровому персонажу перейти с одной точки на карте к другой: нужно учитывать ландшафт, препятствия и, возможно, «туман войны».
Игра "16384"
Игра 16384 - это логическая игра, действие которой происходит на гексагональном поле 3x3x3 с гексагональными плитками, расположенными на ней (см. рис. 1)

Рис. 1 Скриншот игры 16384

Игра идет по следующим правилам:
В каждом раунде появляется плитка номинала с номиналом "1", "2" или "4"
Нажатием клавиши игрок может скинуть все плитки игрового поля в одну из 6 сторон. Если при сбрасывании две плитки одного номинала «налетают» одна на другую, то они слипаются в одну, номинал которой равен сумме соединившихся плиток. После каждого хода на свободной секции поля появляется новая плитка номиналом "1". Если при нажатии кнопки местоположение плиток или их номинал не изменится, то ход не совершается.
За каждое соединение игровые очки увеличиваются на номинал получившейся плитки.
Игра заканчивается проигрышем, если после очередного хода невозможно совершить действие.
Игра заканчивается выигрышем, если после очередного хода появится плитка с номиналом "16384".
Суть работы
Суть моей работы состояла в написании искусственного интеллекта для игры "16384".
ОБЗОР МАТЕМАТИЧЕСКИХ МЕТОДОВ
Для создания ИИ я использую алгоритм минимакса с оптимизацией "альфа - бета отсечения".
Термины
Для облегчения дальнейшего объяснения я буду оперировать следующими терминами:
Игра с нулевой суммой
Игра с нулевой суммой - игра с участием 2х игроков, в которой победа первого игрока означает проигрыш второго (и наоборот).
Дерево игры
Дерево игры - граф, узлы которого представляют собой состояния игрового поля одного из игроков (см. рис. 2)

Рис. 2 Пример дерева игры в игре "крестики-нолики"
Минимаксная процедура
Для сокращения дерева игры, можно делать как человек: он не способен продумать все варианты развития игры в соответствии со своим ходом, но он может продумать возможные варианты на несколько ходов вперед и выбрать наилучший из них. Количество шагов, на которое способен продумать игру человек, ограничено его интеллектуальными способностями. В случае с компьютерным решением, таким ограничением может стать память или время работы алгоритма. В простейшем случаем можно ограничиться глубиной раскрытия дерева.
Самый интересный аспект такого подхода, это способ оценки выгоды от того или иного хода. В самом простейшем случае, можно выделить некоторые состояния игрового поля (ничья, победа и поражение) и присвоить каждому из них некоторый числовой коэффициент(оценку) (см. рис. 3).

Рис. 3 Ничего = 0; ничья = 2; победа = 5; проигрыш = -5)
Такая оценка строится не для каждого узла дерева игры, а только для его листьев. Оценка же каждого узла получается из следующих соображений: на каждом этапе раскрытия дерева решений, начиная с последнего (на котором получаются листы с оценками), выбирается ход, наиболее предпочтительный для игрока, чей ход приводит к порождению узлов. При этом, для игрока, за которого ведется игра, оценка должна стремиться к максимуму, а для противника к минимуму.
Так, играя (к примеру) за нолики, каждый нечетный ход представляет их интересы и выбирается ход с наибольшей оценкой (игрок MAX), а каждый четный - интересы крестиков, выбирается ход с наименьшей оценкой (игрок MIN). Такой подход называется минимаксной процедурой (см. рис. 4).

Рис. 4 Пример дерева игры, раскрытого на глубину в три хода
Альфа-бета отсечение
Благодаря минимаксу количество раскрываемых вершин существенно сократилось, но для реализации умного ИИ понадобится раскрывать дерево игры на достаточно большую глубину, а вместе с тем производить оценку все большего количества вершин. Это может приводить к существенным издержкам как по времени, так и по памяти. Поэтому, не смотря на то, что минимаксная процедура существенно сокращает количество раскрываемых вершин, она все еще не дает приемлемых результатов.
Одной из оптимизаций минимакса является альфа-бета отсечение. Рассмотрим её на примере дерева гипотетической игры " кружки-ромбики" (см. рис. 5):

Рис. 5 дерево игры " кружки-ромбики", кружки выбирают max, ромбики - min
Предположим, что мы раскрыли крайнюю левую вершину за кружки на глубине 3, получили оценку 7 и перешли к раскрытию следующей вершины на этой глубин. Видно, что следующая вершина последняя в этой ветке и после ее раскрытия мы перейдем на глубину выше, где выбор будут делать ромбики. Ромбики же, получив оценку первой вершины 7, очевидно, не станут делать выбор вершины с большей оценкой и вторая, раскрытая нами вершина с оценкой 9, выбрана не будет. Таким образом, обзор этих листьев можно было завершить, когда мы нашли вершину 8, тогда вершина была бы равна минимум 8, что меньше 7 (вершины на том же уровне левее), а следовательно правая ветка уже не могла бы быть выбрана.
Вот как работает оптимизация: раскрытие корневой вершины начинается с определенными параметрами альфа и бета. В простейшем случае им присваиваются максимально и минимально допустимые оценки. Далее, дерево раскрывается на максимальную глубину, которая может определяться фиксированным значением глубины, временем или памятью. Производится эвристическая оценка полученных листов (о ней далее). Оценки сравниваются на предмет попадания в диапазон альфа-бета. Если раскрытие происходит за игрока MAX и оценка оказывается больше беты, или раскрытие происходит за игрока MIN и оценка оказывается меньше альфа, то дальнейшее рассмотрение вершин становится не целесообразным.
Оценивающая функция
Для реализации минимакса (и альфа-бета отсечения) нужна оценивающая функция, которая будет возвращать выгодность данного состояния игрового поля для игрока (в нашем случае, для пользователя (точнее, для бота, выполняющего его функцию), который будет играть в игру 16384).
Опытным путем была подобрана оптимальная формула, позволяющая достигнуть достаточной точности при удовлетворительной глубине поиска:
score = max⁡((actualScore+ log (1 + actualScore)*numberOfEmptyCells-clusteringScore),min⁡〖(actualScore,1)〗)
Где actualScore - это кол-во очков на данный момент, numberOfEmptyCells - это кол-во пустых клеток на поле, а clusteringScore - это значение, отвечающее за "беспорядочность" плиток (см. ниже).
Функции max и min используются, чтобы функция не могла вернуть отрицательное значение. При отрицательном значении первого числа в max(), вернется 0 если actualScore = 0 и 1, если не равно.
Рассмотрим каждое из значений подробнее.
actualScore. По очевидным причинам мы используем кол-во очков в оценивающей функции. Состояния поля с большим числом очков как правило предпочтительнее, чем с меньшим.
numberOfEmptyCells. Так как с каждым ходом на наше поле добавляются новые плитки, предусмотрительно всегда оставлять несколько пустых клеток, дабы они не заполнились в следующих ходах и игра не была бы проиграна. В оценивающей функции используется логарифмическое значение от кол-ва очков, умноженное на кол-во пустых клеток. Это логично, т. к. при малом кол-ве очков (т. е. в самом начале игры кол-во пустых клеток не так важно, т. к. плитки легче складываются), при большом же кол-ве очков кол-во пустых клеток очень важно, т. к. игра заканчивается от их недостатка.
clusteringScore. Мы используем "оценку беспорядочности" чтобы определить, как сильно разбросаны плитки по доске. Когда плитки с одинаковыми значениями рядом, их проще соединить, а следовательно, тяжелее проиграть игру. В этом случае clusteringScore принимает низкое значение. Когда же состояние "раскиданное", clusteringScore принимает большое значение. В функции clusteringScore вычитается из суммы предыдущих двух значений (см. функцию), таким образом, clusteringScore гарантирует, что из двух состояний будет выбрано более "сгруппированное". Алгоритм clusteringScore построен так, что он "учитывает" советы по игре: "нужно держать плитки с одинаковыми значениями рядом, чтобы их было легче соединять" и "плитки с большими значениями лучше держать вместе (чтобы потом при слиянии меньшей из плиток и становлении ее равной второй плитке их было легко соединить)". Давайте посмотрим, как подсчитывается clusteringScore. Для каждой плитки на поле мы подсчитываем среднюю разницу значения плитки и значений ее соседей по модулю:
(∑▒〖модулей разностей значений с соседями〗)/(кол-во соседей)
ПОСТАНОВКА ЗАДАЧИ
Для реализации искусственного интеллекта для игры 16384 понадобится следующее:
1) Требуется сама игра 16384 с графическим интерфейсом и возможностью играть самому. Игра должны корректно, по правилам, работать. Выдавать уведомление о выигрыше при выигрыше и уведомление о проигрыше при проигрыше. Игра должна сохранять лучший результат (максимальное кол-во очков) в файл и показывать лучший и текущий результат во время игры. Для лучшего внешнего вида плитки будут изменять свой цвет в зависимости от своего значения.
2) Искусственный интеллект, который будет приводить игру к выигрышу за достаточно малое время, при этом не сильно используя системные ресурсы. Искусственный интеллект состоит из алгоритма минимакса с оптимизацией альфа-бета отсечения, и оценивающей функции, позволяющей оценивать выгодность листьев дерева игры для игрока.
ОПИСАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ
В данном разделе описываются разработанные алгоритмы: перевод строки в ОПЗ, подсчет выражения в ОПЗ, алгоритмы отлова ошибок в исходной строке, а также алгоритмы арифметических действий.
Алгоритм перевода в ОПЗ
Обра́тнаяпо́льскаянота́ция (ОПН) — форма записи математических выражений, в которой операнды расположены перед знаками операций. Также именуется как обратная польская запись, обратная бесскобочная запись (ОБЗ), постфиксная нотация, бесскобочная символика Лукашевича, польская инверсная запись, ПОЛИЗ.
Автоматизация вычисления выражений в обратной польской нотации основана на использовании стека. Алгоритм вычисления для стековой машины элементарен:
Обработка входного символа:
Если на вход подан операнд, он помещается на вершину стека.
Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
Если входной набор символов обработан не полностью, перейти к шагу 1.
После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.
Реализация стековой машины, как программная, так и аппаратная, чрезвычайно проста и может быть очень эффективной. Обратная польская запись совершенно унифицирована — она принципиально одинаково записывает унарные, бинарные, тернарные и любые другие операции, а также обращения к функциям, что позволяет не усложнять конструкцию вычислительных устройств при расширении набора поддерживаемых операций. Это и послужило причиной использования обратной польской записи в некоторых научных и программируемых микрокалькуляторах.
3.2 Алгоритм подсчета в ОПЗ
Для наглядности далее приведен пример вычисления выражения в обратной польской записи. На рисунке 1.1 написаны пошаговые изменения стека и оставшейся цепочки при подсчете в ОПЗ.
Обратная польская запись идеально подходит для вычисления формул на компьютере со стеком. Формула состоит из n символов, каждый из которых является либо операндом, либо оператором. Алгоритм для вычисления формулы в обратной польской записи с использованием стека прост. Нужно просто прочитать обратную польскую запись слева направо. Если встречается операнд, его нужно пометить в стек. Если встречается оператор, нужно выполнить заданную им операцию.
В качестве примера рассмотрим вычисление следующего выражения: (8+2*5)/(1+3*2-4) Соответствующая формула в обратной польской записи выглядит так: 825*+132*+4-/
Число на вершине стека – это правый операнд (а не левый). Это очень важно дл операций деления, вычитания и возведения в степень, поскольку порядок следования операндов в данном случае имеет значение (в отличие от операций сложения и умножения). Другими словами, операция деления действует следующим образом: сначала в стек помещается числитель, потом знаменатель, и тогда операция даёт правильный результат. Отметим, что преобразовать обратную польскую запись в машинный код очень легко: нужно просто двигаться по формуле в обратной польской записи, записывая по одной команде для каждого символа. Если символ является константой или переменной, нужно вписывать команду помещения этой константы или переменной в стек, если символ является оператором, нужно вписывать команду выполнения это операции

Рисунок 1Пошаговый подсчет в ОПЗ
Алгоритм отлова ошибок
Я реализовал 2 функции отлова ошибок.
1) Отлов ошибок в записи
2) Отлов ошибок в выражении
Первая функция отлавливает такие ошибки:
1) Неправильное кол-во скобок (кол-во открывающихся не равно кол-ву закрывающихся), или две разные скобки идут подряд
2) Два операнда идут подряд
3) Введен неизвестный символ
4) Неправильно введена функция факториала
5) Неправильно введен унарный минус
6) Если после закрывающейся скобки стоит сразу цифра или перед открывающейся(например “6(8*7+9)”)
Отлов второго типа ошибок(в выражении) реализован в функции подсчета в обратной польской нотации. И возвращает такие ошибки(как только нашла ошибку, сразу возвращает номер ошибки).
1) Больше 1 точки в числе
2) Деление на 0
3) Число под знаком факториала не целое
4) Число под знаком факториала отрицательное
5) Число возведение в степень не целое(т.к. я возведение в степень выполняю просто умножением числа n на себя k раз, то k должно быть целым и большим 0)
6) Показатель степени меньше 0
7) Число под корнем меньше 0
8) Тангенс в данной точке не существует
Если есть хотя бы одна ошибка, программа выдаст сообщение об ошибке и выведет его в MessageBox.
Алгоритм арифметических и тригонометрических действий
В данном подпункте рассматриваются алгоритмы реализации арифметических действий (сложение, вычитание, умножение, деление, взятие корня, возведение в степень и т.д.) и тригонометрических функций(sin, cos, tan, ctg)
Сумма двух длинных чисел
Складывание происходит в столбик, складываются соответствующие разряды, при необходимости выполняется переход через десяток
Разность двух длинных чисел
Для начала, необходимо проверить, можно ли преобразовать разность в сумму, например,a-(-b) =a+b и т.п., если это невозможно, то требуется проверить, не равны ли числа, если равны, надо возвратить 0. Если ничего из этого не выполняется, то необходимо привести разность к такому виду, чтобы она была больше 0(например, если a>0,b>0,a <b, то a-b=-(b-a), причем, b-a>0). После приведения к такому виду, требуется вычитать по разрядам.
Произведение двух длинных чисел
Для начала определяется знак произведения. Т.к. отрицательное число характеризуется полем sign = -1, а положительное – 1, то легко заметить, что знак произведения будет равен знаку произведения двух полей sign двух умножаемых чисел. Произведение осуществляется столбиком. Надо перебрать только такие j, что разряд, куда помещается произведение i-й цифры первого числа на j-ю второго был в пределах NEG_ACC..POS_ACC, где NEG_ACC – количество цифр после запятой, а POS_ACC – количество чисел до запятой, все остальные цифры просто обрубаются. Производится умножение i-й цифры первого числа на j-ю второго, результат записывается в p. Если p >10, то лишние разряды распихиваются по разрядам(как при умножении в столбик на бумаге).
После того, как посчитано само число результату присваивается нужный знак (который определяется на первом шаге)
Деление длинных чисел
Для начала определяется знак результата (так же как и в случае умножения). Т.к. деление производится столбиком, то первым шагом находятся порядки чисел. Далее, вычисляется, на сколько надо сдвинуть делитель, чтобы его порядок совпал с делимым, и производится сдвиг на нужное количество. После этого, подбирается такое j и
(tempnum = j*делитель)
, где делитель уже сдвинут под делимое. И чтобы tempnum был меньше или равен нашему делимому, но (j+1)*делитель был больше, чем делимое. В таком случае j это цифра, номер которой равен разности разрядов двух чисел. После, производится вычитание из делимого j*делитель и сдвиг делителя вправо на один разряд. В конце присваивается знак результата и возвращаетсяон(результат).
Извлечение квадратного корня
Еще 4000 лет назад вавилонские ученые составляли наряду с таблицами умножения и таблицами обратных величин (при помощи которых деление чисел сводилось к умножению) таблицы квадратов и квадратных корней из чисел. При этом они умели находить приблизительное значение квадратного корня из любого целого числа. Вавилонский способ приближенного вычисления квадратных корней можно иллюстрировать на следующем примере, изложенном в одной из найденых при раскопках клинописных табличек.
Вычислим √2, то есть найдем с помощью метода приближенных вычислений положительный корень уравнения x2 = 2. Это уравнение равносильно следующему: x=2/x(1)
Предположим, что мы имеем некоторое приближенное значение xo числа равное 1.
Согласно (1), xo =1 надо сравнить с числом 2/x_0 , то есть с 2/1 ; если xo и2/x_0
совпадают, то xo - точное значение числа √2 равное 1. Так как 1 не равно √2, тоодно из чисел меньше, а другое больше, чем√2 , то есть√2лежит между 1 и 2/1;.Можно предположить, что среднее арифметическое этих чиселx_1=1/2*(x_0+2/x_0 )является лучшим приближением числа√2, чем исходное приближение xo, то есть
x_1=1/2*(x_0+2/x_0 )=1,5
Это приближение x1можноулучшить таким же способом, то есть взять среднее арифметическое чисел x1и2/x_1 и так далее.
x_2=1/2*(x_1+2/x_1 )=1,416666667
x_3=1/2*(x_2+2/x_2 )=1,4142115686
x_4=1/2*(x_3+2/x_3 )=1,414213562
x_5=1/2*(x_4+2/x_4 )=1,414213562
Как видим, уже пятое приближение не отличается (при вычислениях с девятью знаками после запятой) от четвертого. Естественно принять, что приблизительно равно 1,414213562.
x_n-√2=1/2*(x_(n-1)+2/x_(n-1) )-√2=〖(x_(n-1)-2)〗^2/(2*x_(n-1) ) (2)
Какова точность вавилонского способа? Для ответа на этот вопрос проведем вычисления:
Равенство (2) дает возможность выразить ошибку приближения xn (то есть число x_n-√2) через ошибку предыдущего приближения xn-1:
x_0-√2=(x_0-2)^2/(2*x_0 )=0,500 или 50%
x_1-√2=(x_1-2)^2/(2*x_1 )=0,083 или 8,3%
x_2-√2=(x_2-2)^2/(2*x_2 )=0,012 или 1,2%
Формула, с помощью которой вычислялись последовательные приближения числа по вавилонскому способу, может быть записана следующим образом:
x_n = f(x_(n-1)). (3)
В данном случае в качестве функции f(x) берется функция
f(x) = 1/2(x + 2/x)(4)
Легко видеть также, что уравнение (1), которое приближенно решалось этим способом, переписывается с помощью функции (4) в виде f(x) = x. (5)
Такой способ приближенного вычисления квадратных корней называется методом итераций.
Итерация (с латинского iteratio - повторение) - результат повторного применения какой-либо математической операции.
Тригонометрические функции
Реализованные в данной программе тригонометрические функции – периодические, следовательно можно воспользоваться формулами приведения, такими как sin(2*pi+x)=sin(x) и аналогичными для других функций.То есть для нахождения тригонометрической функции от длинного числа, достаточно посчитать остаток от деления числа на его период и стандартными функциями для поиска синуса/косинуса/и т.д. посчитать их.
Факториал числа
Факториал высчитывается по стандартной формуле(6):
n!=1*2*3*…*(n-1)*n (6)
Таким образом, для вычисления n!, достаточно произвести умножение n-1 раз
Остальные функции
1) Сравнение двух чисел по модулю. Для реализации сравнения двух чисел по модулю требуется пройти циклом с максимального разряда до минимального(с POS_ACC-1 до –NEG_ACC), сравнивая одинаковые разряды, если числа равны, продолжать идти, в противном случае возвратить число, у которого разряд больше.
2) Сравнение двух чисел. Для начала требуется сравнить знаки чисел. Если знаки одинаковые, происходит сравнивание их по модулю, в противном случае, больше то число, которое положительное.
3) Степень числа(n^k). Просто k раз производится умножение на себя числоn.
4) Сдвиг числа на n разрядов влево(также работает и вправо, если n < 0). Простопроисходит сдвиг массива на n элементов влево(если это возможно).
ОПИСАНИЕ ПРОГРАММЫ
Общие сведения
Программа была создана в среде разработки Visual C++, занимает незначительный объем памяти (до 1 мб).
Программа будет работать на любом компьютере, где установленна платформа .NET не ниже 4.0. Т.к. в программе нет параллельных вычислений, от кол-ва ядер процессора скорость вычислений не зависит.
Запуск осуществляется двойным щелчком по иконке.
Назначение и логическая структура
Программа считает выражения со скобками, арифметическими действиями(+,-,*,/), тригонометрическими функциями, извлекает корень из числа, считает степень, считает факториал чисел.
Длинная арифметика реализована при помощи структуры LongNum.
Структура LongNum имеет такие поля: chardata[10000] – собственно само длинное число, которое хранится в виде массива символов, intsign – знак числа(-1 при отрицательном, 1 при положительном).
Первые NEG_ACC цифр это цифры после запятой, остальные POS_ACC это до запятой.
intpriorityAction(char); получает символ операции, возвращает ее приоритет.
intgetError(char*); получает строку, возврещает номер ошибки или 0, если ошибок нет.
intLNtoInt(LongNum, int&); переводит число из LongNumв int получает длинное число и ссылку на int, возвращает номер ошибки, или 0, если ошибок нет, в int& записывает результат перевода
voidtransferToPolishNotation(char*); переводит строку в обратную польскую нотацию. Получает строку, которую необходимо перевести, ничего не возвращает(результат записывает в глобальный стек).
intcountInBackPolishNotation(stack<char*>, LongNum&); считаетвыражение в обратной польской нотации. Получает стек операций, и ссылку на LongNum, возвращает номер ошибки или 0, если ошибки нет, результат записывается в LongNum&
intconvertCharToInt(char*);переводитchar*вint
voidLNsubLN( LongNum&ln,LongNumsubtractment);вычитаетизlnsubtractment, результатзаписываетвln
intLNpow(LongNum&, LongNum); возводит число в степень. Результат записывает в LongNum&
intLNsqrt(LongNum&); извлекает корень из числа
voidLNcos(LongNum&); считает косинус числа
voidLNsin(LongNum&);считает синус числа
intLNtg(LongNum&ln);считает тангенс числа. Возвращает номер ошибки, результат записывает в ln
intLNctg(LongNum&ln);считает котангенс числа. Возвращает номер ошибки, результат записывает в ln
intconvertCharToLongNum(char *, LongNum&);переводитchar*вLongNum&
char* LNoutput(LongNumln);
intLNcmp(constLongNum&a, constLongNum&b)
intLNabscmp(constLongNum&a, conststructLongNum&b)сравниваетпомодулюдвачиславозвращает 1 если |a|>|b|; -1 если |a|<|b| и возвращает 0 еслиониравны
LongNumtoLN(int n) переводитn вLongNum
intLNcmp(constLongNum&a, constLongNum&b)сравнение двух длинных чисел.Возвращает 1 если a>b ; -1 если a<bи возвращает 0 если они равны.
voidLNaddLN(LongNum&ln, LongNumaddment) сложение двух длинных чисел.
voidLNmulLN(LongNum&ln, LongNummultiplier) умножение двух длинных чисел.
voidLNshlLN(LongNum&ln, intdisplacement) сдвигдлинногочисланаdisplacementразрядов.
voidLNdivLN(LongNum&ln, LongNumdivider) деление длинных чисел
intLNfac(LongNum&ln) считает факториал числа. Возвращает номер ошибки, результат записывает в ln
intLNsqrt(LongNum&ln) считает корень квадратный из числа. Возвращает номер ошибки, результат записывает в ln.
Пользовательский интерфейс
Далее будет описан корректный ввод строки в текстовое поле.
Арифметические операции.
Используются так же, как и при обычной записи, например:
6+7
8-9
4*6
6/3
Тригонометрические функции.
Вначале в скобках указывается число, от которого берется функция, затем идет сама функция
(60)sin
(120)cos
(30)tan
(90)ctg
Факториал, модуль, степень
!(10)
abs(-5)
5^2
Пример ввода выражения:
(!(5)/2)sin*abs(-5)^3 (рисунок 2)
Выражение вводится в верхнее текстовое поле(оно подписано)
Во второе текстовое поле(также подписанное) вводится кол-во цифр после запятой
В третье поле, самое нижнее, выводится ответ. Также ответ показывается в MessageBox’е.
Рисунок 3 и Рисунок 4 иллюстрируют пример работы программы и пример вывода ошибки соответственно.

Рисунок 2 Пример ввода

Рисунок .3 Скриншот работы программы

Рисунок 4 Скриншот выдачи ошибки

ВЫВОД
В данной курсовой был разработан калькулятор длинных чисел. Для этого были реализованы: структура для работы с длинными числами, обратная польская нотация и подсчет выражения в ней, отлов ошибок.
Чтобы оптимизировать вычисления можно было записывать число в 10000 системе счисления, также есть метод быстрого умножения, который позволяет умножить числа за меньшее время.
СПИСОК ЛИТЕРАТУРЫ
Википедия. Обратная польская запись. / Неизвестный автор // Программирование. - 2007.
Бурсук. Методы извлечения квадратного корня. / Бурсук В.О. // Алгебра. – 2009. – С.6-8
Википедия. Длинная арифметика. / Неизвестный автор // Математика. – 2007.
Хабрахабр. Обратная польская запись. / GORKOFF // алгоритмы. – 2010.