| engineerklub | Дата: Среда, 03.01.2018, 11:33 | Сообщение # 1 |
 Генералиссимус
Группа: Администраторы
Сообщений: 29399
Статус: Offline
| Дискретная математика. Лабораторная работа №3. Все варианты
Тип работы: Работа Лабораторная
Форматы файлов: Microsoft Word
Сдано в учебном заведении: СибГУТИ
Описание:
Лабораторная работа № 3 Генерация перестановок
Дано конечное множество A. Требуется сгенерировать все возможные перестановки его элементов в лексикографическом порядке (по материалам главы 1, п. 1.3.6, и главы 2, п. 2.2.1). Требования к заданию множества – в нем не должно быть повторяющихся элементов, кроме того, удобнее использовать или только буквы, или только цифры.
Программа должна сначала упорядочить все элементы заданного множества по возрастанию (это первый – минимальный – набор), затем – посредством МИНИМАЛЬНО ВОЗМОЖНЫХ ПЕРЕСТАНОВОК! – сгенерировать последовательно возрастающие (лексикографически) наборы, вплоть до последнего, в котором все элементы упорядочены по убыванию.
Следует оценивать количество возможных перестановок и в случае, если они не поместятся на экран, выполнять их вывод в файл с выдачей на экран соответствующей информации для пользователя и выполнять поэкранный вывод с ожиданием нажатия клавиши.
Дополнительно: Предоставить пользователю возможность выбора другого варианта работы программы, в котором за исходную точку упорядочивания наборов выбирается не минимальный набор, а набор в таком порядке, как он задан пользователем.
Возможный алгоритм решения (Пример: множество А={1, 2, 3, 4, 5, 6}, |A| = n):
Предположим, что уже построено m наборов. Тогда для получения m+1-го набора:
Выполняется проверка последнего (m-го) набора на наличие в его конце некоторого количества символов, упорядоченных по убыванию – пусть это символы ak+1…an.
á 3 5 2 6 4 1ñ – k=3, символы с 4-го по 6-й упорядочены по убыванию.
Если такое k найдено, то поменять местами k-й элемент и наименьший элемент из ak+1…an, больший этого ak.
В нашем примере это 2 и 4: á 3 5 4 6 2 1ñ (это промежуточный набор).
После шага 2 упорядочить элементы с k+1-го до последнего по возрастанию. Получен очередной набор Þ выдать его на печать.
á 3 5 4 1 2 6ñ.
Если на шаге 1 ответ отрицательный, то поменять местами 2 последних элемента и выдать на печать полученный набор. В частности, после шага 3 это неизбежное действие, т.к. все последние элементы были размещены по возрастанию Þ целесообразно после выполнения ш.3 задавать признак его выполнения, который будет анализироваться (и сбрасываться) на шаге 1. После шага 3 было á 3 5 4 1 2 6ñ Þ выдать á 3 5 4 1 6 2ñ .
Если был набор á 3 5 2 6 1 4ñ Þ выдать á 3 5 2 6 4 1ñ .
Если полученный набор не последний (упорядоченный по убыванию), то возврат на шаг 1. В противном случае конец работы.
З.Ы. здесь на сайте не корректно отображаются основные операции, видимо проблемы с кодировкой
Комментарии: Уважаемый слушатель, дистанционного обучения,
Оценена Ваша работа по предмету: Дискретная математика
Вид работы: Лабораторная работа 3
Оценка:Зачет
Дата оценки: 11.01.2014
Рецензия:Уважаемый
Бах Ольга Анатольевна
СКАЧАТЬ МОЖНО ЗДЕСЬ
|
| |
| |
