ЛОЙКО В И СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ КРАСНОДАР 2004 261 С 13

readln(key);
v:=maketree(key);
while p<>nil do
begin
q:=p;
if key else p:=right(p);
end;
if p=nil then
begin
writeln('Это корень');
tree:=v;
end
else
if key else right(p):=v;
end;

При обходе дерева слева - направо получаем отсортированный массив 20, 30, 35, 45, 60, 70, 82, 85, 86, 87, 88, 90. Элемент дерева заносится в массив при втором заходе в него (на рисунке вторые заходы показаны зелеными стрелками).

Обход дерева слева - направо
procedure InTree(tree);
begin
if Tree = nil then write('Дерево пусто')
else
with Tree^ do
begin
if left<>nil then InTree(left);
if right<>nil then InTree(right);
end;
end;

Задания

Вариант 1: На заводе выпустили детали со следующими серийными номерами : 45, 56, 13, 75, 14, 18, 43, 11, 52, 12, 10, 36, 47, 9. Детали с четными номерами поступают на склад №1, а с нечетными на слад №2. Требуется отсортировать детали на складе №1.

Вариант 2 : Угнали автомобиль. Свидетель запомнил, что первой цифрой номера была 4. В базе угнанных автомобилей в этот день были следующие номера : 456, 124, 786, 435, 788, 444, 565, 127, 458, 322, 411, 531, 400, 546, 410. Нужно составить список номеров начинающихся на 4 и упорядочить его по возрастанию.

Вариант 3 : За неделю езды в транспорте накопились билеты с номерами 124512, 342351, 765891, 453122, 431350, 876432, 734626, 238651, 455734, 234987. Нужно отобрать "счастливые" билеты и расположить их по возрастанию.

Вариант 4 : Дан список людей с указанием их возраста. Для составления графика ухода сотрудников на пенсию требуется составить новый список новый список в том порядке, в каком они будут уходить на пенсию.

Вариант 5 : Студенты сдали пять экзаменов. Нужно отсортировать список студентов по возрастанию общего балла по результатам сданных экзаменов.

Вариант 6 : В городе был один автобусный парк, куда приезжали автобусы с номерами : 11, 32, 23, 12, 6, 52, 47, 63, 69, 50, 43, 28, 35, 33, 42, 56, 55, 101. После строительства второго автопарка решили перевести туда автобусы с нечетными номерами. Для того чтобы составить расписание их движения нужно организовать список номеров автобусов второго парка, упорядочив их по убыванию.

Вариант 7 : Была составлена ведомость по зарплате, представленная в виде : Иванов - 166000, Сидоров - 180000, ... Требуется упорядочить этот список таким образом, чтобы размер зарплаты уменьшался.

Вариант 8 : На стоянке стоят автомобили со следующими номерами : 1212, 3451, 7694, 4512, 4352, 8732, 7326, 2350, 4536, 2387, 5746, 6776, 4316, 1324. Для статистики необходимо составить список автомобилей с такими номерами, сумма первых двух цифр которых равна сумме двух последних цифр, так чтобы каждый следующий номер был меньше предыдущего.

Вариант 9 : Выпустили лотерейные билеты с четырехзначными номерами. Выигрышными считаются те билеты, сумма цифр которых делится на 4. Составить список выигрышных билетов, упорядоченных по убыванию.

Вариант 10 : Молодой человек взял номер телефона у своей знакомой, но забыл его. Он смог вспомнить только первые три цифры : 469***. В его записной книжке были следующие номера телефонов : 456765, 469465, 469321, 616312, 576567, 469563, 567564, 469129, 675665, 469873, 569090, 469999, 564321, 469010. Составить список номеров начинающихся с цифр 469 и упорядочить их по убыванию.

Вариант 11 : Студенты сдали пять экзаменов. Нужно отсортировать список студентов по убыванию общего балла по результатам сданных экзаменов.

Вариант 12 : Выпустили лотерейные билеты с четырехзначными номерами. Выигрышными считаются те билеты, сумма первых трех цифр которых равна 8. Составить список выигрышных билетов, упорядоченных по возрастанию.

Лабораторная работа № 10. "ИССЛЕДОВАНИЕ МЕТОДОВ ЛИНЕЙНОГО И БИНАРНОГО ПОИСКА"

