Генерирование всех перестановок заданного множества
Упрощение задачи поиска экстремума целевой функции в его окрестностях. Сравнение алгоритмов перестановок в поиске наилучшего. Разработка, отладка и тестирование программ на языке С++. Изучение возможностей среды программирования Visual Studio 2017.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 22.02.2019 |
Размер файла | 434,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на 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
...Подобные документы
Решение задач по информатике, перебор различных комбинаторных конфигураций объектов и выбор наилучшего, с точки зрения условия задачи. Генерация k-элементных подмножеств, всех подмножеств данного множества, всех перестановок n-элементного множества.
реферат [44,0 K], добавлен 03.01.2010Постановка задачи. Математическое обоснование. Последовательность разбиений множества. Язык программирования. Реализация алгоритмов. Генерирование разбиений множества. Генерирование всех понятий.
курсовая работа [29,9 K], добавлен 20.06.2003Средства интегрированной среды Microsoft Visual Studio, предоставляемые программисту для реализации программ на языке С++. Особенности стиля написания программ. Типовые приемы и методы создания и отладки программ. Листинги программ и их тестирование.
лабораторная работа [814,3 K], добавлен 26.05.2013Особенности визуальной среды программирования Microsoft Visual Studio 2015 Enterprise. Средства объектно-ориентированного программирования. Этапы проектирования программного комплекса. Отладка и тестирование программы игры "Виселица".
курсовая работа [2,4 M], добавлен 31.01.2016Изучение принципов построения линейных алгоритмов и простых расчетных программ на языке программирования C. Разработка программы расчета математических выражений на основе вводимых данных. Создание консольных приложений в среде Microsoft Visual Studio.
лабораторная работа [254,4 K], добавлен 23.11.2014Изучение алгоритмов, написание программ на языке C#. Работа с массивами, строками, перечислениями, структурами, интерфейсами. Разработка и функциональность Windows-приложения. Создание и подключение баз данных в среде программирования Visual Studio 2019.
отчет по практике [6,7 M], добавлен 18.10.2020Изучение особенностей проектирования прикладных программ с помощь средств Visual Studio 2010 на языке C#. Расчет конического соединения, конусного градиента, усилия для разрыва соединения и требуемой силы сжатия. Реализация и тестирование программы.
курсовая работа [1,7 M], добавлен 19.02.2013Объектно-ориентированная технология создания программ. Среда разработки Visual Studio.NET. Особенности среды Microsoft Visual Studio 2010. Приложения C# для расчетов по формулам, консольный ввод-вывод. Форматирование значений данных. Программы с циклами.
методичка [2,1 M], добавлен 11.09.2014Описание программного продукта Visual Studio. Возможности, преимущества и недостатки бесплатной среды программирования Sharp Develop для проектов на платформе MS.NET. Получение информации из справочной системы .NET SDK. Запуск визуального отладчика CLR.
реферат [393,4 K], добавлен 05.04.2017Общие сведения о работе программы в среде программирования Microsoft Visual Studio 2008, на языке программирования C++. Ее функциональное назначение. Инсталляция и выполнение программы. Разработанные меню и интерфейсы. Алгоритм программного обеспечения.
курсовая работа [585,5 K], добавлен 24.03.2009Обоснование выбора средства программирования. Входная и выходная информация. Основные требования к программному и аппаратному обеспечению. Анализ метода поиска в строке по алгоритму Боуера-Мура. Глобальные переменные и константы в среде Visual Studio.
курсовая работа [489,0 K], добавлен 01.07.2015Основные этапы определения радиуса и центра окружности, проходящей через три различные точки заданного множества точек. Особенности построения алгоритма на языке программирования. Составление тестовых примеров для демонстрации возможностей программы.
контрольная работа [103,9 K], добавлен 21.08.2013Выбор наиболее эффективного метода поиска экстремума для функции. Оценка погрешности определения точки минимума. Проверка унимодальности уравнения аналитическим методом и по графику. Сравнение алгоритмов по количеству обращений к функции и по точности.
контрольная работа [909,0 K], добавлен 14.08.2019Приемы работы с инструментальной средой программирования С++. Кодирование арифметических и логических выражений с использованием стандартных библиотечных функций ввода, вывода в С++. Описание переменной вещественного типа в языке программирования С++.
лабораторная работа [137,9 K], добавлен 13.06.2014Понятие математического программирования. Класс как тип структуры, позволяющий включать в описание типа не только элементы данных, но и функции. Рассмотрение основных особенности языка программирования C++. Характеристика среды MS Visual Studio 2008.
контрольная работа [318,0 K], добавлен 13.01.2013Разработка учебного транслятора на языке программирования C# в среде объектно-ориентированного программирования Visual Studio 2012. Выделение лексем и построение цепочки символов на этапе синтаксического анализа. Функциональное тестирование программы.
курсовая работа [406,8 K], добавлен 07.08.2013Структурное программирование, схема алгоритма. Программа на языке Си для int, float. Подпрограмма ввода и вывода целых чисел на Ассемблере IBM. Тестирование и отладка, инструкция пользователя. Язык программирования Си (для int и float), этапы трансляции.
курсовая работа [1,5 M], добавлен 21.10.2014Изучение функций и возможностей среды разработки языка программирования Pascal. Рассмотрение работы с одномерными и двумерными массивами, со строками и числами. Математическая формулировка задач. Разработка алгоритмов, описание структуры программ.
курсовая работа [879,8 K], добавлен 11.02.2016Языки среды программирования Visual Studio. Стартовая страница интегрированной среды разработки. Окно New Project. Вкладка разработки формы. Перемещение и изменение размера кнопки. Прибавление программного кода к кнопке. Запуск и сохранение проекта.
презентация [1,4 M], добавлен 29.04.2014Требования к MS Office 2007. Набор средств разработки Visual Studio Tools for Office как альтернатива VBA. Разработка СУБД на базе MS Access. Разработка надстройки "Электронные компоненты" для PowerPoint на языке C# в среде MS Visual Studio 2010.
дипломная работа [5,2 M], добавлен 03.05.2013