Алгоритмы информационного поиска и сортировки
Презентацию подготовила учитель информатики МОСШ №3, г. Белоярский Тутынина Ирина Анатольевна
Задача поиска и ее разновидности
1. Задача поиска состоит в отыскании в некотором массиве элемента (или нескольких элементов) с заданными свойствами.
Рассмотрим задачу определения размера самого маленького яблока из лежащих в ящике
Сделаем из мягкой проволоки рамку размером в любое произвольное яблоко, т. о. мы получили ЭТАЛОН
Берем следующее яблоко и протаскиваем его через рамку.
Если оно не проходит, откладываем.
Если же проходит, то мы уменьшаем рамку до размера этого яблока и продолжаем сравнивать
Пример. Найти минимальный элемент и индекс в массиве
VAR A: array [0..50] of integer;
i, min, nomer: integer;
BEGIN
randomize;
FOR i:=1 TO 20 DO
BEGIN
A[i]:=random(50); { заполняем массив случайными числами }
WRITELN (‘A[‘, i, ’]=‘, A[i]);
END;
min:=A[1]; nomer:=1;
FOR i:=2 TO 20 DO
IF A[i] { сравниваем элементы массива с минимальным }
BEGIN
min:=A[i]; nomer:=i
END;
END.
2. Неупорядоченная последовательность
Известно, что все элементы массива имеют разные значения.
Требуется определить номер элемента, значение которого
равно Р (Р может не оказаться в массиве)
Например. Поиск книги на полке. Просматриваем все книги и сравниваем с автором и названием. Когда обнаружим, заполняем место
Основной алгоритм
Пока есть элементы делай
Начало
Сравнить очередной элемент с поисковой переменной
Конец
3. Задача сортировки
а) СОРТИРОВКА ВЫБОРОМ.
Дана последовательность чисел а 1, а 2 , а 3, .. а n
Переставим элементы по убыванию от большего к меньшему.
Для этого в массиве выбирается наибольший элемент и ставится на первое место, а первый – на место наибольшего. Затем, начиная со второго эта процедура повторяется.
3
6
-1
4
2
2
4
-1
3
6
2
6
4
-1
3
6
4
3
-1
2
а i+1 , то делается перестановка. Так продолжается до тех пор, пока элементы не будут расположены в порядке возрастания . " width="640"
Б) СОРТИРОВКА ОБМЕНОМ
Дана последовательность чисел а 1 , а 2 , а 3 , .. а n Переставим элементы в порядке возрастания.
Для этого сравниваем два соседних элемента а i и а i+1 , если а i а i+1 , то делается перестановка. Так продолжается до тех пор, пока элементы не будут расположены в порядке возрастания .
в) СОРТИРОВКА ВСТАВКАМИ
Дана последовательность чисел а 1 , а 2 , а 3 , .. а n Переставим элементы в порядке возрастания.
Пусть а 1 , а 2 , а 3 , .. а i - возрастающая последовательность,
Берется число a i+1 и вставляется так, чтобы новая последовательность была также возрастающей. Процесс производится до тех пор, пока все элементы массива не будут перебраны.
а i+1 , то меняем местами элементы массива (метод обмена). В итоге самый большой «всплывет» на последнем месте («пузырек») " width="640"
Пузырьковая сортировка (метод обмена)
Элементы расположим в порядке возрастания (от меньшего к большему)
Рассматривая пары элементов и если а i а i+1 , то меняем местами элементы массива (метод обмена). В итоге самый большой «всплывет» на последнем месте («пузырек»)
10 - меняем 10 и 20 местами 20 8 - меняем 20 7 - меняем В=(20, 10, 7 , 8 , 1 5, 2) 1 шаг 10 7 8 1 5 2 20 2 шаг 7 8 10 2 1 5 20 3 шаг 7 2 8 10 1 5 20 4 шаг 2 7 8 10 15 20 5 шаг 2 7 8 10 15 20 " width="640"
Пример
Сравниваем 20 и 10
2010 - меняем 10 и 20 местами
20 8 - меняем
20 7 - меняем
В=(20, 10, 7 , 8 , 1 5, 2)
1 шаг
10 7 8 1 5 2 20
2 шаг
7 8 10 2 1 5 20
3 шаг
7 2 8 10 1 5 20
4 шаг
2 7 8 10 15 20
5 шаг
2 7 8 10 15 20
A[j+1], то поменять местами: t:=A[j]; A[j]:=A[j+1]; A[j+1]:=t j:=j+1 , перейти к п. 5 i:=i+1; перейти к п. 3 Сортировка завершена " width="640"
Пошаговый алгоритм
- Зададим массив A[1..n]
- i:=1
- Если i
- j:=1
- Если j
- Если A[j]A[j+1], то поменять местами: t:=A[j]; A[j]:=A[j+1]; A[j+1]:=t
- j:=j+1 , перейти к п. 5
- i:=i+1; перейти к п. 3
- Сортировка завершена
A[j+1] then begin t:=A[j]; A[j]:=A[j+1]; A[j+1]:=t; end; For i:=1 to 20 do write (A[i], ‘ ‘); end. " width="640"
Program z1;
Var A: array [1..50] of integer;
i,j,t:integer;
Begin
FOR i:=1 TO 20 DO
BEGIN
A[i]:=random(50); { заполняем массив случайными числами }
WRITE (A[i],’ ‘);
END;
For i:=1 to 20 do
For j:=1 to 20-i do
If A[j]A[j+1] then
begin
t:=A[j]; A[j]:=A[j+1]; A[j+1]:=t;
end;
For i:=1 to 20 do write (A[i], ‘ ‘);
end.
Задачи
- Составьте программу сортировки массива заполненного случайными числами по убыванию абсолютных величин ( abs(A[i]))
- Задан массив А размера N . Перепишите его элементы в массив С в порядке убывания.
- Известно, сколько очков заработала каждая из 20 команд в отборочном туре игры КВН. В финал выходят только 5 команд. Выведите на экран очки команд, вышедших в финал.