Цель работы: изучить методы линейного и бинарного поиска.

Задача работы: овладеть навыками написания программ для методов линейного и бинарного поиска на языке программирования ПАСКАЛЬ .

Порядок работы :
* изучить описание лабораторной работы;
* по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
* написать программу на языке ПАСКАЛЬ;
* отладить программу;
* решить задачу;
* оформить отчет.

Краткая теория

ПОИСК
Одно из наиболее часто встречающихся в программировании действий - поиск. Он же представляет собой идеальную задачу, на которой можно испытывать различные структуры данных по мере их появления. Существует несколько основных "вариаций этой темы", и для них создано много различных алгоритмов. При дальнейшем рассмотрении мы исходим из такого принципиального допущения: группа данных, в которой необходимо отыскать заданный элемент, фиксирована. Будем считать, что множество из N элементов задано, скажем, в виде такого массива
a: ARRAY[0..N-1] OF item
Обычно тип item описывает запись с некоторым полем, выполняющим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному "аргументу поиска" x. Полученный в результате индекс i, удовлетворяющий условию a[i].key=x, обеспечивает доступ к другим полям обнаруженного элемента. Так как нас интересует в первую очередь сам процесс поиска, а не обнаруженные данные, то мы будем считать, что тип item включает только ключ, т.е. он есть ключ (key).

Алгоритм
Линейный поиск
Если нет никакой дополнительной информации о разыскиваемых данных, то очевидный подход - простой последовательный просмотр массива с увеличением шаг за шагом той его части, где желаемого элемента не обнаружено. Такой метод называется линейным поиском. Условия окончания поиска таковы:
1. Элемент найден, т.е. ai = x.
2. Весь массив просмотрен и совпадения не обнаружено.

Это дает нам линейный алгоритм:
i := 0;
WHILE (i < N) AND (a[i] <> x) DO
i := i+1 ;
END;
Обратите внимание, что порядок элементов в логическом выражении имеет существенное значение. Инвариант цикла, т.е. условие, выполняющееся перед каждым увеличением индекса i, выглядит так:
(0 ? i < N) AND (Ak : 0 ? k < i : ak ? x)
Он говорит, что для всех значений k, меньших чем i, совпадения не было. Отсюда и из того факта, что поиск заканчивается только в случае ложности условия в заголовке цикла, можно вывести окончательное условие:
((i = N) OR (ai = x)) AND (Ak : 0 ? k < i : ak ? x)
Это условие не только указывает на желаемый результат, но из него же следует, что если элемент найден, то он найден вместе с минимально возможным индексом, т.е. это первый из таких элементов. Равенство i = N свидетельствует, что совпадения не существует.
Совершенно очевидно, что окончание цикла гарантировано, поскольку на каждом шаге значение i увеличивается, и, следовательно, оно, конечно же, достигнет за конечное число шагов предела N; фактически же, если совпадения не было, это произойдет после N шагов.
Ясно, что на каждом шаге требуется увеличивать индекс и вычислять логическое выражение. А можно ли эту работу упростить и таким образом убыстрить поиск ?
Единственная возможность - попытаться упростить само логическое выражение, ведь оно состоит из двух членов. Следовательно, единственный шанс на пути к более простому решению - сформулировать простое условие, эквивалентное нашему сложному. Это можно сделать, если мы гарантируем, что совпадение всегда произойдет. Для этого достаточно в конец массива поместить дополнительный элемент со значением x. Назовем такой вспомогательный элемент "барьером", ведь он охраняет нас от перехода за пределы массива. Теперь массив будет описан так:
a: ARRAY[0..N] OF INTEGER
и алгоритм линейного поиска с барьером выглядит следующим образом:
a[N] := x;
i := 0;
WHILE a[i] <> x DO
i := i+1;
END;
Результирующее условие, выведенное из того же инварианта, что и прежде:
(ai=x) AND (Ak : 0 ? k < i : ak ? x)
Ясно, что равенство i = N свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.

Поиск делением пополам (двоичный поиск).
Совершенно очевидно, что других способов убыстрения поиска не существует, если, конечно, нет еще какой-либо информации о данных, среди которых идет поиск. Хорошо известно, что поиск можно сделать значительно более эффективным, если данные будут упорядочены. Вообразите себе телефонный справочник, в котором фамилии не будут расположены по порядку. Это нечто совершенно бесполезное! Поэтому мы приводим алгоритм, основанный на знании того, что массив а упорядочен, т.е. удовлетворяет условию
Ak : 1? k < N : ak-1 ? ak
Основная идея - выбрать случайно некоторый элемент, предположим am, и сравнить его с аргументом поиска x. Если он равен x, то поиск заканчивается, если он меньше x, то мы заключаем, что все элементы с индексами, меньшими или равными m, можно исключить из дальнейшего поиска; если же он больше x, то исключаются индексы больше и равные m. Это соображение приводит нас к следующему алгоритму (он называется "поиском делением пополам"). Здесь две индексные переменные L и R отмечают соответственно левый и правый конец секции массива а, где еще может быть обнаружен требуемый элемент.
L := 0;
R := N-1;
found := FALSE;
WHILE (L Ј R) AND NOT found DO
m := любое значение между L и R;
IF a[m] = x THEN found := TRUE;
IF a[m] < x THEN L := m+1
ELSE R := m-1;
END;
END;
Инвариант цикла, т.е. условие, выполняющееся перед каждым шагом, таков:
(L ? R) AND (Ak : 0 ? k < L : ak < x) AND (Ak : R < k < N : ak > x)
из чего выводится результат
found OR ((L > R) AND (Ak : 0 ? k < L : ak < x) AND (Ak : R < k < N : ak > x))
откуда следует
(am = x) OR (Ak : 0 ? k < N : ak ? x)
Выбор m совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача - исключить на каждом шагу из дальнейшего поиска, каким бы ни был результат сравнения, как можно больше элементов. Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива. В результате максимальное число сравнений равно log N, округленному до ближайшего целого. Таким образом, приведенный алгоритм существенно выигрывает по сравнению с линейным поиском, ведь там ожидаемое число сравнений - N/2.
Эффективность можно несколько улучшить, поменяв местами заголовки условных операторов. Проверку на равенство можно выполнять во вторую очередь, так как она встречается лишь единожды и приводит к окончанию работы. Но более существенно следующее соображение: нельзя ли, как и при линейном поиске, отыскать такое решение, которое опять бы упростило условие окончания. И мы действительно находим такой быстрый алгоритм, как только отказываемся от наивного желания кончить поиск при фиксации совпадения. На первый взгляд это кажется странным, однако при внимательном рассмотрении обнаруживается, что выигрыш в эффективности на каждом шаге превосходит потери от сравнения с несколькими дополнительными элементами. Напомним, что число шагов в худшем случае - log N. Быстрый алгоритм основан на следующем инварианте:
(Ak : 0 ? k < L : ak < x) AND (Ak : R ? k < N : ak ? x)
причем поиск продолжается до тех пор, пока обе секции не "накроют" массив целиком.
L := 0;
R := N;
WHILE L < R DO
m := (L+R) DIV 2;
IF a[k] < x THEN L := m+1
ELSE R := m ;
END
END
Условие окончания - L і R, но достижимо ли оно? Для доказательства этого нам необходимо показать, что при всех обстоятельствах разность R-L на каждом шаге убывает. В начале каждого шага L < R. Для среднего арифметического m справедливо условие L Ј m < R. Следовательно, разность действительно убывает, ведь либо L увеличивается при присваивании ему значения m+1, либо R уменьшается при присваивании значения m. При L = R повторение цикла заканчивается. Однако наш инвариант и условие L = R еще не свидетельствуют о совпадении. Конечно, при R = N никаких совпадений нет. В других же случаях мы должны учитывать, что элемент а[R] в сравнениях никогда не участвует. Следовательно, необходима дополнительная проверка на равенство а[R] = x. В отличие от первого нашего решения приведенный алгоритм, как и в случае линейного поиска, находит совпадающий элемент с наименьшим индексом.

Задания
Варианты:
1.Найти наименьший элемент в массиве А с помощью линейного поиска.
2.Поиск элементов в массиве А, которые больше 30.
3.Вывести на экран все числа массива А кратные 3 (3,6,9,...) с помощью линейного поиска.
4.Найти все элементы, модуль которых больше 20 и меньше 50, с помощью линейного поиска.
5.Вывести на экран все числа массива А кратные 4 (4,8,...) с помощью линейного поиска.
6.Вывести на экран сообщение, каких чисел больше относительно 50, с помощью линейного поиска.
7.Найти элемент в массиве А и найти число сравнений с помощью линейного поиска.
8.Поиск элементов случайным образом с помощью бинарного поиска.
9.Дан список номеров машин (345, 368, 876, 945, 564, 387, 230), найти, на каком месте стоит машина с заданным номером, бинарный поиск.
10.Поиск каждого второго элемента в списке и число сравнений.
11.Найти элемент с заданным ключом с помощью бинарного поиска.

Лабораторная работа №11. "ИССЛЕДОВАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ ПОИСКА "

Цель работы: исследовать и изучить методы поиска с перемещением в начало и транспозицией.

Задача работы: овладеть навыками написания программ по исследованию методов поиска с перемещением в начало и транспозицией на языке программирования ПАСКАЛЬ .

Порядок работы :
* изучить описание лабораторной работы;
* по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
* написать программу на языке ПАСКАЛЬ;
* отладить программу;
* решить задачу;
* оформить отчет.

Краткая теория

ПОИСК (SEARCH) является одной из основ обработки данных в ЭВМ. Его назначение состоит в том, чтобы по заданному аргументу найти среди массива данных те данные, которые соответствуют этому аргументу или определить, что этих данных нет. Если этих данных нет, добавить их в массив данных.
Набор любых данных будем называть ТАБЛИЦЕЙ или ФАЙЛОМ. Данное или элемент структуры отличается каким-то признаком от других данных. Этот признак называется КЛЮЧОМ. Ключ может быть УНИКАЛЬНЫМ, т.е. в таблице только одно данное с таким ключом, иначе уникальные ключи называются ПЕРВИЧНЫМИ КЛЮЧАМИ.
ВТОРИЧНЫЙ КЛЮЧ в одной таблице может повторяться, но по нему тоже можно организовать поиск. Ключи данных собраны в одном месте (таблице).
Ключи, которые выделены из таблицы данных и организованы в свой файл, называются ВНЕШНИМИ КЛЮЧАМИ. Если ключ в записи, то он называется ВНУТРЕННИМ КЛЮЧОМ.
ПОИСКОМ ПО ЗАДАННОМУ АРГУМЕНТУ называется алгоритм, определяющий соответствие ключа данного с заданным аргументом. Результатом работы алгоритма поиска может быть нахождение этого данного или отсутствие данного в таблице. В случае отсутствия данного возможны две операции:
1. Индикация того, что данного нет.
2. Вставка данного в таблицу.
Пусть К - массив ключей, тогда для всех К(i) существует R(i) - данное. KEY - аргумент поиска. Ему соответствует информационная запись REC. В зависимости от того, какова структура данных в таблице, различают несколько видов поиска.

ПЕРЕУПОРЯДОЧЕНИЕ ТАБЛИЦЫ ПОИСКА

Всегда можно говорить о некотором значении вероятности нахождения того или иного элемента.
P(i) - вероятность нахождения элемента.
В этом случае таблица поиска представляется как система с дискретными состояниями, а искомый элемент характеризуется i-ым состоянием системы, вероятность которого P(i).
P(1) + P(2) + ... + P(n) = 1
Количество сравнений Z при поиске в таблице, т.е. количество сравнений, необходимых для поиска по заданному аргументу, представляет собой значение дискретной случайной величины, определяемой номерами состояний и вероятностями состояний системы.
Z=1*P(1) + 2*P(2) + 3*P(3) + ... + n*P(n)

ТАБЛИЦА ДАННЫХ ДОЛЖНА БЫТЬ УПОРЯДОЧЕНА ТАКИМ ОБРАЗОМ , чтобы в начале таблицы были элементы с большими вероятностями поиска или элементы , к которым чаще всего обращаются в таблице.
P(1) >= P(2) >= P(3) >= ... >= P(n)

ИМЕЕТСЯ ДВА ОСНОВНЫХ МЕТОДА ПЕРЕУПОРЯДОЧЕНИЯ ТАБЛИЦ ПОИСКА:
1. Переупорядочение путем перестановки найденного элемента в начало списка.
2. Метод транспозиции.
Алгоритм
Переупорядочение путем перестановки в начало списка

Найденный элемент сразу оказывается в голове списка.

Первоначально указатель q нулевой, указатель p указывает на начало списка; p перемещается на второй элемент, а q на первый. Указатель начала списка (table) перемещается на второй элемент, а указатель второго элемента на третий. Таким образом второй элемент перемещается на первое место.

(ПСЕВДОКОД)
q=nil
p=table
WHILE (p <> nil) do
IF key=k(p)
then SEARCH=p
next(q)=next(p)
next(p)=q
table=p
return
end IF
q=p
p=next(p)
end WHILE
SEARCH=0
return
Метод транспозиции
В данном методе найденный элемент переставляется на один элемент к голове списка. Если к этому элементу обращаются часто, то постепенно перемещаясь к началу списка, он скоро окажется в его голове.
Этот метод удобен тем, что он эффективен не только в списковых структурах, но и в неупорядоченных массивах, т.к. меняются местами только два рядом стоящих элемента.
Будем использовать три указателя:
p - рабочий указатель, указывает на элемент.
q - вспомогательный указатель, отстает на один шаг от p.

s - вспомогательный указатель, отстает на два шага от p.

Найденный нами третий элемент передвигается на один шаг к голове списка (т.е. становится вторым). Указатель первого элемента перемещается на третий элемент, указатель второго элемента на четвертый, таким образом третий элемент перемещается на второе место. Если к данному элементу обратиться еще раз, то он окажется в голове списка.

s=nil
q=nil
p=nil
while (p<>nil) do
if key=k(p) then search=p
if q=nil then return
else next(q)=next(p)
next(p)=q
if s=nil then table
else next(s)=p
end if
search=p
end if
end if
return
end while
search=nil return

Задания

Дан массив целых чисел. Составить процедуры метода транспозиции и перестановки в начало. Решить заданную задачу и переставить найденный в задаче элемент обоими методами в начало списка.

ВАРИАНТ 1. Найти максимальный элемент массива.

ВАРИАНТ 2. Найти минимальный элемент массива.

ВАРИАНТ 3. Найти число, нацело делящееся на 11 ( если таких чисел несколько, то найти максимальное; если таких чисел нет - выдать сообщение ).

ВАРИАНТ 4. Найти число, нацело делящееся на 11 ( если таких чисел несколько, то найти максимальное; если таких чисел нет - выдать сообщение ).

ВАРИАНТ 5. Найти элемент, разность соседних элементов которого не меньше 72. Если таких элементов несколько, выбрать максимальный. Если таких элементов нет, выдать сообщение.

ВАРИАНТ 6. Найти элемент, частное соседних элементов которого четное число. Если таких элементов несколько, выбрать максимальный или минимальный элемент. Если таких элементов нет, выдать сообщение.

ВАРИАНТ 7. Найти элемент, разность соседних элементов которого четное число. Если таких элементов несколько, выбрать максимальный или минимальный элемент. Если такого элемента нет, выдать сообщение.

ВАРИАНТ 8. Найти элемент, среднее арифметическое элементов, находящихся до этого элемента равно 12. Если таких элементов нет, выдать сообщение.

ВАРИАНТ 9. Найти максимальный элемент, делящийся на 10. Если такого элемента нет, выдать сообщение.

ВАРИАНТ 10. Найти элемент, разность соседних элементов которого четное число и делится на 3. Если такого элемента нет, выдать сообщение.

ВАРИАНТ 11. Найти элемент, среднее квадратичное элементов, находящихся после этого элемента меньше 10. Если таких элементов несколько, выбрать максимальный элемент. Если таких элементов нет, выдать сообщение.

ВАРИАНТ 12. Найти значение tg (x) от каждого элемента и переставить на 1 место элемент, значение функции от которого максимально.

Лабораторная работа № 12. "ПОИСК ПО ДЕРЕВУ С ВКЛЮЧЕНИЕМ"

Цель работы: освоить алгоритм и метод вставки элементов бинарного дерева.

Задача работы: овладеть навыками написания программ по исследованию методов вставки элементов бинарного дерева на языке программирования ПАСКАЛЬ .

Порядок работы :
* изучить описание лабораторной работы;
* по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
* написать программу на языке ПАСКАЛЬ;
* отладить программу;
* решить задачу;

<< Пред. стр. 13 (из 19) След. >>

Список литературы по разделу