Практическая работа №4 по дисциплине: Теория алгоритмов наименование работы: Составление алгоритмов сортировки методом грубой силы.


Смоленский колледж телекоммуникаций
(филиал) федерального государственного образовательного
бюджетного учреждения высшего профессионального образования
«Санкт-Петербургский государственный университет телекоммуникаций
им. проф. М.А. Бонч-Бруевича»
Практическая работа №4
по дисциплине: Теория алгоритмов
наименование работы: Составление алгоритмов сортировки методом грубой силы.
для специальностей: 230115, 09.02.03
работа рассчитана на 2 часа
составлена преподавателем: Скряго О.С.
Смоленск, 2014
1. Цель работы:
- изучить основные понятия сортировки;
- овладеть навыками составления алгоритмов сортировки данных методами прямого выбора и пузырька.
2. Литература:
2.1. Балюкевич, Э.Л. Математическая логика и теория алгоритмов [Электронный ресурс]: учебное пособие/ Балюкевич Э.Л., Ковалева Л.Ф.— Электрон. текстовые данные.— М.: Евразийский открытый институт, 2009.— 188 c. ISBN:978-5-374-00220-1
2.2. Верещагин, Н.К. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции [Электронный ресурс]/ Верещагин Н.К., Шень А.— Электрон. текстовые данные.— М.: МЦНМО, 2012.— 160 c. ISBN:978-5-4439-0014-8
2.3. Гаврилов, Г.П. Задачи и упражнения по дискретной математике [Электронный ресурс]: учебное пособие/ Гаврилов Г.П., Сапоженко А.А.— Электрон. текстовые данные.— М.: ФИЗМАТЛИТ, 2009.— 416 c. ISBN:978-5-9221-0477-7
3. Подготовка к работе:
3.1. Повторить тему «Сортировка. Метод грубой силы».
3.2. Подготовить бланк отчета (см.п.7).
3.3. Ответить на вопросы допуска:
3.3.1. Сформулировать определение сортировки?
3.3.2. В чем заключается метод грубой силы при построении алгоритмов?
3.3.3.Сформулировать определения массива?
4. Основное оборудование: ПЭВМ
5. Задание:
Выполните задание согласно варианту.
5.1. Составить блок-схему и написать программу, выполняющую сортировку заданного массива. Тип элементов в массиве и их количество, а также способ сортировки определяется согласно варианту.
№ варианта Тип элементов Количество элементов Упорядочить по: Метод сортировки
1 Целый 9 убыванию Прямой выбор
2 Вещественный 6 возрастанию «пузырек»
3 Строковый 8 алфавиту Прямой выбор
4 Вещественный 9 убыванию «пузырек»
5 Символьный 10 алфавиту в обратном порядке «пузырек»
6 Целый 13 убыванию «пузырек»
7 Строковый 5 алфавиту в обратном порядке Прямой выбор
8 Вещественный 6 убыванию Прямой выбор
9 Строковый 6 алфавиту «пузырек»
10 Целый 11 возрастанию «пузырек»
11 Целый 10 убыванию Прямой выбор
12 Вещественный 6 возрастанию «пузырек»
13 Строковый 14 алфавиту Прямой выбор
14 Символьный 15 алфавиту «пузырек»
15 Вещественный 10 возрастанию Прямой выбор
6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ.
6.1. Ознакомиться с заданием.
6.2. Определить номер варианта (в соответствии с номером в журнале).
6.3. Выполнить задание 5 письменно.
6.4. Сообщить преподавателю о выполненных заданиях.
6.5. Повторить правила техники безопасности:
Правила техники безопасности в компьютерном классе.
Перед началом работы необходимо убедиться в отсутствии видимых повреждений аппаратуры.
Работа с компьютером производится строго по указаниям преподавателя.
Запрещается:
Разъединять или соединять разъемы аппаратуры;
Прикасаться к экрану монитора;
Включать и выключать аппаратуру без указания преподавателя;
Класть какие-либо предметы на монитор, системный блок или клавиатуру;
Работать во влажной одежде, а также влажными или грязными руками;
Пытаться самостоятельно исправлять возникшую в аппаратуре неисправность.
Включите компьютер.
Включите в сеть стабилизатор напряжения (если он имеется).
Включите принтер (если он имеется).
Включите монитор.
Включите системный блок (большая кнопка на передней панели).
Выключение компьютера.
Завершите выполнение всех программ.
Выполните команду: Пуск Завершение работы Выключить компьютер (Alt+F4→ Завершение работы).
Выключите системный блок.
6.6. Приступить к выполнению тестирование программ.
6.7.Оформить отчет.
7. Содержание отчета:
7.1. Название и цель работы.
7.2 Ответы на вопросы допуска.
7.2. Указать номер варианта, привести условия задач своего варианта.
7.3. Представить выполненные задания согласно варианта, текст программы с комментариями.
7.4. Ответы на контрольные вопросы.
8. Контрольные вопросы:
8.1. Перечислить способы представления массива в памяти компьютера?
8.2. Описать суть метода сортировки массива?
8.3. Перечислите типичные задачи, для решения которых используется тип данных массив?
8.4. Описать суть сортировки методом прямого выбора?
8.5. Описать суть сортировки методом «пузырька»?

