Генерирование всех перестановок заданного множества в лексикографическом порядке
Разработка переборного алгоритма оптимального решения среди большого числа вариантов. Монотонность генерируемой последовательности для упрощения задачи поиска экстремума целевой функции. Графический интерфейс с возможностью ввода и вывода информации.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 22.02.2019 |
| Размер файла | 383,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
КУРСОВАЯ РАБОТА
по курсу "Логика и основы алгоритмизации в инженерных задачах"
на тему "Генерирование всех перестановок заданного множества в лексикографическом порядке"
Выполнил: Иванов Н.А.
Содержание
- Введение
- 1. Постановка задачи
- 2. Теоретическая часть
- 3. Описание программы
- 4. Отладка и тестирование
- Заключение
- Список используемых источников
Введение
Во многих прикладных задачах требуется найти оптимальное решение среди очень большого числа вариантов, важно чтобы их количество было конечным или, в крайнем случае, генерируемая последовательность должна иметь монотонный характер для упрощения задачи поиска экстремума целевой функции в его окрестностях. В общем случае переборный алгоритм состоит в генерации всех возможных вариантов и сравнении их между собой в поиске наилучшего. Комбинаторика - раздел математики, в котором изучаются вопросы о том, сколько и каких комбинаций подчиненных определенным законам можно составить из выделенных объектов.
1. Постановка задачи
Написать программу для генерирования перестановок заданного множества в лексикографическом порядке.
Программа должна предоставлять пользователю возможность задавать конечное число и выводить все возможные перестановки до заданного числа включительно в лексикографическом порядке на экран. Для удобства использования программы должен быть разработан графический интерфейс с возможностью ввода и вывода информации.
Устройствами ввода информации являются клавиатура и мышь.
Программа должна быть разработана для работы в операционной системе Microsoft Windows.
2. Теоретическая часть
Данный метод легче всего понять, если в качестве переставляемых элементов взять числа 1,…,n. На множестве всех перестановок определим лексикографический порядок:
x1,x2,…xn < y1,y2,…,yn существует k1, такое что xk < yk и xp= yp для каждого p < k.
Заметим, что если вместо чисел 1,2,…, n взять буквы а, б,…,р с естественным порядком абв…р, то лексикографический порядок определяет стандартную последовательность, в которой слова длины n появляются в словаре.
Для примера приведем перестановки множества X = {1,2,3} в лексикографическом порядке:
123, 132, 213, 231, 312, 321.
Начиная с перестановки (1,2,…,n), переход от текущей перестановки P=(p1,p2,…,pn) к перестановке, следующей за текущей в смысле лексикографического порядка, осуществляется последовательным выполнением следующих действий:
просмотр Р справа налево в поисках самой правой позиции k, в которой pk<pk+1 (если такой позиции k нет, то текущая перестановка является последней и следует закончить генерацию);
просмотр P от pk слева направо в поисках наименьшего из таких элементов pm, что k<m и pk<pm; транспозиция элементов pk и pm и обращение отрезка pk+1,…, pn путем транспозиции симметрично расположенных элементов (заметим, что элементы обращаемого отрезка расположены в порядке убывания).
Например, для п=8 и Р=(2,6,5,8,7,4,3,1) имеем pk =5 и pm=7, результат транспозиции pk и pm - (2,6,7,8,5,4,3,1), результат обращения отрезка pk+1,…, pn переводит Р в перестановку (2,6,7,1,3,4,5,8), которая следует за Р в лексикографическом порядке.
3. Описание программы
Изначально была проведена работа с теорией по данной теме. В результате был найден подходящий алгоритм для решения поставленной задачи. Был спроектирован интерфейс
В качестве среды программирования был выбран программный продукт от компании Visual Studio 2015.
Для создания графического интерфейса использовался пакет Win32.
Интерфейс очень прост и состоит из не большего числа элементов, это кнопка запуска работы алгоритма, кнопка выхода из программы, textbox для задания множества, MessageBox для вывода ошибок и два listbox для вывода информации. На рисунке 3.1 представлено диалоговое окно программы.
Рисунок 3.1 - Окно программы
4. Отладка и тестирование
алгоритм экстремум функция интерфейс
В качестве среды разработки была выбрана программа Visual Studio 2015 которая содержит в себе все необходимые средства для разработки и отладки модулей и программ. Для отладки программы использовались различные инструменты: точка остановки, пошаговое выполнение кода программы, анализ содержимого глобальных и локальных переменных.
Тестирование проводилось в рабочем порядке, в процессе разработки и после завершения написания программы.
В ходе отладки программы выяснились, случаи в которых программа не может выдать ответ. Это связано с тем что при вводе были указаны символы не принадлежащие к типу int. В таких случаях выводится сообщение об ошибке, которое представлено на рисунке 4.1.
Рисунок 4.1 - Сообщение об ошибке
На рисунке 4.2 представлены результаты работы программы при правильном вводе данных, так как при неверном вводе появляется указанное выше на рисунке 4.1 окно.
Рисунок 4.2 - Результаты работы программы
Заключение
При выполнении данной курсовой работы были получены базовые навыки программирования на языках С++, усовершенствованы навыки разработки многомодульных программ. Изучены основные возможности среды программирования Visual Studio 2015, получены навыки отладки и тестирования программ. Были изучены базовые алгоритмы обработки данных.
В результате выполнения курсовой работы была разработана программа, предназначающаяся для генерации всех перестановок заданного множества в лексикографическом порядке.
В дальнейшем можно реализовать функции генерации всех размещений и сочетаний заданного множества.
Список используемых источников
1. Бьёрн Страуструп - "Язык программирования С++"
2. Р. Стивенс - "Алгоритмы. Теория и практическое применение"
3. Э.Л. Балюкевич, Л.Ф. Ковалева, А.Н. Романников.- "Дискретная математика"
4. Гринченков Д.В., Потоцкий С.И. - "Математическая логика и теория алгоритмов для программистов"
5. P. Лафоре - "Объектно-ориентированное программирование в С++"
Размещено на Allbest.ru
...Подобные документы
Методика решения задачи по выбору подмножества, состоящего из нескольких компонент. Характеристики, порядок записи и листинг программ по генерации множества всех подмножеств из N элементов и генерации последовательности чисел в лексикографическом порядке.
реферат [22,4 K], добавлен 07.03.2010Постановка задачи. Математическое обоснование. Последовательность разбиений множества. Язык программирования. Реализация алгоритмов. Генерирование разбиений множества. Генерирование всех понятий.
курсовая работа [29,9 K], добавлен 20.06.2003Решение задач по информатике, перебор различных комбинаторных конфигураций объектов и выбор наилучшего, с точки зрения условия задачи. Генерация k-элементных подмножеств, всех подмножеств данного множества, всех перестановок n-элементного множества.
реферат [44,0 K], добавлен 03.01.2010Методика разработки программной модели числового метода поиска экстремума функции двух переменных, конструирование ввода исходных данных и вывода с сохранением. Исследование ограничений на функцию, обусловленные методом поиска и средствами моделирования.
курсовая работа [195,4 K], добавлен 17.04.2010Использование программой функции ввода-вывода данных для реализации дружественного интерфейса с пользователем. Функции консоли и особенности их применения для обеспечения аккуратного ввода информации и упорядоченного вывода. Обзор стандартных функций.
лабораторная работа [40,4 K], добавлен 06.07.2009Разработка алгоритма работы. Выбор и обоснование структурной схемы. Разработка функциональной схемы блока ввода и блока вывода. Проектирование принципиальной схемы блока ввода и блока вывода, расчет элементов. Разработка программного обеспечения.
курсовая работа [1,7 M], добавлен 25.12.2011Особенности dirent как входной структуры каталога, независимой от файловой системы. Получение содержимого каталога и информации о файле. Разработка блок-схемы алгоритма программы. Изучение программного обеспечения для реализации поставленной задачи.
курсовая работа [1,1 M], добавлен 22.07.2014Обзор методов и подходов решения поставленной задачи аппроксимации логического вывода экспертной системы. Разработка и описание метода сетевого оператора для решения данной задачи. Разработка алгоритма решения. Проведение вычислительного эксперимента.
дипломная работа [1,5 M], добавлен 23.02.2015Практическое обоснование выгодности использования web-модуля "Расширенный поиск по сайту". Схема отображения процесса ввода и запроса информации. Описание алгоритма и модель решения задачи. Структура и характеристика базы данных расширенного поиска.
дипломная работа [2,4 M], добавлен 19.01.2017Классификация методов оптимизации. Обзор и выбор языка C#. Алгоритмический анализ задачи, описание алгоритма решения. Графические схемы разработанных алгоритмов. Разработка приложения и результаты тестовых испытаний. Интерфейс пользователя, тестирование.
курсовая работа [1,6 M], добавлен 08.03.2016Периферийные или внешние устройства ввода информации: клавиатура, манипуляторы, джойстик, трекбол. Сенсорные устройства ввода: сенсорный манипулятор, световое перо, графический планшет. Матричные, струйные, лазерные, термические и литерные принтеры.
реферат [280,7 K], добавлен 25.11.2010Построение пространства допустимых решений. Нахождение оптимального решения с помощью определения направления убывания целевой функции. Нахождение оптимальной точки. Поиск экстремумов методом множителей Лагранжа. Условия экстремума Куна-Таккера.
контрольная работа [396,2 K], добавлен 13.09.2010Сущность симплекс-метода. Общая характеристика задачи о смесях. Разработка основных алгоритмов решения задачи. Решение задачи в среде визуального программирования Delphi. Проектирование интерфейса пользователя. Разработка форм ввода-вывода информации.
курсовая работа [476,6 K], добавлен 22.05.2012Постановка задачи нелинейного программирования. Определение стационарных точек и их типа. Построение линий уровней, трехмерного графика целевой функции и ограничения. Графическое и аналитическое решение задачи. Руководство пользователя и схема алгоритма.
курсовая работа [2,5 M], добавлен 17.12.2012Разработка программного продукта для поиска максимально удалённых вершин в графе. Характеристика ориентированного, смешанного и изоморфного графов. Обзор способов представления графа в информатике. Алгоритм поиска пути. Графический интерфейс программы.
курсовая работа [384,0 K], добавлен 10.01.2015Считывание информации из файла, анализ заголовка. Установка видеорежима и анализ его параметров. Разработка процедуры вывода изображения на экран. Методы вывода сообщений. Разработка алгоритма, удовлетворяющего требованиям задания и интерфейса программы.
курсовая работа [23,6 K], добавлен 17.05.2013Организация и назначение консольного ввода-вывода, необходимые для этого функции и их применение. Библиотеки, организующие функционирование потокового ввода-вывода, выполняемые операции. Арифметические операции и математические функции в среде С++.
лабораторная работа [33,8 K], добавлен 15.07.2009Методы поиска подмножеств множества вершин V графа G, удовлетворяющих определенным условиям и свойствам. Понятие независимых множеств и порядок их генерации. Определение доминирующего множества. Основные этапы решения задачи о наименьшем разбиении.
контрольная работа [32,1 K], добавлен 11.03.2010Оптимизация решения задачи с помощью алгоритма отжига. Анализ теории оптимизации как целевой функции. Метод градиентного спуска. Переменные и описание алгоритма отжига. Представление задачи коммивояжера через граф. Сведение задачи к переменным и решение.
курсовая работа [784,0 K], добавлен 21.05.2015Разработка и тестирование программы на языке Pascal для поиска, вывода на экран и сохранения в файл списка книг с фамилиями авторов в алфавитном порядке, изданных после 2012 года. Разработка алгоритма и его описание. Инструкции по эксплуатации приложения.
курсовая работа [903,0 K], добавлен 13.06.2013
