'

Массивы и сортировка элементов массива.

Понравилась презентация – покажи это...





Слайд 0

Массивы и сортировка элементов массива. Учитель информатики МОУ Лицей№4 г.Красногорск Пимкина Г.И.


Слайд 1

Цель урока Дать определение сортировки, сформировать умение определять вид массива, отработать навык упорядочения массива.


Слайд 2

План урока Актуализация знаний (тест) Объяснение нового материала Закрепление нового материала Практическая работа Домашнее здание Разминка


Слайд 3

Вопрос №1 1. Определить количество элементов в последовательности а81……….а332 332 252 251 330


Слайд 4

Вопрос №2 2. Определить правильную запись описания массива из 20 фамилий учеников 11 А класса DIM FIO(1 to 20) as byte DIM FIO(1 to 20) as integer DIM FIO(1 to 20) as string DIM FIO(1 to 20) as byte


Слайд 5

Вопрос №3 3. Опишите одномерный массив: 2 -9 23 -2 6,2 dim a(1 to 5) as byte; dim a(1 to 5) as integer; dim a(1 to 5) as single;


Слайд 6

Вопрос №4 4.Выберите тип для описания индекса элемента массива: real; integer; string; single;


Слайд 7

Вопрос №5 5. Какой алгоритм описывает последовательность операторов? K = 0 FOR I = 1 TO N IF A(I) > 0 THEN K=K+A(I) NEXT I нахождение суммы всех элементов в массиве нахождение суммы положительных элементов в массиве нахождение количества чисел в массиве нахождение количества положительных элементов в массиве


Слайд 8

Вопрос №6 6. Массив — это: поименованный набор фиксированного числа однотипных данных; ограниченная апострофами последовательность любых символов; совокупность разнородных данных, описываемых и обрабатываемых как единое целое; именованный набор однотипных данных на диске; набор переменных, начинающихся с одной буквы


Слайд 9

Вопрос №7 7. В результате выполнения фрагмента алгоритма FOR i=1 TO 5 A(i,2) = 0 NEXT i в массиве A, имеющем 5 строк и 5 столбцов, произойдет: обнуление значений по диагонали обнуление всех элементов массива обнуление значений одной строки обнуление значений одного столбца


Слайд 10

Вопрос №8 8. В результате выполнения фрагмента алгоритма m:=a; if m<b   then    m:=b if m<c   then    m:=c Будет найдено : минимальное значение 3 элементов максимальное значение 2 элементов максимальное значение 3 элементов минимальное значение 2 элементов никакого значения


Слайд 11

Вопрос №9 9. В фрагменте алгоритма допущена ошибка , укажите ошибку Max=a[i]; for i = 2 to 10 if Max<a[i]     then Max = a[i]


Слайд 12

Вопрос №10 10. В результате выполнения фрагмента алгоритма FOR i=1 TO 10 B(i)=A(i) NEXT i будут: изменены значения массива A и массива B суммированы значения элементов массивов A и B и записаны в массив A изменяются значения массива B скопированы значения массива A в массив B Проверить тест


Слайд 13

Сортировка массивов Определение сортировки и виды сортировки Методы сортировки и критерии алгоритмов сортировки Сортировка методом «Пузырька» Сортировка методом «Отбора» Сортировка массива по возрастанию методом перестановок. Решение задач


Слайд 14

Сортировка массивов Для решения многих задач удобно сначала упорядочить данные по определенному признаку, так можно ускорить поиск некоторого объекта. Например, в классном журнале фамилии учеников записаны в алфавитном порядке, удобно проверять Или возьмем любой энциклопедический словарь - статьи в нем упорядочены в алфавитном порядке, удобно искать необходимую информацию. На уроке физкультуры Вас выстраивают по росту. И т. Д. Перегруппирование заданного множества объектов в определенном порядке называют сортировкой. Сортировка — один из наиболее распространенных процессов современной обработки данных. Почему сортировке уделяется большое внимание? Вы это поймете, прочитав цитаты двух великих программистов. "Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею! Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования." /Д. Кнут/ "Создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки." /Н. Вирт/


Слайд 15

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


Слайд 16

Массив отсортирован по убыванию ? ? ? ? ? 96 80 72 66 48 ? ? ? ? ? 48 66 72 80 96 Массив отсортирован по возрастанию


Слайд 17

Существует несколько методов сортировки массива: сортировка отбором (линейная), сортировка методом пузырька, метод быстрой сортировки с разделением (метод К.Хоора) , сортировка массива методом перестановок и т.д. Методы сортировки массивов


Слайд 18

Методы сортировки массивов Критерии оценки эффективности алгоритмов сортировки могут включать следующие параметры: количество шагов алгоритма, необходимых для упорядочения; количество сравнений элементов; количество перестановок, выполняемых при сортировке. Рассмотрим только простейшие схемы сортировки.