Составил преподаватель __________________________Скряго О.С.
9. Приложение:
Массив - это сгруппированный по месту распределения набор значений однотипных переменных, имеющих общее название. Различают одномерный и многомерный массивы. Максимально допустимое количество измерений в массиве - четыре. Допускаются массивы любых типов данных.
Элемент массива - это составная часть массива; индексированная переменная с одноимённым названием, имеющая некоторое значение.

Индекс элемента массива - одно или несколько целых значений, указанных в виде константы, переменной или выражения, перечисленных через запятую и заключённых в квадратные скобки. Индекс элемента массива однозначно определяет место элемента в массиве. Индекс элемента массива указывается непосредственно после идентификатора переменной (названия массива) и является неотъемлемой частью элемента массива. В MQL4 принято индексирование, начинающееся с нуля.

Пример описания массива:
Const
n=20; {задали размерность}
Varmas: array[1..n] of integer; {описали массив из целых чисел заданной размерности}
Пример заполнения массива:
for i:=1 to n do {цикл от 1 до n}
begin
writeln(‘Введите элемент’);
readln(mas[i]); {оператор ввода}
end;
Сортировка данных
Часто удобно располагать данные (особенно когда их много) в порядке возрастания или в порядке убывания. Такое упорядочение в программировании зовется сортировкой. Сортировать можно любые данные — важно только, чтобы их можно было тем или иным образом сравнивать (устанавливать, какое из них является наименьшим). Сортировать можно, например, значения скалярных типов, символы, упакованные массивы символов (строки).
Сортировка применяется во множестве задач. Например, слова в словаре или фамилии в списке располагаются в алфавитном порядке. И вообще, для того чтобы легче находить то или иное данное в большом массиве данных, следует их рассортировать. Поэтому в программах часто применяют сортировку. Есть различные методы сортировки. Одни из них простые, но более медленные, другие быстрые, но более сложные. Одни сортируют каждый массив заново, другие распознают уже упорядоченные части массива и потому работают быстрее.
Классические методы сортировки.
1) Метод прямого выбора.
Предназначенные для сортировки данные следует записать в массив. Результатом сортировки должен быть тот же самый массив — только его элементы должны быть расположены в порядке от наименьшего к наибольшему.
Его суть: находится наименьший (точнее, не превышающий всех прочих) элемент массива и меняется местами с первым; затем в части массива, начинающейся со второго элемента, снова ищется наименьший элемент и обменивается со вторым и т. д. Когда обменяется последний элемент, массив считается упорядоченным.
Алгоритм Selectionsort (А [1..n])// Сортировка массива методом выбора// Входные данные: Массив А[1..n] упорядочиваемых//элементов
// Выходные данные: Массив А[1..n], отсортированный//в неубывающем порядке
для I от 1 до n-1
min = iдля j от I до n
если A[j] < A[min] то min <=j
Обмен А [i] и A [min]
2) Метод прямого обмена («пузырек»)
При выполнении предыдущего метода в неотсортированной части массива находится наименьший элемент и переносится в начало этой части — словно бы погружается под большие. Можно поступить и противоположным образом — наибольшие элементы поднимать на поверхность. Так и происходит при сортировке методом «пузыря». Поочередно сравниваются соседние элементы: х(1) с х(2), х(2) с х(3), х(3) с х(4) и т. д Если x(i-1)>x(i), то элементы меняются местами: i-м элементом становится ((i-1)-й элемент, который опять сравнивается уже с элементом x(i+l). Таким образом, как пузыри в воде, большие элементы быстрее всплывают на поверхность, а самый большой элемент – быстрее всех.
Алгоритм BubbleSort (А [0..n - 1])
// Входные данные: Массив А[1..n] упорядочиваемых//элементов
// Выходные данные: Массив А[1..n], отсортированный//в неубывающем порядке
для I от 1 до n-1
для j от 1 до n-i если A[j] > A[j+1] то Обмен А [j] и A [J+1]
Для усовершенствования метода можно ввести переменную, фиксирующую, были ли обмены в очередном проходе (первоначально равная 0). Если массив уже упорядочен, то во внутреннем цикле не меняется местами ни одна пара элементов и значение этой переменной остается 0. Это значит, что можно закончить сортировку. Если применить процедуру к уже упорядоченному массиву, внешний цикл будет выполняться только один раз. Если в последнем проходе обмены были, переменная примет значение 1, и внешний цикл продолжится.
Обмен значениями двух переменных a, b
tmp:=a; {сохраняем значение а во временной переменной}
a:=b; {значение b кладем в а}
b:=tmp; {кладем в b значение, сохраненное в tmp}

Приложенные файлы

  • docx 19
    Размер файла: 45 kB Загрузок: 0

Добавить комментарий