Н.П. Трифонов, В.Н. Пильщиков - Практикум на ЭВМ, страница 3
Описание файла
Документ из архива "Н.П. Трифонов, В.Н. Пильщиков - Практикум на ЭВМ", который расположен в категории "". Всё это находится в предмете "практика расчётов на пэвм" из 1 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Н.П. Трифонов, В.Н. Пильщиков - Практикум на ЭВМ"
Текст 3 страницы из документа "Н.П. Трифонов, В.Н. Пильщиков - Практикум на ЭВМ"
Xi, Xi+k, Xi+2k, Xi+3k, ... (i=1, 2, ..., k)
Затем k уменьшается и процесс повторяется заново. Последний шаг обязательно должен быть выполнен при k=1.
Значение k можно менять разными способами, один из них таков: вначале k равно (целой части от) n/2, а затем k каждый раз уменьшается вдвое.
БЫСТРАЯ СОРТИРОВКА
Выбирается некоторый элемент (например, средний) и все элементы последо-вательности переставляются так, чтобы выбранный элемент оказался на своем окончательном месте, т.е. чтобы слева от него были только меньшие или равные ему элементы, а справа - только большие или равные. Затем этот же метод применяется к левой и правой частям последовательности, на которые ее разделил выбранный элемент. (Замечание: если в части оказалось два-три элемента, то упорядочивать ее следует более простым способом.)
Требуемая перестановка элементов выполняется так. Выбранный элемент копируется в некоторую переменную q. Последовательность просматривается слева направо, пока не встретится элемент, больший или равный q, а затем просматривается справа налево до элемента, меньшего или равного q. Оба этих элемента меняются местами, после чего просмотры с обоих концов последовательности продолжаются со следующих элементов, и т.д. В итоге выбранный элемент окажется в той позиции, где просмотры сошлись, это и есть его окончательное место.
Быструю сортировку можно реализовать рекурсивно и нерекурсивно. Во втором случае границы одной из двух частей (лучше - более длинной), на которые выбранный элемент разделил последовательность, запоминаются в стеке, а другая часть упо-рядочивается описанным способом. После ее упорядочения из стека извлекаются границы первой части, и теперь уже она упорядочивается.
СОРТИРОВКА СЛИЯНИЕМ
Основная идея такой сортировки - разделить последовательность на уже упорядоченные подпоследовательности (назовем их "отрезками") и затем объединять эти отрезки во все более длинные упорядоченные отрезки, пока не получится единая упорядоченная последовательность. Отметим, что при этом необходима дополнительная память (массив Y[1..n]).
Различаются следующие варианты сортировки слиянием.
а) ПРОСТОЕ СЛИЯНИЕ. Считается, что вначале отрезки состоят только из одного элемента, и они сливаются в отрезки из двух элементов (из X1 и X2, из X3 и X4, ...), которые переносятся в массив Y. На втором этапе соседние двухэлементные отрезки (Y1, Y2 и Y3, Y4; Y5, Y6 и Y7, Y8; ...) объединяются в отрезки из 4 элементов, которые записываются в массив X. На третьем этапе строятся отрезки из 8 элементов, и они заносятся в массив Y, и т.д.
б) ЕСТЕСТВЕННОЕ СЛИЯНИЕ. Берутся наиболее длинный (по неубыванию) отрезок в начале массива X и наиболее длинный (также по неубыванию, но при просмотре справа налево) отрезок в конце массива, и они сливаются в один отрезок, который записывается в начало массива Y. Затем сливаются следующие максимально длинные отрезки с обоих концов, и полученный отрезок записывается (справа налево) в конец массива Y. Третьи по порядку отрезки после слияния записываются снова в начало Y (вслед за первым объединенным отрезком), четвертые - в конец Y (перед вторым объединенным отрезком) и т.д. Первый этап сортировки оканчивается, когда все элементы из X будут перенесены в массив Y. На втором этапе применяется та же процедура, только массивы X и Y меняются ролями. И так далее.
Замечание: в обоих вариантах следует учитывать, что в конце концов упорядо-ченные элементы должны оказаться в массиве X.
ЗАДАНИЕ 4. ЯЗЫК ПАСКАЛЬ.
ИНТЕРФЕЙС ПРОГРАММЫ СОРТИРОВКИ.
ПОСТАНОВКА ЗАДАЧИ
Требуется дополнить программу сортировки, реализованную в задании 3, подсистемой диалогового взаимодействия с пользователем (интерфейсом), которая с помощью экранных окон, меню и других средств упрощает общение пользователя с этой программой. Работу с экраном подсистема должна осуществлять в текстовом режиме.
Объединенная система должна предусматривать следующие возможности.
- Пользователь должен иметь возможность выбрать из нескольких предъявленных ему методов сортировки тот метод, которым затем будут упорядочиваться последовательности.
- Пользователь должен иметь возможность задавать свою длину последователь-ностей, которые будут упорядочиваться выбранным методом.
- В системе должна быть предусмотрена возможность работы в двух режимах - отладки и счета. В режиме отладки пользователь сам вводит элементы (даты) последо-вательности, которая должна быть упорядочена, а в ответ система демонстрирует пошаговую работу процедуры сортировки для этой последовательности (это нужно для показа правильности работы процедуры). В режиме счета система должна работать так же, как и в задании 3: должна сформировать несколько последовательностей заданной длины, отсортировать их и вывести на экран таблицу результатов.
- Система должна позволять пользователю менять сделанный им ранее выбор (метода, длины или режима) и должна повторять свою работу при новом выборе.
- При вводе длины и элементов последовательности пользователь должен иметь возможность редактировать вводимую информацию.
ВОЗМОЖНЫЕ СЦЕНАРИИ РАБОТЫ С СИСТЕМОЙ
Ниже описаны два возможных сценария работы пользователя с системой. Любой из них можно взять за основу и со своими изменениями реализовать в задании.
Сценарий 1.
Этап 1. Выбор метода.
Работа системы начинается с очистки экрана и показа на нем списка названий различных (не менее 4-5) методов сортировки. Пользователь выбирает один из них либо прекращает работу с системой.
Этот список должен быть реализован в виде вертикального меню - в виде окна (закрашенного своим цветом прямоугольника), в котором друг под другом выписаны названия методов (см. рис. 1). Вначале должно быть выделено (высвечено особым цветом) первое из этих названий, а затем при нажатии пользователем клавиши со стрелкой вниз или вверх система должна выделить следующее или предыдущее (по кругу) название, сняв выделение текущего названия.
Одновременно с меню методов на экране (в его нижней строке) должен высвечиваться текст, подсказывающий пользователю, что он должен сейчас делать, какие клавиши может нажимать и что они означают. Подсказка может быть, например, такой:
ВЫБЕРИТЕ МЕТОД: ↓,↑–сдвиг Enter-выбор Esc-выход
Нажатие пользователем клавиши Enter означает, что он выбрал тот метод, название которого сейчас выделено. (Замечание: поскольку в системе реализовано лишь два метода сортировки, то при выборе нереализованного метода система должна как-то сообщить об этом, например звуковым сигналом или выдачей сообщения "Метод не реализован", и позволить пользователю выбрать иной метод. Желательно реализованные методы как-то пометить, например звездочкой.)
Нажатие клавиши Esc означает конец работы с системой.
На этом этапе система не должна реагировать на другие клавиши, а курсор должен быть невидимым.
Этап 2. Выбор режима.
После того как пользователь выбрал метод сортировки, система спрашивает его о режиме дальнейшей работы - режиме отладки или режиме счета. Пользователь выбирает нужный режим, но может и вернуться на предыдущий этап. В нижней строке экрана должна высвечиваться соответствующая подсказка.
Запрос режима может быть реализован следующим образом. В свободной части экрана появляется окно с текстом "РЕЖИМ: ОТЛАДКА" (см. рис. 1). Если пользователь нажимает клавишу пробела, тогда слово "ОТЛАДКА" заменяется на слово "СЧЕТ"; при новом нажатии этой клавиши снова появляется слово "ОТЛАДКА" и т.д. Нажатие клавиши Enter означает выбор того режима, название которого указано сейчас в окне.
Допустимо также нажатие клавиши Esc, что означает отказ от выбора режима и возврат на предыдущий этап (с удалением окна режима и восстановлением подсказки, соответствующей предыдущему этапу). На иные клавиши система в это время не должна реагировать. Курсор должен быть невидимым.
Этап 3. Выбор длины.
При любом выбранном режиме система далее спрашивает у пользователя, последова-тельности какой длины он желает упорядочивать. В режиме счета длина может меняться от 1 до 100, а в режиме отладки - от 1 до 15.
Запрос длины можно реализовать так. На экране появляется окно с текстом "ДЛИНА (<=15): " (или "<=100" в режиме счета), за которым следует "поле ввода" - 3-4 позиции, в которые пользователь будет вводить длину (система не должна разрешать ему выходить за рамки этого поля). Курсор на этом этапе видим и показывает позицию, в которую пользователь вводит очередной символ (вначале это первая позиция поля ввода, а затем курсор сдвигается вправо по мере ввода числа). В нижней строке экрана должна высвечиваться соответствующая подсказка. Экран в этот момент может выглядеть так:
┌─────────────────────┐ ┌──────────────────┐ │ методы сортировки: │ │ режим: отладка │ │ Бинарные вставки │ └──────────────────┘ │ Метод пузырька (*)│ │ Простой выбор │ ┌──────────────────┐ │ МЕТОД ШЕЛЛА (*) │ │ длина (<=15): _ │ │ Естест.слияние │ └──────────────────┘ └─────────────────────┘ СТРОКА С ПОДСКАЗКОЙ |
Рис. 1
При вводе числа (до нажатия клавиши Enter) пользователь должен иметь возможность вносить изменения в набранный текст. Рекомендуется использовать следующие клавиши для редактирования вводимого текста:
← , → - перемещение курсора на одну позицию влево или вправо (без выхода за границы поля ввода)
Del - удаление символа, на который указывает курсор (со сдвигом влево на одну позицию правой части уже набранного текста)
Backspace - удаление символа слева от курсора (если только курсор не находится в начале поля ввода) со сдвигом на одну позицию влево самого курсора и правой части уже набранного текста
Ins - переключение с режима вставки на режим замены или наоборот (начальный режим - вставка)
(Замечание. В режиме замены введенный символ заменяет на экране тот символ, на который указывает курсор, а в режиме вставки часть текста (от курсора и вправо) сдвигается на одну позицию вправо и в освободившуюся позицию вставляется введенный символ. Далее (в любом режиме) курсор перемещается на одну позицию вправо, если только он не находится в конце поля ввода.)
При вводе длины нажатие клавиши Enter (при любом положении курсора) означает, что ввод окончен. Система должна считать набранные цифры и перевести их в соответствующую числовую величину. Если число набрано верно и не выходит за определенный диапазон, то система переходит к следующему, четвертому, этапу своей работы, а иначе она должна каким-то образом сообщить об ошибке и предоставить пользователю возможность исправить ранее набранную длину.
Помимо указанных выше клавиш система должна реагировать и на клавишу Esc, нажатие которой означает отказ от ввода и возврат системы на предыдущий этап (с удалением окна длины и восстановлением прежней подсказки).
Этап 4а. Работа в режиме счета.
Если пользователь выбрал режим счета, тогда система (после запроса длины) сама генерирует несколько последовательностей заданной длины (какие именно - см. задание 3) и сортирует каждую из них выбранным методом. В результате на экране должна появиться таблица, в которой для каждой последовательности указано число сравнений и число перемещений, выполненных во время ее сортировки, а также усредненные значения этих характеристик. Таблица должна сохраняться на экране до тех пор, пока пользователь не нажмет на какую-нибудь клавишу, после чего следует восстановить состояние экрана, соответствующее 3-му этапу, чтобы пользователь мог задать новую длину.
Этап 4б. Работа в режиме отладки.
В этом режиме система (после запроса длины) очищает экран и высвечивает в его левой части окно из n строк, где n - заданная длина (см. рис. 2). Это окно предназначено для ввода пользователем дат той последовательности, которую он хочет упорядочить (поэтому ширина окна должна быть выбрана с расчетом на самую "длинную" дату). Курсор в это время видим и показывает место, куда будет помещен очередной набранный символ. Пользователь должен иметь возможность редактировать набираемый текст - так же, как и при вводе длины (см. выше).
Желательно в верхней части окна указать, в каком порядке должны вводиться элементы дат (например: день, месяц, год) и какой символ (например, точка) используется как разделитель. При этом формат вводимых дат должен быть свободным: не надо требовать, чтобы каждый элемент даты содержал ровно две цифры, не надо заранее расставлять точки.
┌────────────┐ │ дд.мм.гг │ ┌────────────┐ ┌────────────┐ │────────────│ │ │ │ │ │ 9.5.45 │ │ предыдущий │ │ очередной │ │ 25.10.17 │ │ шаг │ │ шаг │ │ 15.7_ │ │ сортировки │ │ сортировки │ │ │ │ │ │ │ │ │ │ │ │ │ └────────────┘ └────────────┘ └────────────┘ строка с подсказкой |
Рис. 2
Нажатие клавиши Enter или ↓ является признаком конца ввода текущей даты. В этот момент система должна проверить, правильно ли была набрана дата, и, если да, перейти к следующей строке окна. Иначе система должна сообщить (звуковым сигналом или каким-то сообщением) пользователю об ошибке и остаться в текущей строке окна, чтобы пользователь мог исправить дату. Смысл клавиши ↑ аналогичен, но по ней происходит переход к предыдущей дате (этот возврат нужен, чтобы пользователь мог изменить ранее набранную дату).