Слайд 19

Сортировка методом "пузырька" Одним из самых популярных методов сортировки – «пузырьковый» метод основан на том, что в процессе исполнения алгоритма более легкие элементы массива постепенно «всплывают». Особенностью данного метода является сравнение не каждого элемента сов семи, а сравнение в парах соседних элементов. Алгоритм пузырьковой сортировки по убыванию состоит в последовательных просмотрах снизу вверх (от начала до конца) массива. Если соседние элементы таковы, что выполняется условие, согласно которому элемент справа больше элемента слева, то выполняется обмен значениями этих элементов.


Слайд 20

Сортировка методом "пузырька" Метод "пузырька" является самым простым методом сортировки. Чтобы уяснить его идею, представьте , что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом: если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами; при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним . В результате наибольший элемент оказывается в самом верху массива. Применение метода "пузырька" можно проследить здесь


Слайд 21


Слайд 22

Задачи на повторение Перед тем как записать программу для сортировки, давайте вспомним следующие задачи. Задача№1. Даны две целочисленные переменные х и y. Составить фрагмент программы, после выполнения которого значения этих переменных распределяются в порядке убывания. Обмен значений переменных нужно производить лишь в том случае, если х<у. Для того чтобы не потерять начальное значение переменной х, введем дополнительную переменную t. if x<y  then begin       t:=x;       x:=y;       y:=t; end;. Задача.№2 Дан массив а, состоящий из 10 элементов. Составить программу поиска максимального элемента массива. Используем идею предыдущей задачи. Перед началом поиска выберем условно в качестве максимального первый элемент массива Max:=a[1]. Затем по очереди каждый элемент массива сравним со значением переменной m. Если он окажется больше, то изменим значение Max. После анализа всех элементов массива переменная Max содержит значение максимального элемента массива. Max:=a[1]; for i := 2 to 10 do   if Max<a[i]     then Max := a[i]; Next i


Слайд 23

Теперь можно привести текст программы упорядочения массива M[1..N]: For j = 1 To N - 1 For i = 1 To N - j If m(i) > m(i + 1) Then    t = m(i) m(i) = m(i + 1) m(i + 1) = t End If Next i Next j Сортировка методом "пузырька" Решение задач Вернутся назад


Слайд 24

Сортировка методом «отбора» Линейная сортировка (сортировка отбором) Идея линейной сортировки по возрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наименьшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива минимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т.д. Применение метода «отбора» можно проследить здесь


Слайд 25

Сортировка массива по возрастанию методом перестановок. Сортировка массива по возрастанию методом перестановок. Идея алгоритма сортировки по возрастанию массива, состоящего из N элементов, методом перестановок элементов, состоит в последовательном поиске минимальных элементов и их перемещении к началу массива с помощью перестановок с элементами, имеющими меньший индекс. Рассмотрим этот метод. На первом шаге находим минимальный элемент массива и меняем его местами с первым элементом массива. Остаются неупорядоченными N-1 элемент. Проводим поиск минимального элемента среди элементов со 2 по N-1 и делаем перестановку. Повторяем процедуру поиска минимального элемента среди оставшихся неупорядоченных элементов многократно. Повторение реализуем с помощью цикла со счетчиком, максимальное значение которого составляет N-1. В результате массив сортируется по возрастанию.


Слайд 26

Решение задач Задача №1. Дан список класса из 30 учеников, отсортировать его алфавит . Данная задача аналогична следующей: Дан строковый массив. Упорядочить его элементы в порядке возрастания. Идея решения: пусть часть массива (по K-й элемент включительно) отсортирована. Нужно найти в неотсортированной части массива минимальный элемент и поменять местами с (K+1)-м


Слайд 27

Решение 1.Описание массива и величин Имя массива a количество элементов 30 Тип string Промежуточная величина t – string, индекс I,j-byte 2. Ввод С клавиатуры 3. Сортировка по возрастанию методом «пузырька» 4.Вывод


Слайд 28

Задача №1 Private Sub Command1_Click() 'program Sortirovka; Dim N, I, J As Integer Dim a(1 To 30) As String Dim t As String   N = InputBox("Введите количество элементов: ", "") For I = 1 To N a(I) = InputBox("Введите фамилию", "") Next I Print For j = 1 To N-1 For i = 1 To N-j If a(i)<=a(i+1)Then t = a(I) a(I) = a(i+1) a(i+1) = t Next I Next J   For I = 1 To N Print a(I); " "; Next I  End Sub Просмотреть решение Вернутся назад


Слайд 29

Задача №2 Дан список, в котором указано роста участников команд. Отсортируйте по росту Данная задача аналогична следующей: Дан целочисленный массив. Упорядочить его элементы в порядке убывания.


