Дискретная математика. Лабораторная работа № 3. Вариант №18. СибГУТИ
Состав работы
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Работа представляет собой zip архив с файлами (распаковать онлайн), которые открываются в программах:
- Программа для просмотра текстовых файлов
- Microsoft Word
Описание
(Разделение на варианты не предусмотрено)
Генерация перестановок
Дано конечное множество A. Требуется сгенерировать все возможные перестановки его элементов в лексикографическом порядке (по материалам главы 1, п. 1.3.6, и главы 2, п. 2.2.1). Требования к заданию множества – в нем не должно быть повторяющихся элементов, кроме того, удобнее использовать или только буквы, или только цифры.
Программа должна сначала упорядочить все элементы заданного множества по возрастанию (это первый – минимальный – набор), затем – посредством МИНИМАЛЬНО ВОЗМОЖНЫХ ПЕРЕСТАНОВОК! – сгенерировать последовательно возрастающие (лексикографически) наборы, вплоть до последнего, в котором все элементы упорядочены по убыванию.
Следует оценивать количество возможных перестановок и в случае, если они не поместятся на экран, выполнять их вывод в файл с выдачей на экран соответствующей информации для пользователя и выполнять поэкранный вывод с ожиданием нажатия клавиши.
Дополнительно: Предоставить пользователю возможность выбора другого варианта работы программы, в котором за исходную точку упорядочивания наборов выбирается не минимальный набор, а набор в таком порядке, как он задан пользователем.
Возможный алгоритм решения (Пример: множество А={1, 2, 3, 4, 5, 6}, |A| = n):
Предположим, что уже построено m наборов. Тогда для получения m+1-го набора:
1) Выполняется проверка последнего (m-го) набора на наличие в его конце некоторого количества символов, упорядоченных по убыванию – пусть это символы ak+1…an.
<3 5 2 6 4 1> – k=3, символы с 4-го по 6-й упорядочены по убыванию.
2) Если такое k найдено, то поменять местами k-й элемент и наименьший элемент из ak+1…an, больший этого ak.
В нашем примере это 2 и 4: <3 5 4 6 2 1> (это промежуточный набор).
3) После шага 2 упорядочить элементы с k+1-го до последнего по возрастанию. Получен очередной набор => выдать его на печать.
<3 5 4 1 2 6>.
4) Если на шаге 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>.
5) Если полученный набор не последний (упорядоченный по убыванию), то возврат на шаг 1. В противном случае конец работы.
Генерация перестановок
Дано конечное множество A. Требуется сгенерировать все возможные перестановки его элементов в лексикографическом порядке (по материалам главы 1, п. 1.3.6, и главы 2, п. 2.2.1). Требования к заданию множества – в нем не должно быть повторяющихся элементов, кроме того, удобнее использовать или только буквы, или только цифры.
Программа должна сначала упорядочить все элементы заданного множества по возрастанию (это первый – минимальный – набор), затем – посредством МИНИМАЛЬНО ВОЗМОЖНЫХ ПЕРЕСТАНОВОК! – сгенерировать последовательно возрастающие (лексикографически) наборы, вплоть до последнего, в котором все элементы упорядочены по убыванию.
Следует оценивать количество возможных перестановок и в случае, если они не поместятся на экран, выполнять их вывод в файл с выдачей на экран соответствующей информации для пользователя и выполнять поэкранный вывод с ожиданием нажатия клавиши.
Дополнительно: Предоставить пользователю возможность выбора другого варианта работы программы, в котором за исходную точку упорядочивания наборов выбирается не минимальный набор, а набор в таком порядке, как он задан пользователем.
Возможный алгоритм решения (Пример: множество А={1, 2, 3, 4, 5, 6}, |A| = n):
Предположим, что уже построено m наборов. Тогда для получения m+1-го набора:
1) Выполняется проверка последнего (m-го) набора на наличие в его конце некоторого количества символов, упорядоченных по убыванию – пусть это символы ak+1…an.
<3 5 2 6 4 1> – k=3, символы с 4-го по 6-й упорядочены по убыванию.
2) Если такое k найдено, то поменять местами k-й элемент и наименьший элемент из ak+1…an, больший этого ak.
В нашем примере это 2 и 4: <3 5 4 6 2 1> (это промежуточный набор).
3) После шага 2 упорядочить элементы с k+1-го до последнего по возрастанию. Получен очередной набор => выдать его на печать.
<3 5 4 1 2 6>.
4) Если на шаге 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>.
5) Если полученный набор не последний (упорядоченный по убыванию), то возврат на шаг 1. В противном случае конец работы.
Дополнительная информация
Программа написана самостоятельно и не содержит багов (полностью отлаженный и работающий вариант). Отчёт о проделанной работе содержит подробную информацию о ходе написания программы, её тестирования и работы. Также отчёт снабжен гиперссылками.
Уважаемый слушатель, дистанционного обучения,
Оценена Ваша работа по предмету: Дискретная математика
Вид работы: Лабораторная работа 3
Оценка:Зачет
Дата оценки: 05.02.2013
Рецензия:Уважаемая +++++++++++++,
Бах Ольга Анатольевна
Уважаемый слушатель, дистанционного обучения,
Оценена Ваша работа по предмету: Дискретная математика
Вид работы: Лабораторная работа 3
Оценка:Зачет
Дата оценки: 05.02.2013
Рецензия:Уважаемая +++++++++++++,
Бах Ольга Анатольевна
Похожие материалы
Лабораторная работа №3. Дискретная математика. (СибГУТИ)
Lost
: 15 февраля 2012
Генерация перестановок
Дано конечное множество A. Требуется сгенерировать все возможные перестановки его элементов в лексикографическом порядке (по материалам главы 1, п. 1.3.6, и главы 2, п. 2.2.1). Требования к заданию множества – в нем не должно быть повторяющихся элементов, кроме того, удобнее использовать или только буквы, или только цифры.
Программа должна сначала упорядочить все элементы заданного множества по возрастанию (это первый – минимальный – набор), затем – посредством МИНИМАЛЬНО
70 руб.
Дискретная математика. Контрольная работа. Вариант 18. СибГУТИ
Shamrock
: 2 февраля 2015
No1 Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна. а) A\\ ((AB)\\C) = (A\\B) (A C)
б) U2 \\ (C D) = (U (U\\D)) ((U\\C) U).
No2 Даны два конечных множества: А={a,b,c}, B={1,2,3,4}; бинарные отношения P1 A B, P2 B2. Изобразить P1, P2 графически. Найти P = (P2P1)–1. Выписать области определения и области значений всех трех отношений: P1, P2, Р. Построить матрицу [P2], проверить с ее помощью, являет
250 руб.
Дискретная математика. Лабораторная работа № 1. Вариант 18. СибГУТИ
Shamrock
: 2 февраля 2015
(Деление на варианты не предусмотрено)
Множества и операции над ними
Задание:
Написать программу, в которой для конечных упорядоченных множеств реализовать все основные операции с помощью алгоритма типа слияния (по материалам главы 1, п.1.2). Допустима организация множеств в виде списка или в виде массива.
Работа программы должна происходить следующим образом:
1. На вход подаются два упорядоченных множества A и B (вводятся с клавиатуры, элементы множеств – буквы латинского алфавита).
2. После вв
220 руб.
Дискретная математика. Лабораторная работа № 5. Вариант №18. СибГУТИ
Shamrock
: 2 февраля 2015
(Разбиение на варианты не предусмотрено)
Поиск компонент связности графа
Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа (по материалам главы 3, п. 3.2.3 и 3.4). При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода (поиск в глубину или поиск в ширину по материалам п. 3.4.3).
Пользователю
220 руб.
Дискретная математика. Лабораторная работа № 4. Вариант №18. СибГУТИ
Shamrock
: 2 февраля 2015
(Разделение на варианты не предусмотрено)
Генерация подмножеств
Задано целое положительное число n, которое представляет собой мощность некоторого множества. Требуется с минимальными трудозатратами генерировать все подмножества этого множества, для чего каждое последующее подмножество должно получаться из предыдущего путем добавления или удаления только одного элемента. Множество и все его подмножества представляются битовой шкалой. Для генерации использовать алгоритм построения бинарного кода Г
220 руб.
Дискретная математика. Лабораторная работа № 2. Вариант 18. СибГУТИ
Shamrock
: 2 февраля 2015
Отношения и их свойства
Бинарное отношение R на конечном множестве A: R принадлежит A2 – задано списком упорядоченных пар вида (a,b), где a,b принадлежат A. Требования на множество – те же, что и раньше (в нем не должно встречаться повторяющихся элементов, кроме того, оно должно быть упорядочено по возрастанию). Программа должна определять свойства заданного отношения: рефлексивность, симметричность, антисимметричность, транзитивность (по материалам главы 1, п.1.3). Проверку свойств выполнять по
220 руб.
Лабораторные работы № 1-3. Дискретная математика. (СибГУТИ)
Lost
: 15 февраля 2012
Работа 1.
Множества и операции над ними
Написать программу, в которой для конечных упорядоченных множеств реализовать все основные операции с помощью алгоритма типа слияния (по материалам главы 1, п.1.2). Допустима организация множеств в виде списка или в виде массива.
Работа программы должна происходить следующим образом:
1. На вход подаются два упорядоченных множества A и B (вводятся с клавиатуры, элементы множеств – буквы латинского алфавита).
2. После ввода множеств выбирается требуемая опе
150 руб.
СИБГУТИ, Дискретная математика
fred_student
: 2 октября 2014
В данном сборнике решения следующих лабораторных работ:
1. Множества и операции над ними
2. Отношения и их свойства
3. Генерация перестановок
4. Генерация подмножеств
5. Поиск компонент связности графа
Все работы написаны на языке Pascal.
500 руб.
Другие работы
Особенности современных мироторговых связей
Slolka
: 28 октября 2013
Структура и динамика международной торговли. Формирование и особенности мирового рынка товаров и услуг.
Обычно систему международной торговли понимают как сферу товарного обмена между странами на базе международного разделения труда. Такая трактовка международной торговли отражает лишь международный уровень товарных потоков, обусловленный межстрановым разделением труда, на котором происходит торговля традиционными товарами. Международная торговля базируется, однако, не только на международном ра
10 руб.
Базы данных. Вариант №3
IT-STUDHELP
: 24 ноября 2021
1 Предметная область
База данных «Хроники восхождений» в альпинистском клубе. В базе данных должны записываться даты начала и завершения каждого восхождения, имена и адреса участвовавших в нем альпинистов, название и высота горы, страна и район, где эта гора расположена. Написать запросы, осуществляющие следующие операции:
1) Для введенного пользователем интервала дат показать список гор с указанием даты последнего восхождения. Для каждой горы сформировать в хронологическом порядке список груп
1000 руб.
Оптические мультисервисные сети. Лабораторная № 1,2. Вариант №6
ElenaA
: 2 марта 2018
Лабораторная работа № 1:
Цель работы: Изучение технологии пассивных оптических сетей.
Лабораторная работа № 2:
Цель работы: Изучение характеристик технологии GFP, структуры кадра GFP, управления GFP.
130 руб.
Лабораторная работа №1 по дисциплине «Структуры и алгоритмы обработки данных (часть 2-я)»
boeobq
: 17 ноября 2021
Идеально сбалансированное дерево поиска (ИСДП) и случайное дерево поиска (СДП)
Задание:
1. Написать подпрограммы для вычисления характеристик двоичного дерева, которые определяют:
o размер дерева;
o высоту дерева;
o среднюю высоту дерева;
o контрольную сумму данных в вершинах дерева;
o Проверить их работу на конкретном примере.
2. Запрограммировать обход двоичного дерева слева направо и вывести на экран получившуюся последовательность данных.
3. Разработать подпрограмму поиска вершины с зада
60 руб.