Рабочие листы
к вашим урокам
Скачать
1 слайд
Алгоритмы информационного поиска и сортировки
2 слайд
Задача поиска и ее разновидности
1. Задача поиска состоит в отыскании в некотором массиве элемента (или нескольких элементов) с заданными свойствами.
Рассмотрим задачу определения размера самого маленького яблока из лежащих в ящике
3 слайд
Сделаем из мягкой проволоки рамку размером в любое произвольное яблоко, т. о. мы получили ЭТАЛОН
4 слайд
Берем следующее яблоко и протаскиваем его через рамку.
Если оно не проходит, откладываем.
Если же проходит, то мы уменьшаем рамку до размера этого яблока и продолжаем сравнивать
![Пример. Найти минимальный элемент и индекс в массивеVAR A: array [0..50] of i...](https://documents.infourok.ru/ef576050-9109-4e1c-8efa-86a620f1ed49/0/slide_05.jpg "Пример. Найти минимальный элемент и индекс в массивеVAR A: array [0..50] of i...")
5 слайд
Пример. Найти минимальный элемент и индекс в массиве
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]<min THEN {сравниваем элементы массива с минимальным}
BEGIN
min:=A[i]; nomer:=i
END;
END.
6 слайд
2. Неупорядоченная последовательность
Известно, что все элементы массива имеют разные значения.
Требуется определить номер элемента, значение которого
равно Р (Р может не оказаться в массиве)
Например. Поиск книги на полке. Просматриваем все книги и сравниваем с автором и названием. Когда обнаружим, заполняем место
7 слайд
Основной алгоритм
Пока есть элементы делай
Начало
Сравнить очередной элемент с поисковой переменной
Конец
8 слайд
3. Задача сортировки
а) СОРТИРОВКА ВЫБОРОМ.
Дана последовательность чисел а1, а2, а3, ..аn
Переставим элементы по убыванию от большего к меньшему.
Для этого в массиве выбирается наибольший элемент и ставится на первое место, а первый – на место наибольшего. Затем, начиная со второго эта процедура повторяется.
3
6
-1
4
2
6
3
-1
4
2
6
4
-1
3
2
6
4
3
-1
2
9 слайд
Б) СОРТИРОВКА ОБМЕНОМ
Дана последовательность чисел а1, а2, а3, ..аn Переставим элементы в порядке возрастания.
Для этого сравниваем два соседних элемента аi и аi+1 , если аi > аi+1 , то делается перестановка. Так продолжается до тех пор, пока элементы не будут расположены в порядке возрастания.
10 слайд
в) СОРТИРОВКА ВСТАВКАМИ
Дана последовательность чисел а1, а2, а3, ..аn Переставим элементы в порядке возрастания.
Пусть а1, а2, а3, ..аi - возрастающая последовательность,
Берется число ai+1 и вставляется так, чтобы новая последовательность была также возрастающей. Процесс производится до тех пор, пока все элементы массива не будут перебраны.
11 слайд
Пузырьковая сортировка
(метод обмена)
Элементы расположим в порядке возрастания (от меньшего к большему)
Рассматривая пары элементов и если аi > аi+1 ,то меняем местами элементы массива (метод обмена). В итоге самый большой «всплывет» на последнем месте («пузырек»)
12 слайд
Пример
В=(20, 10, 7, 8, 15, 2)
1 шаг
2 шаг
3 шаг
4 шаг
5 шаг
10 7 8 15 2 20
7 8 10 2 15 20
2 7 8 10 15 20
7 2 8 10 15 20
2 7 8 10 15 20
Сравниваем 20 и 10
20>10 -> меняем 10 и 20 местами
20>8 ->меняем
20>7 -> меняем
![Зададим массив A[1..n]
i:=1
Если i](https://documents.infourok.ru/ef576050-9109-4e1c-8efa-86a620f1ed49/0/slide_13.jpg "Зададим массив A[1..n]
i:=1
Если i")
13 слайд
Зададим массив A[1..n]
i:=1
Если i<n, то перейдем к п.4, иначе к п. 9
j:=1
Если j<n-i, то перейти к п. 6, иначе i-тый шаг выполнен. Перейти к п. 8
Если 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
Сортировка завершена
Пошаговый алгоритм
![Program z1;
Var A: array [1..50] of integer;
i,j,t:integer;
Begin
FOR i:=1 T...](https://documents.infourok.ru/ef576050-9109-4e1c-8efa-86a620f1ed49/0/slide_14.jpg "Program z1;
Var A: array [1..50] of integer;
i,j,t:integer;
Begin
FOR i:=1 T...")
14 слайд
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.
15 слайд
Задачи
Составьте программу сортировки массива заполненного случайными числами по убыванию абсолютных величин (abs(A[i]))
Задан массив А размера N. Перепишите его элементы в массив С в порядке убывания.
Известно, сколько очков заработала каждая из 20 команд в отборочном туре игры КВН. В финал выходят только 5 команд. Выведите на экран очки команд, вышедших в финал.
Рабочие листы
к вашим урокам
Скачать
В презентации разбираются различные способы сортировки массива. Алгоритмы информационного поиска и сортировки образуют отдельные классы алгоритмов, которые имеют ярко выраженную специфику: внешне тривиальные задачи «найти» или «упорядочить» допускают разнообразные решения. Подобные алгоритмы следует разрабатывать с использованием пошаговой детализации. Задача поиска заключается в отыскании в заданной последовательности элемента или нескольких элементов с заданными свойствами. Поиск может быть следующим. A.Поиск минимального элемента последовательности. B.Поиск номера минимального элемента последовательности. C.Поиск максимального элемента и его номера в заданной последовательности. D.Поиск номера элемента последовательности с заданным значением
6 663 436 материалов в базе
Настоящий материал опубликован пользователем Тутынина Ирина Анатольевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс повышения квалификации
36/72 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Курс профессиональной переподготовки
300 ч. — 1200 ч.
Мини-курс
4 ч.
Мини-курс
3 ч.
Мини-курс
4 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.