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

Содержание

• Введение
• 1. Постановка задачи
• 2. Теоретическая часть
• 3. Описание программы
• 4. Отладка и тестирование
• Заключение
• Список используемых источников
• Приложение


Введение

Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Разные пути или варианты, которые приходится выбирать человеку, складываются в самые разнообразные комбинации. И целый раздел математики, называемый комбинаторикой, занят поиском ответов на вопросы: сколько всего есть комбинаций в том или другом случае.

С комбинаторными величинами приходится иметь дело представителям многих специальностей: ученому-химику, биологу, конструктору, диспетчеру и т.п. Усиление интереса к комбинаторике в последнее время обуславливается бурным развитием кибернетики и вычислительной техники.

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

Написать программу для генерирования всех перестановок заданного множества в антилексикографическом порядке.

Программа должна предоставлять пользователю возможность задавать множество и выводить все возможные перестановки этого множества в антилексикографическом порядке на экран.

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

Устройствами ввода информации являются клавиатура и мышь.

Программа должна быть разработана для работы в операционной системе Microsoft Windows.

2. Теоретическая часть

Антилексикографический порядок (обозначим ) определяется следующим образом:

x1,x2,…xn < y1,y2,…,y n существует такое kn, что xk yk и xp = yp для каждого p k..

Для примера приведем перестановки множества X = {1,2,3} в антилексикографическом порядке: 123, 213, 132, 312, 231, 321.

Алгоритм генерирования перестановок в антилексикографическом порядке сформулировать удобнее. Заметим, что последовательность перестановок множества {1,2,…, n} в этом случае имеет следующие свойства, вытекающие непосредственно из определения:

1) в первой перестановке элементы идут в растущей последовательности, в последней - в убывающей другими словами, последняя перестановка - обращение первой,

2) последовательность всех перестановок можно разделить на n блоков длины (n-1), соответствующих убывающим значениям элемента в последней позиции. Первые n-1 позиций блока, содержащего элемент р в последней позиции, определяют последовательность перестановок множества {1,2,…, n}\{р} в антилексикографическом порядке.

3. Описание программы

Для написания данной программы использовался язык программирования C++. C++ -- чрезвычайно мощный язык, содержащий средства создания эффективных программ практически любого назначения, от низкоуровневых утилит и драйверов до сложных программных комплексов самого различного назначения.

Структура языка C++ позволяет наилучшим образом использовать возможности современных ЭВМ. На языке C++ программы обычно отличаются компактностью и быстротой исполнения. Программа, написанная на C++ для одной вычислительной системы, может быть перенесена с небольшими изменениями (или вообще без них) на другую.

Предсказуемое выполнение программ является важным достоинством для построения систем реального времени. Весь код, неявно генерируемый компилятором для реализации языковых возможностей.

Операции присваивания (=), инкрементации (++), декрементации (--) и другие возвращают значение. В сочетании с обилием операций это позволяет, хотя и не обязывает, создавать трудночитаемые выражения. Наличие этих операций в Си было вызвано желанием получить инструмент ручной оптимизации кода, но в настоящее время оптимизирующие компиляторы обычно генерируют оптимальный код и на традиционных выражениях.

C++ позволяет пропускать break в ветви оператора switch с целью последовательного выполнения нескольких ветвей. Такой же подход принят в языке Java. Есть мнение, что это затрудняет понимание кода.

В качестве среды программирования был выбран программный продукт от компании Microsoft Visual Studio 2010.

Для создания графического интерфейса использовались приложения Windows Form.

Интерфейс очень прост и состоит из не большего числа элементов, это кнопка запуска работы алгоритма, кнопка выхода из программы, textbox для задания множества, MessageBox для вывода ошибок и два listbox для вывода информации. (Рис.3.1)

Рисунок 3.1 Окно программы

Для запуска программы нужно ввести последнею цифру множества и нажать кнопку «Генерирование». Получив необходимые данные, алгоритм начинает работу. В качестве результата выводится список всех возможных перестановок заданного множества и количество перестановок.

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

Рисунок 3.2 Схема работы программы

4. Отладка и тестирование

В качестве среды разработки была выбрана программа Visual Studio 2010 которая содержит в себе все необходимые средства для разработки и отладки программы. Для отладки программы использовались наборы инструментов: точка остановки, пошаговое выполнение кода программы, анализ содержимого глобальных и локальных переменных.

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

В результате отладки программы выяснились, случаи в которых программа не выдавала ответ, либо отключается. Это связано с тем что при вводе были указаны символы, не принадлежащие к целочисленному типу данных, а также отрицательные числа. В таких случаях выводится сообщение (Рис. 4.1.).

Рисунок 4.1 Сообщение об ошибке

программирование перестановка антилексикографический

При вводе целого положительно числа, происходит вывод программной количество перестановок и все перестановки веденного множества. (Рис 4.2-4.3) Если ввести иные символы, выведется сообщение об ошибке приведенное выше.

Рисунок 4.2 Результаты работы программы

Рисунок 4.3 Результаты работы программы

Заключение

При выполнении данной курсовой работы были получены базовые навыки программирования на языках С++, усовершенствованы навыки разработки многомодульных программ. Изучены основные возможности среды программирования Visual Studio 2010, получены навыки отладки и тестирования программ. Были рассмотрены некоторые функции из стандартной библиотеки языка С++. Были изучены базовые алгоритмы обработки данных.

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

В дальнейшем можно реализовать функции генерации всех размещений и сочетаний заданного множества в антилексикографическом порядке.

Список используемых источников

1. Ф.Новиков - «Дискретная математика»

2. Р.Стивенс - «Алгоритмы. Теория и практическое применение»

3. P.Лафоре - «Объектно-ориентированное программирование в С++»

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