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

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 20.02.2019
Размер файла 143,4 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

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

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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проектированию

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

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

Выполнил: студент группы 16ВВ 2

Шамрай А.С.

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

Пащенко Д.В.

Пенза, 2017

Содержание

    • Введение
    • 1. Постановка задачи
    • 2. Выбор решения
    • 2.1 Определение необходимых модулей программы
    • 2.2 Определение структуры файла базы данных
    • 3. Описание разработки программы
    • 4. Отладка и тестирование
    • 5. Описание программы
    • Заключение
    • Список используемых источников
    • Приложение А. Листинг программы
    • Приложение B. Результат работы программы

Введение

В настоящее время невозможно представить инженера, не обращающегося в своей работе к ЭВМ. Диапазон их общения определяется наличием прикладных программных средств, позволяющих пользователю решать нужные инженерные и научные задачи. При этом он должен и уметь пользоваться ранее созданными программами и участвовать в разработке нового программного обеспечения. Пользователь-инженер, включенный в коллектив разработчиков задачи для ее решения на ЭВМ, а, тем более, выполняющий эту работу лично, должен уметь "общаться" с алгоритмами. Разработка новой задачи всегда начинается с оценки возможности использования уже созданных программ. При такой оценке необходимо понять суть алгоритма рассматриваемой программы. Если он полностью удовлетворяет пользователя, то можно остановиться на этой программе. Если же этот алгоритм отличается от предлагаемого разработчиками, то следует рассмотреть возможность доработки анализируемой программы. И только в тех случаях, когда такую доработку выполнить невозможно или для новой задачи не удается найти ранее созданных аналогов, возникает необходимость ее полной разработки, включая написание новой программы.

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

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

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

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

На вход программа должна принимать целое число n - количество цифр в множестве (от 1 до n, с шагом равным единице).

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

Использование сложных типов данных. Использовать в программе такие сложные типы данных, как массивы.

Режим работы видеосистемы. Необходимо определить тип видеосистемы: текстовый или графический.

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

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

2. Выбор решения

2.1 Определение необходимых модулей программы

Разработанная программа состоит из 4 модулей:

1. Файл NextSet.cpp

2. Файл Print.cpp

3. Файл Swap.cpp

4. Файл Source.cpp

В файле NextSet.cpp реализуется алгоритм генерации следующей последовательности по следующим правилам:

1. Просматривается текущая перестановка справа налево. Если следующий элемент перестановки (элемент с большим номером) больше, чем предыдущий (элемент с меньшим номером) алгоритм останавливается и запоминается номер предыдущего элемента (элемента с меньшим номером).

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

3. Вся последовательность, которая идет справа от запомненного элемента на 2 шаге, сортируется по возрастанию.

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

Файл Print.cpp предоставляет возможность вывести результаты работы алгоритма на экран.

Файл Swap.cpp осуществляет перестановку между двумя переменными. Также данная функция используется для выполнения 3-го пункта алгоритма, сортировки.

Файл Source.cpp является главным связующим звеном всех выше описанных функций.

2.2 Определение структуры файла базы данных

Для структурирования всех чисел множества был выбран динамический массив целочисленных данных.

a = new int[n];

В программе, осуществляется следующая работа с данными:

1. Ввод данных

2. Сортировка данных

3. Вывод данных

3. Описание разработки программы

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

Синтаксис C++ унаследован от языка C. Одним из принципов разработки было сохранение совместимости с C. Тем не менее, C++ не является в строгом смысле надмножеством C; множество программ, которые могут одинаково успешно транслироваться как компиляторами C, так и компиляторами C++, довольно велико, но не включает все возможные программы на C.

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

Разработка программы началась с реализации набора функций, необходимых для основной работы c последовательностью. Для создания новой последовательности была использована функция NextSet().

Для сортировки данных была разработана функция Swap(). Данная функция осуществляет обмен двух переменных местами.

Для вывода каждой последовательности была создана функция Print().

