Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Топ:
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Дисциплины:
2017-10-09 | 233 |
5.00
из
|
Заказать работу |
|
|
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Практикум содержит набор лабораторных работ по предмету «теория алгоритмов» во время проведения которых изучаются:основные принципы и приемы построения алгоритмических схем для различного рода задач, а также механизм реализации этих алгоритмов на языке высокого уровня.
Данные методические указания рассчитанный на студентов специальност:
230115 «Программирование в компьютерных системах»;
и содержат сведения необходимые для выполнения заданий лабораторного практикума. Для освоения изучаемого материала студентами выполняются индивидуальные задания.
Перечень лабораторных работ:
ЛАБОРАТОРНАЯ РАБОТА № 1«Разработка программ для Машины Поста»
ЛАБОРАТОРНАЯ РАБОТА № 2 «Разработка программ для Машины Тьюринга» ЛАБОРАТОРНАЯ РАБОТА № 3 «Разработка программ для алгорифмов Маркова»
ЛАБОРАТОРНАЯ РАБОТА №4 «Разработка программ с использованием рекурсивных функций»
ЛАБОРАТОРНАЯ РАБОТА №5 «Разработка программ с использованием алгоритмов перебора»
ЛАБОРАТОРНАЯ РАБОТА №6 «Разработка программ с использованием алгоритмов сортировки»
ЛАБОРАТОРНАЯ РАБОТА №7 «Составление алгоритма решения для системы линейных уравнений на алгоритмическом языке»
ЛАБОРАТОРНАЯ РАБОТА №8 «Составление алгоритма поиска кротчайшего пути»
ЛАБОРАТОРНАЯ РАБОТА № 1
Разработка программ для Машины Поста
Цель работы: развить аналитическое и логическое мышление учащихся, математическую интуицию, по средствам разработки алгоритмов задач для логических машин.
Задача работы: изучить программу имитатор машины Поста. Выработать навык составления алгоритмов для машины Поста.
Теоретическая часть
|
Формат команды машины Поста имеет вид: n K m
где:
n - номер текущей команды;
K - команда из системы команд машины Поста (см. табл. 1);
m - ссылка - номер команды, которая будет выполняться следующей.
Таблица 1. Система команд машины Поста | |
--> | Сдвиг каретки вправо, содержимое ленты не меняется. |
<-- | Сдвиг каретки влево, содержимое ленты не меняется. |
V | В обозреваемую секцию ставится метка "V". Выполнение этой команды возможно только в том случае, если обозреваемая секция пустая, в противном случае команда считается невыполнимой. |
Каретка стирает метку в обозреваемой секции. Выполнение этой команды возможно только в том случае, если обозреваемая секция содержит метку, в противном случае команда считается невыполнимой. | |
? b1, b2 | Команда передачи. Проверяется содержимое текущей секции, если метки нет, то происходит передача управления команде с номером b1, иначе, если метка есть - команде с номером b2. Содержимое ленты не меняется. |
! | Команда останова машины. Содержимое ленты не меняется. У команды остановки ссылка не обязательна. |
Для того чтобы заполнить ленту достаточно подвести к ячейке указатель мыши и выполнить двойной щелчок левой кнопкой, или воспользоваться кнопкой .
- запоминает начальное состояние ленты.
- восстанавливает начальное состояние ленты.
- запускает алгоритм программы на выполнение.
- пошаговое выполнение программы.
- остановка выполнения программы.
Текст задания:
Отчет выполняется в электронном виде. Если строк таблицы для описания алгоритма программы не хватает их не обходимо добавить. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.
Отчет о выполнении задания
Вставить скриншот состояния ленты после выполнения алгоритма.
Заполнить таблицу вписав алгоритм программы комментируя каждую строку.
Номер команды | команда | отсылка | комментарий |
Контрольные вопросы:
|
Задания для выполнения лабораторных работ
Задача 1
Составить программу перевода информационной ленты из начального состояния в конечное:
1 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
2 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
3 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
4 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
5 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
6 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
7 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | … |
8 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
9 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
10 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
11 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
12 вариант
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | … |
|
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
Задача 2
Выполнить арифметические действия:
1. 3+4, 4-2;
2. 5+3, 3*2;
3. 5-2, 2*2;
4. 5-4, 6/2;
5. 3+2, 4/2;
6. 2+4, 2*4;
7.
Задача 1
Составить программу для прохождения каретки от левой метки к правой. Количество пустых клеток между метками неизвестно.
Н.с. | … | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | … |
Задача 2
Составить программу для заполнения всех клеток от левой метки до правой. Количество пустых клеток между метками неизвестно.
Н.с. | … | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | ۷ | … |
Задача 3
Составить программу перевода информационной ленты из начального состояния в конечное. Количество меток произвольное (не обязательно равно 4).
Н.с. | … | ۷ | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | … |
Задача 4
Составить программу перевода информационной ленты из начального состояния в конечное. Количество меток произвольное (не обязательно равно 4).
Н.с. | … | ۷ | ... | ۷ | ۷ | ۷ | ۷ | … |
К.с. | … | ۷ | ۷ | ۷ | ۷ | … |
5.
ЛАБОРАТОРНАЯ РАБОТА № 2
Разработка программ для Машины Тьюринга
Цель работы: развить аналитическое и логическое мышление учащихся, математическую интуицию, по средствам разработки алгоритмов задач для логических машин.
Задача работы: изучить программу имитатор машины Тьюринга. Выработать навык составления алгоритмов для машины Тьюринга.
Теоретическая часть
Формат команды машины Тьюринга имеет вид: a K q, где:
a - новое содержание текущей ячейки (новый символ внешнего алфавита, который заносится в текущую ячейку),
K - команда лентопротяжного механизма машины Тьюринга (влево, вправо, стоп)
q - новое внутренне состояние машины Тьюринга
Внешний алфавит
Это редактор для введения, отображения и хранения символов внешнего алфавита машины Тьюринга. Его необходимо заполнять в первую очередь, при написании алгоритма машины Тьюринга. Каждый символ можно указать только один раз. Между символами могут быть пробелы. Символ "Пробел" присутствует во внешнем алфавите всегда по умолчанию.
|
Если редактор "внешний алфавит" не виден, выберите пункт меню "Вид/ Внешний алфавит",
повторный выбор прячет редактор.
Прежде, чем вводить алгоритм, нужно ввести внешний алфавит.
Таблица машины Тьюринга
После окончания ввода внешнего алфавита формируется первый столбец таблицы: он заполняется символами внешнего алфавита в том же порядке что и в редакторе. При редактировании внешнего алфавита автоматически изменяется таблица: вставляются, удаляются или меняются местами строки. При очистке "внешнего алфавита", очищается вся таблица.
В ячейках верхней строки записываются символы состояний головки: Q1,Q2...Qn.
В ячейках первого столбца записываются символы внешнего алфавита.
В ячейках других столбцов и строчек помещаются команды машины Тьюринга.
Чтобы ввести команду в ячейку нужно:
1) Ввести символ внешнего алфавита на который будет заменен старый или записан если ячейка пуста;
2) Ввести одну из команд лентопротяжного механизма:
• "Влево" - ввести левую угловую скобку "<"
• "Вправо" - ввести правую угловую скобку ">"
• "Стоп" - ввести восклицательный знак "!"
3) Ввести номер нового внутреннего состояния. Нужно ввести только цифру, букву Q вводить не надо.
Пробелы в команде игнорируются.
Чтобы указать в команде в качестве символа внешнего алфавита "пробел", нужно ввести в ячейку символ подчеркивания "_", пробел или ввести сразу команду лентопротяжного механизма. Если команда не была введена правильно, то в ячейку таблицы ничего не запишется. Чтобы удалить, вставить, добавить столбцы, очистить строки или столбцы воспользуйтесь соответствующими пунктами главного или всплывающего меню или панелью инструментов.
Текст задания:
Отчет выполняется в электронном виде. Если строк таблицы для описания алгоритма программы не хватает их не обходимо добавить. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.
Отчет о выполнении задания
Вставить скриншот состояния ленты после выполнения алгоритма.
Заполнить таблицу вписав алгоритм программы, комментируя каждую строку.
Q A | Q0 | Q1 | Q2 | Q3 | комментарий |
Контрольные вопросы:
|
ЛАБОРАТОРНАЯ РАБОТА № 3
Разработка программ для алгорифмов Маркова
Цель работы: развить аналитическое и логическое мышление учащихся, математическую интуицию, по средствам разработки алгоритмов задач для логических машин.
Задача работы: изучить программу имитатор алгорифмов Маркова. Выработать навык составления алгорифмов Маркова.
Теоритическая часть
Нормальный алгоритм задает метод преобразования строк с помощью системы подстановок.
Каждая подстановка состоит из слова-образца и слова-замены, разделенных цепочкой символов «->». На каждом шаге замены подстановки просматриваются по порядку сверху вниз, и выполняется первая из них, которая подошла: первое найденное слово-образец рабочей строки заменяется на слово-замену.
Слова слева и справа от знака «->» могут быть (а могут и не быть) заключены в апострофы или двойные кавычки.
Следующие подстановки равносильны и определяют замену буквы «а» на сочетание «бв»:
а -> бв
'а' -> 'бв '
"а" -> "бв "
'а' -> "бв "
Левая часть (слово-образец) может отсутствовать, в этом случае слово-замена ставится в самое начало рабочего слова. Обычно такая замена должна стоять последней в списке подстановок (иначе происходит зацикливание).
Правая часть подстановки тоже может отсутствовать (при стирании образца).
Символ «.» после слова-замены обозначает терминальную подстановку, после которой выполнение алгоритма заканчивается.
Например:
'а' -> 'б '. заменить «а» на «б» и остановить программу
* ->. стереть знак * и остановить программу
В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.
Система постановок, задающая нормальный алгорифм Маркова, набирается в виде таблице в нижней части окна программы.
Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.
Задачи можно сохранять в файлах и загружать из файлов. Сохраняется условие задачи, исходное слово и система подстановок.
Протокол работы алгоритма, в котором показаны все последовательные замены, вызывается при нажатии клавиш Ctrl+P.
Текст задания:
Отчет выполняется в электронном виде. Если строк таблицы для описания алгоритма программы не хватает их не обходимо добавить. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.
Отчет о выполнении задания
Вставить скриншот состояния рабочий строки после выполнения алгоритма.
Заполнить таблицу вписав алгоритм программы, комментируя каждую строку.
№ | образец | замена | комментарий | |
-> | ||||
-> | ||||
-> | ||||
-> | ||||
5 | -> | |||
6 | -> | |||
7 | -> | |||
8 | -> | |||
9 | -> | |||
10 | -> | |||
11 | -> | |||
12 | -> | |||
13 | -> | |||
14 | -> | |||
15 | -> | |||
16 | -> | |||
17 | -> | |||
18 | -> | |||
19 | -> | |||
20 | -> | |||
21 | -> | |||
22 | -> |
Контрольные вопросы:
1. Что такое алгорифм Маркова.
2. Система подстановок алгорифма Маркова.
3. Правела выполнения алгорифмов Маркова.
4. Варианты окончания выполнения программы.
ЛАБОРАТОРНАЯ РАБОТА №4
Теоретическая часть
рекурсия - способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе.
Имеется два вида рекурсии:
1) прямая рекурсия означает, что процедура вызывает саму себя;
2) косвенная рекурсия означает, что одна процедура вызывает другую процедуру, а это в свою очередь прямо или косвенно приводит к вызову первоначальной процедуры.
Рекурсию следует использовать только тогда, когда задача легко поддается рекурсивному решению. Любая задача, которая может быть решена рекурсивно, также может быть решена и без рекурсии.
Перед выполнением работы необходимо изучить способы описания и использования рекурсивных процедур и функций:
Функция
Function <имя ф-ции> (n-формальные параметры): <тип возвращаемого результата>;
Begin
<имя ф-ции>:=<имя ф-ции> (n-1);
End;
Процедура
Procedure <имя п-ры> (n-формальные параметры);
Begin
<имя п-ры> (n-1);
End;
2. косвенная рекурсия
До вызова процедура или функция должна быть обязательно описана, для этого используется опережающее объявление: процедура или функция содержит описание только своего заголовка, вслед за которым ставится зарезервированное слово forward.
Var
<имя переменной>: <тип переменной>;
Procedure <имя п-ры 2> (n-формальные параметры); forward;
Procedure <имя п-ры 1> (n-формальные параметры);
Begin
<имя п-ры 2> (n-1);
End;
Procedur e <имя п-ры 2> (n-формальные параметры);
Begin
<имя п-ры 1> (n-1);
End;
Отчет о выполнении
Отчет выполняется в электронном виде. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.
Текст задачи |
Спецификация программы |
Листинг алгоритма исполняемого файла |
Скриншот интерфейса запускного файла программы |
Контрольные вопросы:
1. Что понимается под структурным программированием?
2. Что называется подпрограммой?
3. Что такое «рекурсия»?
4. Как объявляется рекурсивная подпрограмма?
5. В чем преимущества и недостатки использования рекурсии?
6. Какие виды рекурсий бывают и в чем их особенность?
ЛАБОРАТОРНАЯ РАБОТА №5
Теоретическая часть
Перестановки
Задача: Напечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).
First = (1,2,...,N) Last = (N,N-1,...,1)
Всего таких перестановок будет N!=N*(N-1)*...*2*1 (докажите!). Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).
Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]<X[i+1]>...>X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1],...,X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1,...,N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:
procedure Next;
begin
{найти i: X[i]<X[i+1]>X[i+2]>...>X[N]};
{найти j: X[j]>X[i]>X[j+1]>...>X[N]};
{обменять X[i] и X[j]};
{X[i+1]>X[i+2]>...>X[N]};
{перевернуть X[i+1],X[i+2],...,X[N]};
end;
Теперь можно написать программу:
program Perestanovki;
type Pere=array [byte] of byte;
var N,i,j:byte;
X:Pere;
Yes:boolean;
procedure Next(var X:Pere;var Yes:boolean);
var i:byte;
procedure Swap(var a,b:byte); {обмен переменных}
var c:byte;
begin c:=a;a:=b;b:=c end;
begin
i:=N-1;
{поиск i}
while (i>0)and(X[i]>X[i+1]) do dec(i);
if i>0 then
begin
j:=i+1;
{поиск j}
while (j<N)and(X[j+1]>X[i]) do inc(j);
Swap(X[i],X[j]);
for j:=i+1 to (N+i) div 2 do Swap(X[j],X[N-j+i+1]);
Yes:=true
end
else Yes:=false
end;
begin
write('N=');readln(N);
for i:=1 to N do X[i]:=i;
repeat
for i:=1 to N do write(X[i]);writeln;
Next(X,Yes)
until not Yes
end.
Разбиения
Задача: Перечислить все разбиения целого положительного числа N на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно).
Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.
First = (1,1,...,1) - N единиц Last = (N)
Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Сказать, сколько их будет всего, не так-то просто (см.следующий пункт). Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?
Во-первых, должно быть X[i-1]>X[i] или i=1. Во-вторых, i должно быть не последним эле ментом (увеличение i надо компенсировать уменьшением следующих). Если такого i нет, то данное разбиение последнее. Увеличив i, все следующие элементы надо взять минимально возможными, т.е. равными единице:
procedure Next;
begin
{найти i: (i<L) and ((X[i-1]>X[i]) or (i=1))}
X[i]:=X[i]+1;
{ L:= i + X[i+1]+...+X[L] - 1 }
X[i+1]:=...:=X[L]:=1
end;
Через L мы обозначили количество слагаемых в текущем разбиении (понятно, что 1<=L<=N). Программа будет выглядеть так:
program Razbieniya;
type Razb=array [byte] of byte;
var N,i,L:byte;
X:Razb;
procedure Next(var X:Razb;var L:byte);
var i,j:byte;
s:word;
begin
i:=L-1;s:=X[L];
{поиск i}
while (i>1)and(X[i-1]<=X[i]) do begin s:=s+X[i];dec(i) end;
inc(X[i]);
L:=i+s-1;
for j:=i+1 to L do X[j]:=1
end;
begin
write('N=');readln(N);
L:=N; for i:=1 to L do X[i]:=1;
for i:=1 to L do write(X[i]);writeln;
repeat
Next(X,L);
for i:=1 to L do write(X[i]);writeln
until L=1
end.
Отчет о выполнении
Отчет выполняется в электронном виде. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.
Текст задачи |
Листинг алгоритма исполняемого файла |
Скриншот интерфейса запускного файла программы |
Контрольные вопросы:
1. Какие бывают комбинаторные объекты?
2. Что называется перестановкой?
3. Что такое разбиение?
4. Объясните алгоритм перестановки?
5. Объясните алгоритм разбиения?
6. Какие виды перебора вы знаете?
ЛАБОРАТОРНАЯ РАБОТА №6
Теоретический материал
Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве. В этом смысле сортировка присутствует почти во всех задачах обработки информации. С сортировкой связаны многие фундаментальные приемы построения алгоритмов, которые и будут нас интересовать в первую очередь. В частности, сортировка является идеальным примером огромного разнообразия алгоритмов, выполняющих одну и ту же задачу, многие из которых в некотором смысле оптимальные, а большинство имеет какие-либо преимущества по сравнению с остальными. Поэтому на примере сортировки мы убеждаемся в необходимости сравнительного анализа алгоритмов. Зависимость выбора алгоритмов от структуры данных - явление довольно частое, а в случае сортировки она настолько сильна, что методы сортировки обычно разделяются на две категории:
· сортировка массивов (внутренняя сортировка)
· сортировка файлов (внешняя сортировка).
ПОСТАНОВКА ЗАДАЧИ
ДАНО
ТРЕБУЕТСЯ
СВЯЗЬ
и последовательность является перестановкой исходной последовательности.
Основное требование к методам внутренней сортировки - экономное использование памяти. Это означает, что переупорядочивание элементов надо выполнять на том же месте.
Методы внутренней сортировки можно разбить на четыре основных класса в зависимости от лежащего в их основе приема:
· сортировка включением(вставкой),
· сортировка выбором,
· сортировка обменом,
· разделением.
·
СОРТИРОВКА ВКЛЮЧЕНИЕМ. Этот метод состоит в том, что на каждом шаге берут i -ый элемент последовательности и передают его в готовую отсортированную часть последовательность, вставляя его на свое место. Алгоритм сортировки включениями выглядит следующим образом:
FOR I:= 2 TO N DO
BEGIN X:= a[I];
< вставить X на подходящее место в a[1],a[2],...,a[I] >
END
СОРТИРОВКА ВЫБОРОМ. Этот метод основан на следующем
правиле. Выбирается минимальный (максимальный) элемент последовательности и обменивается с первым элементом (элементом) последовательности. Очевидно, один элемент при этом встанет на свое место в отсортированной части последовательности. Далее все выше изложенное надо повторить в не отсортированной части последовательности и т.д.
FOR I = 1 TO N-1 DO
BEGIN
< присвоить K индекс наименьшего элемента из a[I]...a[N] >
< поменять местами a[I] и a[K] >
END
СОРТИРОВКА ОБМЕНОМ. Алгоритм обмена основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы. В качестве примера рассмотрим сортировку методом пузырька.
FOR I:= 2 TO N DO
FOR J:= N DOWNTO I DO
IF a[J-1] > a[J] THEN
BEGIN X:= a[J-1]; a[J-1]:= a[J]; a[J]:= X END
СОРТИРОВКА РАЗДЕЛЕНИЕМ. Алгоритм разделением основан на разбиении последовательности на две подпоследовательности по некоторому правилу. При этом каждая из них может не являться упорядоченной, но последовательное применение указанного правила приводит к упорядоченности последовательности. Примером этого класса алгоритмов является алгоритм быстрой сортировки.
Procedure quicksort(S);
begin
if < S содержит один элемент> then <возвратить S>
else begin <выбрать произвольный элемент a из S>;
<пусть S1,S2 и S3 - последовательности элементов из S, соответственно меньших, равных и больших a>;
<возвратить quicksort(S1), затем S2,, затем quicksort(S3) >
end
end
Внешняя сортировка, т.е. сортировка данных, находящихся на внешних запоминающих устройствах, имеет свои особенности.
Рассмотрим один из алгоритмов внешней сортировки.
СОРТИРОВКА СЛИЯНИЕМ. Главная идея, которая лежит в основе этой сортировки это представлении файла в виде постепенно увеличивающихся серий, т.е. упорядоченных подпоследовательностей. Если есть, по крайней мере, два файла и число серий в них равно или отличается на единицу, то последовательным слиянием отсортированных серий в новый файл можно уменьшить количество серий, по крайней мере, в два раза.
Отчет о выполнении
Отчет выполняется в электронном виде. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.
Текст задачи |
Листинг алгоритма исполняемого файла |
Скриншот интерфейса запускного файла программы |
Контрольные вопросы:
1. Что такое одномерный массив?
2. Что такое двухмерный массив?
3. Что такое сортировка массива?
4. Какие методы сортировки вы знаете?
ЛАБОРАТОРНАЯ РАБОТА №7
Отчет о выполнении
Отчет выполняется в электронном виде. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.
Текст задачи |
Листинг алгоритма исполняемого файла |
Скриншот интерфейса запускного файла программы |
Контрольные вопросы:
1. Что такое система линейных уравнений?
2. Матричный метод решения системы.
3. Какие методы еще знакомы.
ЛАБОРАТОРНАЯ РАБОТА №8
Интернет ресурсы
|
|
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!