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

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

Кафера вычислительной техники

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

по курсу:

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

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

Выполнил Давыдов Д.Ю.

Студент группы 16ВВ3

Руководитель д.т.н.

профессор Малютина Г.И.

Пенза 2017

Содержание

• Введение
• 1. Постановка задачи
• 2. Теоретическая часть задания
• 3. Описание алгоритма решения поставленной задачи
• 4. Пример ручного расчета задачи и вычислений
• 5. Описание программы
• 6. Тесты
• Заключение
• Список литературы
• Приложения

Введение

Множество -- одно из основных понятий современной математики, «произвольная совокупность определенных и различимых объектов, объединенных мысленно в единое целое». Так определял множество основатель теории множеств, известный немецкий математик Георг Кантор. Правда, уже в начале XX в. стало ясно, что определение Кантора нельзя считать достаточно строгим, так как оно приводит к различным логическим противоречиям. Широко распространено убеждение, что Множество -- понятие, поясняемое только на примерах. Такая странная для математики ситуация объясняется отчасти тем, что все попытки определить термин Множество приводят, по существу, к замене его другими, столь же неопределенными понятиями).

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

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

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

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

В программе необходимо реализовать также дополнительные вспомогательные функции, упрощающие ввод или изменение уже введённых данных. Программа разрабатывается для семейства операционных систем на базе архитектуры Windows NT. Программа будет написана на языке С# в среде программирования Microsoft Visual Studio 2017.

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

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

Лексикографический порядок -- отношение линейного порядка на множестве слов над некоторым упорядоченным алфавитом ?. Своё название лексикографический порядок получил по аналогии с сортировкой по алфавиту в словаре. Лексикографический порядок последовательностей предполагает, что последовательность А предшествует последовательности B, если для некоторого S их начальные отрезки длины S равны, а S+1-ый член последовательности A меньше.

Иными словами, элементы в последовательности выстраиваются «по старшинству». Например, 123, 132, 213. 123 имеет меньший вес, чем 132, так как 2 предшествует 3.

Рассмотрим алгоритм нахождения таких перестановок. Начиная с перестановки (1,2,…,n), переход от текущей перестановки P=(p1,p2,…,pn) к перестановке, следующей за текущей в смысле лексикографического порядка, осуществляется последовательным выполнением следующих действий:

1. Просмотр Р справа налево в поисках самой правой позиции k, в которой pk<pk+1 (если такой позиции k нет, то текущая перестановка является последней и следует закончить генерацию);

2. Просмотр P от pk слева направо в поисках наименьшего из таких элементов pm, что k<m и pk<pm;

3. Транспозиция элементов pk и pm и обращение отрезка pk+1,…, pn путем транспозиции симметрично расположенных элементов (заметим, что элементы обращаемого отрезка расположены в порядке убывания).

3. Описание алгоритма решения поставленной задачи

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

Для реализации пользовательского интерфейса использовалась среда разработки Microsoft Visual 2017 и платформа .NetFramework 4.6.1. С помощью конструктора .NetFramework было создано рабочее окно программы, включающее в себя такие интерактивные элементы как кнопки для запуска функций и «текстбоксы» для отображения текстовой информации.

Затем была написана функция read_array(). Эта функция считывает данные введение пользователем. Затем осуществляется проверка корректности введённых данных. В случае если введена пустая строка, то программа уведомит пользователя о необходимости ввести множество в строку ввода. Программа написана таким образом, что обрабатывает широкий спектр разделители между элементами множества. В случае, если множество было введено корректно, то функции формирует массив, состоящий из введённых пользователем элементов. На рисунке 1 представлена блок схема данной функции.

Затем будет вызвана функция Rearrangement, которая непосредственно проверяет сортировку введённого множества. Функция ищет элемент в множестве P, который удовлетворяет условию pk<pk+1, то есть меньше предыдущего. Затем ищем элемент, который стоит выше позиции и больше искомого pk. После этого она меняет местами найденные элементы и инвертирует оставшуюся часть множества. Количество таких операций, равно факториалу длины введённого множества. На рисунке 2 представлена блок схема данной функции.

Так же в программе реализованы вспомогательные функции, которые либо осуществляют дополнительные расчёты, либо взаимодействуют с интерфейсом для облегчения работы пользователя с программой. В данной программе таковыми функциями являются factorial(),clear_all_fields() и clear_out. Действия, которые выполняет данные функции описаны в таблице 1:

Таблица 1

Список вспомогательных функции и их описание

Блок схемы данных функций представлены на рисунке 3.

Рисунок 1 - Блок схема функции read_array()

Рисунок 2 - Блок-схемы функции factorial(x) clear_all_fields() clear_out(); array_out

Рисунок 3 - Блок схема функции Rearrangement ()

4. Пример ручного расчета задачи и вычислений

Для примера приведем перестановки множества X = {1,2,3} в лексикографическом порядке (см. таблицу 2):

программный комбинаторика множество лексикографический

Таблица 2

Ручной расчёт перестановок множества в лексикографическом порядке

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

