Учитель информатики МОУ Лицей4 г.Красногорск Пимкина Г.И. - презентация

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

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

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

4 1. Определить количество элементов в последовательности а 81 ……….а

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

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

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

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

9 6. Массив это: 1. поименованный набор фиксированного числа однотипных данных; 2. ограниченная апострофами последовательность любых символов; 3. совокупность разнородных данных, описываемых и обрабатываемых как единое целое; 4. именованный набор однотипных данных на диске; 5. набор переменных, начинающихся с одной буквы

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

11 8. В результате выполнения фрагмента алгоритма m:=a; if m

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

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

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

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

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

17

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

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

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

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

22

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

24 Теперь можно привести текст программы упорядочения массива 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 Решение задачВернутся назад

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

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

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

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

29 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)

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

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

32 '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 Просмотреть решение Вернутся назад Просмотреть решение Вернутся назад 33 Ответьте на вопросы В каком виде отсортирован массив: 1. Альбина, Сергей, Михаил, Петр,… ,34,12, Что такое сортировка? Какие способы сортировки Вы знаете? Для чего необходима сортировка?

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

35 Упражнение 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, добавив название команды. Вернутся назад

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

37 1. Определить количество элементов в массиве а 81 ……….а

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

39 3. Опишите массив: ,2 1. dim a(1 to 5) as real; 2. dim a(1 to 5) as integer; 3. dim a(1 to 5) as single;

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

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

42 6. Массив это: 1. поименованный набор фиксированного числа однотипных данных; 2. ограниченная апострофами последовательность любых символов; 3. совокупность разнородных данных, описываемых и обрабатываемых как единое целое; 4. именованный набор однотипных данных на диске; 5. набор переменных, начинающихся с одной буквы

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

44 8. В результате выполнения фрагмента алгоритма m:=a; if m

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

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