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

Министерство образования Российской Федерации

Пензенский государственный университет

Кафедра «Вычислительная техника»

Курсовая работа

на тему: Генерирование всех перестановок заданного множества

по курсу: Логика и основы алгоритмизации в инженерных задачах

Выполнил: студент Забродина

Принял: д.т.н., профессор Пащенко

Содержание

Введение

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

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

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

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

Заключение

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

Введение

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

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

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

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

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

Напомним, что перестановкой n-элементного множества X называется упорядоченный набор длины n, составленный из попарно различных элементов множества X. Опишем некоторые методы генерирования последовательности всех n перестановок n-элементного множества.

Не нарушая общности будем рассматривать не исходное множество Х, а множество А={1,2,…n} - множество индексов элементов, т.к. между множеством элементов из Х и множеством индексов из А существует взаимно однозначное соответствие, которое задается в виде: xi i.

Будем предполагать, что элементы множества запоминаются в виде элементов массива Р1,…, Рn. Во всех методах элементарной операцией, которая применяется к массиву Р, является поэлементная транспозиция, т.е. обмен значениями переменных Рi и Рj, где 1i, jn.

Эту операцию будем обозначать Рi :=: Рj.

Очевидно, что она эквивалентна последовательности команд:

а := Рi Рi := Рj Рj := а,

где а - некоторая вспомогательная переменная.

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

Для написания данной программы использовался язык программирования C++.

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

В частности: поддерживаются различные стили и технологии программирования, включая традиционное директивное программирование, ООП, обобщённое программирование, метапрограммирование (шаблоны, макросы).

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

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

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

Ошибки такого рода трудно выявлять, но во многих современных компиляторах предлагается диагностика некоторых подобных конструкций.

Операции присваивания (=), инкрементации (++), декрементации (--) и другие возвращают значение.

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

С другой стороны, один из основных принципов языков Си и C++ -- позволять программисту писать в любом стиле, а не навязывать «хороший» стиль.

Макросы (#define) являются мощным, но опасным средством. Они сохранены в C++ несмотря на то, что необходимость в них, благодаря шаблонам и встроенным функциям, не так уж велика.

В унаследованных стандартных Си-библиотеках много потенциально опасных макросов.

Некоторые преобразования типов неинтуитивны. В частности, операция над беззнаковым и знаковым числами выдаёт беззнаковый результат. C++ позволяет пропускать break в ветви оператора switch с целью последовательного выполнения нескольких ветвей.

Такой же подход принят в языке Java.

Есть мнение, что это затрудняет понимание кода. Например, в языке C# необходимо всегда писать либо break, либо использовать goto case N для явного указания порядка выполнения.

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

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

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

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

Для запуска программы нужно ввести множество и нажать кнопку «Генерирование».

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

Блок-схема программы представлена на рисунке 3.2.

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

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

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

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

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

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

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

Это связано с тем что при вводе были указаны символы не принадлежащие к типу int. В таких случаях выводится сообщение об ошибке, которое представлено на рисунке 4.1.

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

На рисунке 4.2 представлены результаты работы программы при правильном вводе данных, так как при не верном вводе появляется указанное выше на рисунке 4.1 окно. алгоритм перестановка программирование отладка

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

Заключение

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

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

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

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

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

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

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

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