Слайд 30

Решение 1.Описание массива и величин Имя массива m количество элементов 30 Тип byte Промежуточная величина t – byte, индекс I,j-byte 2. Ввод Случайным образом m(i)=int(rnd()*100) 3. Сортировка по убыанию методом «пузырька» 4.Вывод


Слайд 31

Задача №2 'program Sortirovka; Dim N, I, J, K As Integer Dim m(0 To 30) As byte Dim t As byte N = Input Box("Введите количество элементов: ", "") For I = 1 to N m(I) = int(rnd()*60+140) Next I Print For j = 1 To N – 1 For i= 1To N-j If m(i) < m(i + 1) Then    t = m(i) m(i) = m(i + 1) m(i + 1) = t End If Next i Next j For I = 1 To N Print m(I); " "; Next I Просмотреть решение Вернутся назад


Слайд 32

Закрепление материала Ответьте на вопросы В каком виде отсортирован массив: Альбина, Сергей, Михаил, Петр,….. 56,34,12,........ Что такое сортировка? Какие способы сортировки Вы знаете? Для чего необходима сортировка?


Слайд 33

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


Слайд 34

Практическая работа Упражнение 1 Запустите интегрированную среду программирования. Введите текст программы Sortirovka и запишите файл на диск под соответствующим именем. Несколько раз запустите программу на исполнение. Просматривая экран пользователя, убедитесь, что всякий раз в программе упорядоченный набор данных Упражнение 2. Исправить программу Sortirovka, для задачи 2. Задача 2. Дан целочисленный массив. Отсортировать его по убыванию   Тест: N = 10; элементы массива - 1, 2, 2, 2, -1, 1, 0, 34, 3, 3. Ответ: -1, -1, 0, 1, 2, 2, 2, 3, 3, 34. Упражнение 3. Исправить программу Sortirovka, добавив название команды.   Вернутся назад


Слайд 35

Разминка Пройдите пожалуйста тест и узнайте Ваш уровень знаний по информатике. Если готовы нажмите здесь


Слайд 36

Тест Вопрос №1 1. Определить количество элементов в массиве а81……….а332 332 252 251 330


Слайд 37

Тест Вопрос №2 2. Определить правильную запись описания массива из 20 фамилий учеников 11 А класса DIM FIO(1 .. 20) as string DIM FIO(1 to 20) as integer DIM FIO(1 to 20) as string DIM FIO(1 to 20) as byte


Слайд 38

Тест Вопрос №3 3. Опишите массив: 2 -9 23 -2 6,2 dim a(1 to 5) as real; dim a(1 to 5) as integer; dim a(1 to 5) as single;


Слайд 39

Тест Вопрос №4 4.Выберите тип для описания индекса элемента: real; integer; string; single;


Слайд 40

Тест Вопрос №5 5. Какой алгоритм описывает последовательность операторов? K = 0 FOR I = 1 TO N IF A(I) > 0 THEN K=K+A(I) NEXT I нахождение суммы всех элементов в массиве нахождение суммы положительных элементов в массиве нахождение количества чисел в массиве нахождение количества положительных элементов в массиве


Слайд 41

Тест Вопрос №6 6. Массив — это: поименованный набор фиксированного числа однотипных данных; ограниченная апострофами последовательность любых символов; совокупность разнородных данных, описываемых и обрабатываемых как единое целое; именованный набор однотипных данных на диске; набор переменных, начинающихся с одной буквы


Слайд 42

Тест Вопрос №7 7. В результате выполнения фрагмента алгоритма FOR i=1 TO 5 A(i,2) = 0 NEXT i в массиве A, имеющем 5 строк и 5 столбцов, произойдет: обнуление значений по диагонали обнуление всех элементов массива обнуление значений одной строки обнуление значений одного столбца


Слайд 43

Тест Вопрос №8 8. В результате выполнения фрагмента алгоритма m:=a; if m<b   then     m:=b; if m<c   then     m:=c; Будет найдено : минимальное значение 3 элементов максимальное значение 2 элементов максимальное значение 3 элементов минимальное значение 2 элементов никакого значения


Слайд 44

Тест Вопрос №9 9. В фрагменте алгоритма допущена ошибка , укажите ошибку Max=a[i]; for i = 2 to 10 if Max<a[i]     then Max = a[i]


Слайд 45

Тест Вопрос №10 10. В результате выполнения фрагмента алгоритма FOR i=1 TO 10 B(i)=A(i) NEXT i будут: изменены значения массива A и массива B суммированы значения элементов массивов A и B и записаны в массив A изменяются значения массива B скопированы значения массива A в массив B Вернутся назад


×

HTML:





Ссылка: