Файл: Методичка к лабораторным и практическим.doc

3 1 2 6 5 4

а b с

3 1 2 6 5 4

аb с

3 1 2 4 5 6

аbс

Значения переменных After и Before совпадают. Это означает завершение выполнения действий уровня 1, в результате чего исходный массив будет разбит на две подпоследовательности элементов: левую и правую. В левой подпоследовательности находятся элементы, значения которых меньше значения контрольного элемента, а в правой – элементы, значения которых больше или равны значению контрольного элемента.

Вызов процедуры Quick_Sort(A, First, After-1) приведет к переходу на уровень 2. Так как фактические параметры процедуры First = 1, а After-1 = =4 - 1 = 3, то процедурой Quick_Sort будет обрабатываться последовательность, состоящая из 3 элементов и находящаяся слева от контрольного элемента, т.е. 3 1 2. Поэтому этот уровень обработки массива обозначим как 2.Л, , где символ Л означает обработку левой подпоследовательности. Ниже приводятся результаты ее обработки процедурой Quick_Sort.

Уровень 2.Л. Последовательность 3 1 2

a bc

3 1 2

a b с

1 3 2

a b c

1 3 2

ab c

1 2 3

abc

Совпадение значений After и Before означает завершение уровня 2.Л и переход на уровень 3.Л, так как опять происходит вызов процедуры Quick_Sort(A, First, After-1) обработки левой подпоследовательности элементов. Обрабатываемая подпоследовательность состоит только из 1 элемента, так как First = 1, а Last = After – 1 = 2 – 1 = 1.

Уровень 3.Л. Так как условие First < Last не выполняется, то никаких действий в процедуре Quick_Sort(A, First, After-1) не происходит и управление передается оператору вызова процедуры Quick_Sort(A, After+1, Last). Программа переходит на уровень 3.П. На этом уровне обрабатывается подпоследовательность, стоящая справа от контрольного элемента, полученного на уровне 2. В рассматриваемом примере эта подпоследовательность состоит только из одного элемента равного 3.

Уровень 3.П. При вызове процедуры Quick_Sort(A, After+1, Last) формальный параметр First получит значение First = After + 1 = 1 + 1 =2, а формальный параметр - Last = 1. Условие First < Last не выполняется, и программа переходит на уровень 2.П, где обрабатывается подпоследовательность, стоящая справа от контрольного элемента, равного 4.

Уровень 2.П. Последовательность 5 6

a bc

5 6

abс

Уровень 3.Л. Процедурой Quick_Sort(A, First, After-1) обрабатывается последовательность, состоящая из одного элемента, равного 5, параметр First = Last, поэтому происходит переход на уровень 3.П.

Уровень 3.П. Так как обрабатываемая подпоследовательность на этом уровне состоит из одного элемента, то происходит возврат на уровень 2.

Обработка подпоследоватедьностей, стоящих слева и справа от контрольного элемента, полученного на уровне 1 и равного 4, закончена. Программа возвращается на уровень 1, где происходит выход из процедуры Quick_Sort в основную программу. Действие программы завершается выводом результата:

Отсортированный массив

1 2 3 4 5 6.

Контрольные вопросы

1. Зачем нужно сортировать массив данных?

2. Что такое сортировка данных?

3. Какие группы сортировок существуют? Чем они отличаются друг от друга?

4. Какие способы прямых сортировок Вы знаете?

5. Как выглядит алгоритм “пузырьковой” сортировки?

6. Как выглядит алгоритм сортировки выбором?

7. Как выглядит алгоритм сортировки вставкой?

8. В чем суть алгоритма сортировки бинарными вставками?

Задачи

1. Дан одномерный массив Х, состоящий из N элементов, N – заданное натуральное число. Упорядочить элементы массива по неубыванию методом “пузырька”.

2. Дан одномерный массив Х, состоящий из N элементов, N – заданное натуральное число. Упорядочить элементы массива по невозрастанию методом вставки.

3. Дан одномерный массив А, состоящий из N элементов, N – заданное натуральное число. Упорядочить элементы массива по неубыванию методом выбора.

4. Даны целые x₁, ..., x_п. Получить в порядке возрастания все различные числа, входящие в x₁, ..., x_п. Воспользоваться алгоритмом сортировки бинарными вставками. В про­цессе сортировки следует отбрасывать элементы, уже встречав­шиеся раньше. Если в результате поиска места x_i в упорядочен­ной совокупности x₁, ..., x_k (k < i) обнаружится, что среди x₁, ..., x_k есть элемент, равный x_i, то следует перейти к рассмот­рению x_i+1 без изменения x₁, ..., x_k .

5. Даны действительные попарно различные a₁, ,.., а_n. Получить попарно различные целые j₁, ..., j_n, такие, что 1≤ j_k ≤ n (k=1, ..., n) и

6. Даны целые a₁, ..., a_n. Найти наибольшее значение, со­держащееся в последовательности чисел a₁, ..., a_n после выбрасывания из нее:

а) одного из членов со значением mах (a₁, ..., a_n);

б) всех членов со значением mах (a₁, ..., a_n).

7. Даны натуральные п, a₁, ..., a_n (n > 4). Числа a₁, ..., a_n — это измеренные в сотых долях секунды результаты п спортсменов в беге на 100 м. Составить команду из четырех лучших бегунов для участия в эстафете 4 100, т. е. указать одну из четверок натуральных чисел i, j, k, I такую, что 1 ≤i < j < k < l≤ n и сумма a_i + a_j +a_k + a_l имеет наименьшее значение.

8. Задан одномерный массив строк из N элементов. Отсортировать его элементы по алфавиту.

9. Радиостанция провела опрос 120 слушателей. Каждому был задан вопрос: “За кого из 13 политиков Вы намерены голосовать на предстоя­щих выборах?“ Составить программу получения 5 наиболее ча­сто встречающихся ответов и их долей (в %), результат вывести в виде таблицы.

10. Составить программу для обработки результатов кросса на 500 м для женщин. В кроссе участвует не более 100 студенток. В протоколе указывается фамилия, шифр группы, результат. Получить итоговую таблицу результатов спортсменов в порядке занятых ими мест. Определить количество участниц, выполнивших заданный норматив.

11. Лыжные гонки проводятся отдельно для двух групп участ­ников (в каждой группе не более 15 человек). Протокол соревнований каждой группы включает в себя фамилии участников и результат. Объединить результаты в обеих группах, упоря­дочить фамилии спортсменов в порядке занятых ими мест и вывести в виде таблицы с заголовком.

12. На конкурсе песни каждый зритель должен назвать луч­шую по его мнению песню и ее исполнителя. Обработать резуль­таты опроса, упорядочив их по количеству голосов и вывести в виде таблицы информацию о первых десяти песнях, возглавля­ющих список (песня, исполнитель, количество голосов).

13. Результаты соревнований по прыжкам в длину определя­ются по сумме двух попыток. В протоколе для каждого участни­ка указываются фамилия, общество, результаты первой и второй попыток. Вывести протокол в виде таблицы с заголовком с фамилиями участников соревнований в порядке занятых мест.

5.2 Поиск

При подготовке таблиц статистических сводок, справочных изданий, словарей, как правило, производят упорядочивание данных. Это делает работу с таблицей, справочником и тому подобными более удобной. Например, выигравшие номера упорядочены в лотерейных табли­цах по возрастанию. Упорядоченность облегчает проверку билета: если бы номера не были упорядочены, то проверка могла бы по­требовать сравнения номера билета со всеми номерами, содержа­щимися в таблице. Точно так же словарный порядок облегчает поиск слова в словаре или справочнике.

Поиск сведений в разнообразных таблицах и сводках может быть возложен на компьютер. Мы будем зани­маться алгоритмом быстрого поиска элемента в упорядоченной совокупности а₁, ..., а_n. При этом будем считать, что a₁, ..., a_n - целочисленный массив, b - некоторое целое число. Работая со сло­варем, мы имеем дело не с целыми числами, а со словами, но это не играет принципиальной роли: меняется только техника каж­дого сравнения, а не число сравнений.

Пусть a₁<...<a_n . Рассмотрим задачу: выяснить, входит ли данное число b в массив a₁, ..., а_n, и если входит, то каково значение р, для которого а_p=b? Эту задачу мы назовем задачей поиска элемента. Тривиальный алгоритм решения этой задачи ос­новывается на последовательных сравнениях b с элементами a₁, ..., а_n: сравнить b с a₁, если они равны, то р=1, иначе сравнить b с a₂ и т. д. Среднее число требуемых здесь сравнений можно считать равным n/2. Известен алгоритм, который требует гораздо меньших затрат.