Схема работы файла главного файла Source.cpp программы представлена на рисунке 3.

Рисунок 3- Схема программы. Функция обработки событий главного окна

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

алгоритм файл генерирование

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

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

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

Для написания программы была использована OC Windows и среда разработки Microsoft Visual Studio. Программа написана на языке C++. Работа с программой осуществляется через консоль. Для работы с программой пользователю предлагается самостоятельно ввести данные о количестве чисел последовательности, а также пользователь должен ввести эти числа.

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

Заключение

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

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

1. Керниган Б. Ритчи Д., Язык программирования C. 2009г.

2. Б. Страуструп, Программирование: принципы и практика использования C++. 2010г.

3. С. Прата, Язык программирования C. 2013г.

4. В.Г. Давыдов, Программирование и основы алгоритмизации. 2003г.

5. MSDN.

Приложение А. Листинг программы

A.1 - Файл NextSet.cpp

#include "Header.h"

bool NextSet(int *a, int n) {

int j = n - 2;

while (j != -1 && a[j] >= a[j + 1])

{

j--;

}

if (j == -1)

{

return false; // больше перестановок нет

}

int k = n - 1;

while (a[j] >= a[k])

{

k--;

}

Swap(a, j, k);

int l = j + 1,

r = n - 1; // сортируем оставшуюся часть последовательности

while (l < r)

{

Swap(a, l++, r--);

}

return true;

}

A.2 - файл Print.cpp

#include "Header.h"

#include <iostream>

using namespace std;

void Print(int *a, int n) { // вывод перестановки

static int num = 1; // номер перестановки

//cout.width(3); // ширина поля вывода номера перестановки

cout " num++ " ": ";

for (int i = 0; i < n; i++)

cout " a[i] " " ";

cout " endl;

}

A.3 - файл Swap.cpp

#include "Header.h"

void Swap(int *a, int i, int j) {

int s = a[i];

a[i] = a[j];

a[j] = s;

}

A.4 - файл Source.cpp

#include <iostream>

#include <conio.h>

#include "Header.h"

#include <locale.h>

using namespace std;

int main() {

setlocale(LC_ALL, "Russian");

int n, *a;

cout " "Введите количество чисел множества N = ";

cin " n;//Количество чисел в множестве

a = new int[n];

for (int i = 0; i < n; i++)

{

cout " "Введите элемент последовательности: ";

cin " a[i];

}

Print(a, n);

while (NextSet(a, n))

{

Print(a, n);

}

getch();

return 0;

}

A.5 - файл Header.h

#pragma once

void Swap(int *a, int i, int j);

bool NextSet(int *a, int n);

void Print(int *a, int n);

Приложение B. Результат работы программы

Ниже, на рисунке представлен результат для множества из 3-х чисел

Рисунок 4 - Результат работы программы для множества из 3-х чисел

А также, для множества из 4-х чисел

Рисунок 5 - Результат работы программы для множества из 4-х чисел

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

...