При запуска программы откроется основной интерфейс программы, содержащий кнопки ввода и элементы вывода - «текстбоксы» (см. рисунок 4).

Рисунок 4 - Интерфейс программы

В верхнее текстовое поле пользователь вводит свою числовую последовательность. После нажатия на кнопку «Рассчитать простановки», программа считает строку, сгенерирует простановки и отобразит их снизу в лексикографическом порядке. Также в поле для ввода, справа отобразиться общее число перестановок. (рис. 5)

Рисунок 5 - Интерфейс программы, после генерации перестановок

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

Рисунок 6 - Интерфейс программы, после нажатия кнопки «Очистить поля»

При нажатии на кнопку очистить окно вывода программа очистит только окно со сгенерированными перестановками. (рис. 7)

Рисунок 7 - Интерфейс программы, после нажатия кнопки «Очистить окно вывода»

6. Тесты

Отладка производилась в среде Microsoft Visual Studio 2017. С помощью точек остановок, а также контрольных значениях глобальных и локальных переменных удалось исправить множество ошибок, связанных с неверным считыванием строки или генерацией перестановок.

Были добавлены условия на проверку строки на «Пустоту» или некорректные символы. Тогда программа выдаст пользователю сообщение о некорректном вводе. (рис. 8)

Рисунок 8 - Примеры неверно введенных данных

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

Заключение

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

Улучшены навыки работы с программной платформой .NET Framework, а также получены новые знания и умения по разработке прикладного ПО на языке программирования С#.

Список литературы

1. C# 5.0 и платформа .NET 4.5. Нейгел К., Ивьен Б., Глинн Д., Уотсон К., Скиннер М. Издательство Диалектика - 2014 год.

2. Справочник MSDN. Официальная онлайн документация C#; MSDN - Статья «Класс TextBox».

3. Перестановки; Е.А. Максименко ж. §1. Определение перестановки Эксмо - 2007 г.

Приложение А

Листинги программы

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace CourseWorkGraph

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

textBox2.ScrollBars = ScrollBars.Vertical;

}

int n,k,m,x,y;

string soure_scores;

string[] sorce_str;

int Length = 0;

private void Form1_Load(object sender, EventArgs e)

{

}

List<int> scores = new List<int>();

private int factorial(int x)

{

int temp=1;

for (int i = 1; i <= x; i++)

temp *= i;

return temp;

}

private void read_array(object sender, EventArgs e)

{

try

{

if (textBox1.Text == "")

textBox1.Text = "Введите множество чисел";

else

soure_scores = textBox1.Text;

sorce_str = soure_scores.Split(new string[] { " ", ",", ".", ";", "|", "/", "\\", "*"

}, StringSplitOptions.RemoveEmptyEntries);

for (int x = 0; x < sorce_str.Length; x++)

scores.Add(int.Parse(sorce_str[x]));

scores.Sort();

Rearrangement();

}

catch { MessageBox.Show("Введены не поддерживаемые символы",

"Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Exclamation,

MessageBoxDefaultButton.Button1); }

}

private void Rearrangement()

{

k = sorce_str.Length - 1;

n = factorial(sorce_str.Length);

Length = sorce_str.Length;

string[] Final_Mass = new string[n];

for (int i = 0; i < sorce_str.Length; i++)

Final_Mass[0] = Final_Mass[0] + scores[i];

textBox3.Text =" "+Convert.ToString(n);

for (;n != 0; n--)

{

k = sorce_str.Length - 1;

while ((scores[k - 1] >= scores[k]))

{

k--;

if (k <= 0)

break;

}

if (k <= 0)

break;

k--;

m = k + 1;

y = m;

x = scores[m];

while (m != sorce_str.Length)

{

if ((scores[k] < scores[m]) && (scores[m] < x))

{

x = scores[m];

y = m;

}

m++;

}

scores[y] = scores[k];

scores[k] = x;

x = (sorce_str.Length - 1 - k);

m = sorce_str.Length - 1;

while (x / 2 != 0)

{

y = scores[k + 1];

scores[k + 1] = scores[m];

scores[m] = y;

k++;

m--;

x = x - 2;

}

for (int i = 0; i < sorce_str.Length; i++)

{

Final_Mass[n-1] = (Final_Mass[n-1] + scores[i]);

}

}

Array.Sort(Final_Mass);

array_out(Final_Mass);

}

private void clear_all_fields(object sender, EventArgs e)

{

textBox1.Text = "";

textBox2.Text = "";

textBox3.Text = "";

Array.Clear(sorce_str,0,sorce_str.Length);

scores.Clear();

}

private void clear_out(object sender, EventArgs e)

{

textBox2.Text = "";

Array.Clear(sorce_str, 0, sorce_str.Length);

scores.Clear();

}

private void array_out(string[] Final_Mass)

{

for (int i = 0; i < Final_Mass.Length; i++)

textBox2.Text = textBox2.Text + "|"+Final_Mass[i] + "|"+"\r\n";

}

}

}

Приложение Б

Описание работы программы

При вводе следующих данных: 123 программа выведет следующий результат (см. рисунок 9).

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