Предположим, что в массиве a₁, ..., а_n имеется элемент, рав­ный b, т. е. существует такое р, что а_p = b. По результату любого сравнения а_s < b (1 ≤ s ≤ n) мы сразу определяем, лежит ли р в диапазоне от 1 до s или же в диапазоне от s + l до n: второе будет иметь место, если неравенство а_s < b справедливо, а пер­вое—если несправедливо. Если само s находится примерно посе­редине между 1 и n, то сравнение а_s < b сужает диапазон поиска примерно вдвое. Этот прием можно использовать многократно. Получается алгоритм, называемый алгоритмом деления пополам. В соответствии с этим алгоритмом надо взять первоначально 1 и п в качестве границ поиска индекса элемента; далее, до тех пор, пока границы не совпадут, шаг за шагом сдвигать их следующим образом: сравнить b с a_s, где s—целая часть среднего арифметического границ; если a_s < b, то заменить прежнюю нижнюю границу на s + 1, оставив верхнюю границу без измене­ния, иначе оставить без изменения нижнюю границу, а верхнюю заменить на s. Поиск закончится, когда границы совпадут.

Сказанное можно записать в виде последовательности опера­торов Паскаля (р и q обозначают упомянутые верхнюю и нижнюю границы; когда р и q совпадут, выполнение алгоритма закончится, и р дает результат выполнения);

р:=1; q:= n;

while р < q do

begin

s: =(p+q) div 2;

if a[s] < b then p:= s+1

else q:= s

end;

Вообще идея деления пополам (сведение задачи к примерно вдвое более простой в количественном отношении) оказывается весьма плодотворной для построения многих алгоритмов. В научной литературе деление пополам иногда именуется греческим термином «дихотомия» или латинским «бисекция», а для обозначения сущности самой идеи иногда используются слова «разделяй и властвуй».

Заметим сразу следующее. Мы исходим из предположения, что среди элементов a₁, ..., а_n имеется такой, который равен b. Если заранее неизвестно, имеется или нет такой элемент, то, получив р, надо дополнительно проверить, действительно ли а_p=b. И если обнаружится, что равенство несправедливо, то из этого будет сле­довать, что среди a₁, ..., а_n нет элемента, равного b.

Продемонстрируем применение этого алгоритма на конкретном примере. Пусть a₁, ..., а₁₀ соответственно равны 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Тогда для b = 19 поиск будет разворачиваться сле­дующим образом. В начале границы поиска равны 1 и 10. Имеем [(1 + 10) / 2] = 5, неравенство а₅ < b, т.е. 11 < 19, справедливо, поэтому переходим к границам 6, 10. Имеем [(6 +10) / 2] = 8, нера­венство a₈ < b, т.е. 19 < 19, несправедливо, поэтому переходим к границам 6, 8. Имеем [(6+8)/2] = 7, неравенство a₇ < b, т. е. 17 < 19, справедливо, поэтому переходим к границам 8, 8. Эти границы совпадают; следовательно, если в массиве вообще есть элемент со значением b, то это a₈. В данном случае равенство b = a₈ справедливо, так как 19 = 19.

Нетрудно убедиться, что если бы мы взяли в качестве b не 19, а 18, то до самого последнего момента применение алгоритма разворачивалось бы точно так же, но в самом конце дополнительная проверка равенства a₈ = b дала бы отрицательный результат, что явилось бы свидетельством того, что в массиве a₁, ..., а_n нет элемента со значением 18.

Алгоритм поиска элемента делением пополам обладает высоким быстродействием. Если п=2^m, то число сравнений b с элементами a₁, ..., а_n в процессе применения этого алгоритма не превзойдет m, а если п не равно 2^m ни для какого целого т, то в качестве гра­ницы для числа сравнений можно взять наименьшее m такое, что n < 2^m (без учета дополнительного сравнения а_р=b, необходимого в том случае, когда заранее неизвестно, имеется или нет среди a₁, ..., а_n элемент, равный b).

Например, если n = 10, то число сравнений не превосходит 4, так как 10 < 2⁴, для n = 32 это число не превосходит 5, так как 32 = 2⁵, для n = 1000 это число не превосходит 10, так как 1000 < 2¹⁰ и т. д.

Теперь мы приведем пример программы, использующей написан­ную выше последовательность операторов, т.е. алгоритм деления пополам.

Пусть таблица выигрышей лотереи представлена в виде двух массивов a₁, ..., а_n и с₁, ..., с_n (n - некоторая константа) так, что натуральные a₁, ..., а_n — это выигравшие номера (а₁ < ...< а_n), a c₁, ..., c_п - действительные положительные числа, означающие выигрыши в рублях, выпавшие соответственно на номера a₁, ..., а_n. Требуется найти выигрыши, выпавшие на ряд номеров (если номера нет в таблице, то выигрыш считается равным нулю). Схема программы:

program Loto;

описания;

begin

ввод массивов а и с;

1: write(‘ номер='); read(b);

найти р - предполагаемое место b в массиве а;

if a[p]=b then f:= c[p] else f:=0;

writeln(' выигрыш =',f); goto 1

end.

Мы легко можем детализировать эту схему и получить настоя­щую программу. Условимся, что значения элементов массивов а и с заданы в следующей последовательности: a₁, с₁, а₂, с₂,... a_n, c_n, где n—константа, значением которой будем считать 20:

program Loto;

const n =20;

type u=array[1 .. n] of integer;

v=array[1.. n] of real;

var a:u;

c:v;

i, p, q, s, b:integer;

f:real;

begin

for i:=1 to n do read(a[i], c[i]);

write('HOMЕР='); read(b);

p:=1; q:=n;

while p < q do

begin

s:=(p+ q) div 2;

if a[s] < b then p:= s+1

else q:=s

end;

if а[р]=b then f:=c[p]

else f:= 0;

writeln('выигрыш=' ,f);

end.

Идея деления пополам («разделяй и властвуй») может быть положена в основу алгоритма решения еще одной задачи, похожей на задачу поиска элемента. Пусть по-прежнему a₁ < a₂ < ... < а_n, и пусть b—некоторое число. Для числа b имеется n + 1 возмож­ность: b ≤ a₁, a₁ < b ≤ a₂, a₂ < b ≤ a₃, ..., a_n-1 < b ≤ a_n, a_n < b.

Требуется определить, какая из возможностей имеет место. Ответом должно быть одно из чисел 1, 2, ..., n, n+1 (порядковый номер возможности).

По результату любого сравнения a_s < b, 1 ≤ s ≤ n мы сразу определяем, лежит ли ответ в диапазоне от 1 до s или же в диапазоне от s+1 до n+1. Если само s находится примерно по середине между 1 и n+1, то сравнение а_s < b сужает диапазон поиска примерно вдвое. Это приводит к следующему алгоритму:

р:=1; q:=n+1;

while p < q do

begin

s: =(p+q) div 2;

if a[s] < b then p:=s+1

else q:=s

end;

Единственное отличие последнего алгоритма от алгоритма поиска элемента состоит в начальном присваивании q:=n+1 (вместо q:=n). Этот алгоритм удобен, например, когда надо вставить в таблицу новый элемент, не нанося при этом ущерба упорядо­ченности таблицы. Этот алгоритм называется алгоритмом поиска места элемента (до него мы рассматривали алгоритм поиска эле­мента: названия похожи, но не совпадают).

Контрольные вопросы

1. Какие методы поиска данных в массиве Вы знаете?

2. В чем состоит алгоритм прямого перебора?

3. Как выглядит алгоритм бинарного поиска?

4. Как должен быть преобразован массив для организации бинарного поиска?

5. Как определяется быстродействие алгоритма бинарного поиска?

Задачи

1. Изменить программу Loto: как только в качестве номера (т.е. значения переменной b) с клавиатуры указывается отрица­тельное число, выполнение программы должно заканчиваться.

2. Изменить программу Loto: не нужно выводить все выигрыши по отдельности, потребуется вывести суммарный выигрыш, выпавший на все указанные номера. В качестве сигнала об окончании последовательности номеров используется любое отрицательное число (см. предыдущую задачу).

3. Изменить программу Loto, предполагая, что номера в таблице заданы в порядке убывания: а₁ > а₂ >...> а_n.

4. Даны натуральные a₁, ..., a₅₀, т, b₁, .... b_m, (a₁ > а₂ > ... > a₅₀). Подсчитать количество тех b_i , 1 ≤ i ≤ т, для которых нет равных среди а₁, ..., a₅₀.