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

Размещено на 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

...