Подобные документы

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

    реферат [22,4 K], добавлен 07.03.2010

  • Определение необходимых модулей программы, структуры файла базы данных. Описание разработки программы, отладка и тестирование. Разработка приложения Organizer.exe, меню и руководство пользователя. Алгоритм обработки событий главного меню (расписания).

    курсовая работа [901,8 K], добавлен 11.02.2014

  • Словесное описание алгоритма программы. Открытие файла процедурой Rewrite, его проверка на наличие ошибок при открытии. Особенности построения диаграммы. Листинг программы, ее тестирование и отладка. Выполнение процедуры CloseFile при закрытии файла.

    контрольная работа [17,3 K], добавлен 11.06.2010

  • Постановка задачи. Математическое обоснование. Последовательность разбиений множества. Язык программирования. Реализация алгоритмов. Генерирование разбиений множества. Генерирование всех понятий.

    курсовая работа [29,9 K], добавлен 20.06.2003

  • Сортировка как процесс перегруппировки заданного множества объектов в некотором определенном порядке, основные этапы данного процесса. Способы формирования начальных отрезков. Описание структуры программы. Результаты испытаний, их исследование и анализ.

    курсовая работа [111,6 K], добавлен 31.01.2014

  • Решение задач по информатике, перебор различных комбинаторных конфигураций объектов и выбор наилучшего, с точки зрения условия задачи. Генерация k-элементных подмножеств, всех подмножеств данного множества, всех перестановок n-элементного множества.

    реферат [44,0 K], добавлен 03.01.2010

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

    курсовая работа [494,5 K], добавлен 20.06.2012

  • Линейные динамические структуры. Построение списочной структуры, состоящей из трехнаправленного и двух однонаправленных списков, связанных между собой. Дерево двоичного поиска для заданного множества целых чисел. Листинг программы на языках Си и Паскаль.

    курсовая работа [451,1 K], добавлен 19.10.2013

  • Программный комплекс по обработке заданного множества данных в динамической памяти компьютера. Запросы к массиву записей множества данных – групп в детском саду. Функция сортировки массива по числовому полю. Использование главной программы MAINPRO.

    курсовая работа [419,3 K], добавлен 23.07.2014

  • Сравнительный анализ языков программирования высокого уровня Си и Паскаль. Реализация алгоритма обработки данных. Тестирование и отладка программы или пакета программ. Структура программы на языке Турбо Паскаль. Указатели и векторные типы данных.

    курсовая работа [233,5 K], добавлен 14.12.2012

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

    курсовая работа [3,5 M], добавлен 22.06.2012

  • Содержательная и формальная (математическая) постановка задачи. Разработка алгоритма решения задачи. Структуры программы и алгоритмы программных модулей, их описание. Решение задачи на конкретном примере. Разработка системы тестов и отладка программы.

    курсовая работа [882,1 K], добавлен 24.11.2014

  • Создание на языке C базы данных "Стадионы города", требования к программе. Осуществление загрузки базы данных в массив и вывод главного меню в основной программе. Алгоритм работы программы в виде блок-схемы. Описание функций программы и ее листинг.

    курсовая работа [183,6 K], добавлен 06.10.2010

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

    курсовая работа [3,3 M], добавлен 28.04.2014

  • Характеристика алгоритмов и программных реализаций поведения агентов в двумерной среде. Исследование разработки структур данных и знаний. Особенность создания интерфейса и карты лабиринта. Экспериментальное тестирование и отладка модулей программы.

    дипломная работа [2,4 M], добавлен 12.08.2017

  • Разработка информационной программы для риэлтерской конторы по учету клиентской базы и базы квартир с фиксированием всех операций по купле-продаже. Описание структуры базы данных. Создание запросов и отчетов. Инструкция по эксплуатации, текст программы.

    курсовая работа [2,4 M], добавлен 07.09.2012

  • Особенности разработки программы и выбор методов решения задачи. Составление алгоритма, распределение регистров программы и формирование файлов. Описание процедуры очистки памяти, сложения, вычитания, умножения. Тестирование и листинг программы.

    лабораторная работа [51,2 K], добавлен 14.05.2011

  • Вычислительная система: программные и технические средства. Алгоритм задачи: вызов и загрузка, интерфейс пользователя, система помощи, логическая и физическая структуры. Описание программы и ее элементов, сферы ее применения, тестирование и отладка.

    курсовая работа [5,4 M], добавлен 24.07.2012

  • Использование класса статических массивов структур и базы данных "ODER" при создании программы на языке С++. Основные формы выдачи результатов. Технические и программные средства. Тесты для проверки работоспособности алгоритма создания программы.

    курсовая работа [1,1 M], добавлен 17.03.2015

  • Основные структуры в языке С. Обращение к элементам структуры. Типичные ошибки при разработке структуры. Алгоритм определения продолжительности полета. Описание функции int fflush. Алгоритм работы файла run.cpp. Листинг разрабатываемой программы.

    курсовая работа [990,9 K], добавлен 16.02.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.