Дать определение сортировки, Дать определение сортировки




НазваниеДать определение сортировки, Дать определение сортировки
Дата конвертации23.07.2013
Размер445 b.
ТипПрактическая работа



Дать определение сортировки,

  • Дать определение сортировки,

  • сформировать умение определять вид массива,

  • отработать навык упорядочения массива.



Актуализация знаний (тест)

  • Актуализация знаний (тест)

  • Объяснение нового материала

  • Закрепление нового материала

  • Практическая работа

  • Домашнее здание

  • Разминка



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

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

  • а81……….а332

  • 332

  • 252

  • 251

  • 330



2. Определить правильную запись описания массива из 20 фамилий учеников 11 А класса

  • 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



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;



  • 4.Выберите тип для описания индекса элемента массива:

      • real;
      • integer;
      • string;
      • single;


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

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

  • K = 0

  • FOR I = 1 TO N

  • IF A(I) > 0 THEN K=K+A(I)

  • NEXT I

    • нахождение суммы всех элементов в массиве
    • нахождение суммы положительных элементов в массиве
    • нахождение количества чисел в массиве
    • нахождение количества положительных элементов в массиве


  • 6. Массив — это:

    • поименованный набор фиксированного числа однотипных данных;
    • ограниченная апострофами последовательность любых символов;
    • совокупность разнородных данных, описываемых и обрабатываемых как единое целое;
    • именованный набор однотипных данных на диске;
    • набор переменных, начинающихся с одной буквы


  • 7. В результате выполнения фрагмента алгоритма

  • FOR i=1 TO 5

  • A(i,2) = 0

  • NEXT i

  • в массиве A, имеющем 5 строк и 5 столбцов, произойдет:

  • обнуление значений по диагонали

  • обнуление всех элементов массива

  • обнуление значений одной строки

  • обнуление значений одного столбца



8. В результате выполнения фрагмента алгоритма

  • 8. В результате выполнения фрагмента алгоритма

  • m:=a; if m

  • if m

  • Будет найдено :

  • минимальное значение 3 элементов

  • максимальное значение 2 элементов

  • максимальное значение 3 элементов

  • минимальное значение 2 элементов

  • никакого значения



  • 9. В фрагменте алгоритма допущена ошибка , укажите ошибку

  • Max=a[i];

  • for i = 2 to 10

  • if Max



  • 10. В результате выполнения фрагмента алгоритма

  • FOR i=1 TO 10

  • B(i)=A(i)

  • NEXT i

  • будут:

    • изменены значения массива A и массива B
    • суммированы значения элементов массивов A и B и записаны в массив A
    • изменяются значения массива B
    • скопированы значения массива A в массив B
    • Проверить тест


Определение сортировки и виды сортировки

  • Определение сортировки и виды сортировки

  • Методы сортировки и критерии алгоритмов сортировки

  • Сортировка методом «Пузырька»

  • Сортировка методом «Отбора»

  • Сортировка массива по возрастанию методом перестановок.

  • Решение задач



Для решения многих задач удобно сначала упорядочить данные по определенному признаку, так можно ускорить поиск некоторого объекта.

  • Для решения многих задач удобно сначала упорядочить данные по определенному признаку, так можно ускорить поиск некоторого объекта.

  • Например, в классном журнале фамилии учеников записаны в алфавитном порядке, удобно проверять

  • Или возьмем любой энциклопедический словарь - статьи в нем упорядочены в алфавитном порядке, удобно искать необходимую информацию.

  • На уроке физкультуры Вас выстраивают по росту. И т. Д.

  • Перегруппирование заданного множества

  • объектов в определенном порядке называют сортировкой.

  • Сортировка — один из наиболее распространенных процессов современной обработки данных.

  • Почему сортировке уделяется большое внимание? Вы это поймете, прочитав цитаты двух великих программистов.

  • "Даже если бы сортировка была почти бесполезна,

  • нашлась бы масса причин заняться ею!

  • Изобретательные методы сортировки говорят о том,

  • что она и сама по себе интересна как объект исследования." /Д. Кнут/

  • "Создается впечатление, что можно построить

  • целый курс программирования, выбирая

  • примеры только из задач сортировки." /Н. Вирт/



Сортировкой называется распределение элементов множества по группам в соответствии с определенными правилами.

  • Сортировкой называется распределение элементов множества по группам в соответствии с определенными правилами.

  • Самыми распространенными являются сортировки по убыванию и по возрастанию

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

  • В обратном порядке по убыванию





Существует несколько методов сортировки массива:

  • Существует несколько методов сортировки массива:

  • сортировка отбором (линейная),

  • сортировка методом пузырька,

  • метод быстрой сортировки с разделением (метод К.Хоора) ,

  • сортировка массива методом перестановок

  • и т.д.



Критерии оценки эффективности алгоритмов сортировки могут включать следующие параметры:

  • Критерии оценки эффективности алгоритмов сортировки могут включать следующие параметры:

  • количество шагов алгоритма, необходимых для упорядочения;

  • количество сравнений элементов;

  • количество перестановок, выполняемых при сортировке.

  • Рассмотрим только простейшие схемы сортировки.



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

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



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

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

  • если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;

  • при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .

  • В результате наибольший элемент оказывается в самом верху массива.

  • Применение метода "пузырька" можно проследить здесь





  • Перед тем как записать программу для сортировки, давайте вспомним следующие задачи.

  • Задача№1. Даны две целочисленные переменные х и y. Составить фрагмент программы, после выполнения которого значения этих переменных распределяются в порядке убывания.

  • Обмен значений переменных нужно производить лишь в том случае, если х<у. Для того чтобы не потерять начальное значение переменной х, введем дополнительную переменную t.

  • if x

  • Задача.№2 Дан массив а, состоящий из 10 элементов. Составить программу поиска максимального элемента массива.

  • Используем идею предыдущей задачи. Перед началом поиска выберем условно в качестве максимального первый элемент массива Max:=a[1]. Затем по очереди каждый элемент массива сравним со значением переменной m. Если он окажется больше, то изменим значение Max. После анализа всех элементов массива переменная Max содержит значение максимального элемента массива.

  • Max:=a[1]; for i := 2 to 10 do   if Max

  • Next i



Теперь можно привести текст программы упорядочения массива M[1..N]:

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



Линейная сортировка (сортировка отбором)

  • Линейная сортировка (сортировка отбором)

  • Идея линейной сортировки по возрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наименьшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива минимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т.д.

  • Применение метода «отбора» можно проследить здесь



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

  • Сортировка массива по возрастанию методом перестановок. Идея алгоритма сортировки по возрастанию массива, состоящего из N элементов, методом перестановок элементов, состоит в последовательном поиске минимальных элементов и их перемещении к началу массива с помощью перестановок с элементами, имеющими меньший индекс.

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

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



Задача №1. Дан список класса из 30 учеников, отсортировать его алфавит .

  • Задача №1. Дан список класса из 30 учеников, отсортировать его алфавит .

  • Данная задача аналогична следующей:

  • Дан строковый массив. Упорядочить его элементы в порядке возрастания.

  • Идея решения: пусть часть массива (по K-й элемент включительно) отсортирована. Нужно найти в неотсортированной части массива минимальный элемент и поменять местами с (K+1)-м



1.Описание массива и величин

  • 1.Описание массива и величин

  • Имя массива a

  • количество элементов 30

  • Тип string

  • Промежуточная величина t – string, индекс I,j-byte

  • 2. Ввод

  • С клавиатуры

  • 3. Сортировка по возрастанию методом «пузырька»

  • 4.Вывод



  • 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

  • Просмотреть решение Вернутся назад



Дан список, в котором указано роста участников команд. Отсортируйте по росту

  • Дан список, в котором указано роста участников команд. Отсортируйте по росту

  • Данная задача аналогична следующей:

  • Дан целочисленный массив. Упорядочить его элементы в порядке убывания.



1.Описание массива и величин

  • 1.Описание массива и величин

  • Имя массива m

  • количество элементов 30

  • Тип byte

  • Промежуточная величина t – byte, индекс I,j-byte

  • 2. Ввод

  • Случайным образом m(i)=int(rnd()*100)

  • 3. Сортировка по убыанию методом «пузырька»

  • 4.Вывод



'program Sortirovka;

  • '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

  • Просмотреть решение Вернутся назад



Ответьте на вопросы

  • Ответьте на вопросы

  • В каком виде отсортирован массив:

  • Альбина, Сергей, Михаил, Петр,…..

  • 56,34,12,........

  • Что такое сортировка?

  • Какие способы сортировки Вы знаете?

  • Для чего необходима сортировка?



Составить программы для решения следующих задач

  • Составить программы для решения следующих задач

  • Даны список футбольных команд и количество очков, набранных каждой командой. Вывести список команд по рейтингу.

  • Дана температура за неделю, найти самый жаркий день и отсортировать по убыванию.

  • Даны список услуг и цены. Отсортировать по ценам.

  • Ответить на вопросы

    • Что называется сортировкой? Какие методы сортировки Вы знаете, опишите их отличия?
    • Что Вы понимаете под поиском?
    • Почему при описании массивов предпочтительнее употреблять константы, а не указывать размеры в явном виде?


Упражнение 1

  • Упражнение 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, добавив название команды.

  •  



Пройдите пожалуйста тест

  • Пройдите пожалуйста тест

  • и узнайте Ваш уровень знаний по информатике.

  • Если готовы нажмите здесь



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

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

  • а81……….а332

  • 332

  • 252

  • 251

  • 330



2. Определить правильную запись описания массива из 20 фамилий учеников 11 А класса

  • 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



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;



  • 4.Выберите тип для описания индекса элемента:

      • real;
      • integer;
      • string;
      • single;


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

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

  • K = 0

  • FOR I = 1 TO N

  • IF A(I) > 0 THEN K=K+A(I)

  • NEXT I

    • нахождение суммы всех элементов в массиве
    • нахождение суммы положительных элементов в массиве
    • нахождение количества чисел в массиве
    • нахождение количества положительных элементов в массиве


  • 6. Массив — это:

    • поименованный набор фиксированного числа однотипных данных;
    • ограниченная апострофами последовательность любых символов;
    • совокупность разнородных данных, описываемых и обрабатываемых как единое целое;
    • именованный набор однотипных данных на диске;
    • набор переменных, начинающихся с одной буквы


  • 7. В результате выполнения фрагмента алгоритма

  • FOR i=1 TO 5

  • A(i,2) = 0

  • NEXT i

  • в массиве A, имеющем 5 строк и 5 столбцов, произойдет:

  • обнуление значений по диагонали

  • обнуление всех элементов массива

  • обнуление значений одной строки

  • обнуление значений одного столбца



  • 8. В результате выполнения фрагмента алгоритма

  • m:=a; if m

  • Будет найдено :

  • минимальное значение 3 элементов

  • максимальное значение 2 элементов

  • максимальное значение 3 элементов

  • минимальное значение 2 элементов

  • никакого значения



  • 9. В фрагменте алгоритма допущена ошибка , укажите ошибку

  • Max=a[i];

  • for i = 2 to 10

  • if Max



  • 10. В результате выполнения фрагмента алгоритма

  • FOR i=1 TO 10

  • B(i)=A(i)

  • NEXT i

  • будут:

    • изменены значения массива A и массива B
    • суммированы значения элементов массивов A и B и записаны в массив A
    • изменяются значения массива B
    • скопированы значения массива A в массив B
    • Вернутся назад


Похожие:

Дать определение сортировки, Дать определение сортировки iconДать определение термину дать определение термину
Источники информации Горизонт земная поверхность, которую мы видим вокруг себя
Дать определение сортировки, Дать определение сортировки iconДать определение икт в образовании. Дать определение икт в образовании
Методы управления образовательным процессом (учебно-воспитательный процесс «Расписание», информационное обеспечение «Библиотека»,...
Дать определение сортировки, Дать определение сортировки iconПрилагательное – дать определение Прилагательное – дать определение
В окончаниях прилагательных после шипящих под ударением пишем букву О, без ударения букву Е!
Дать определение сортировки, Дать определение сортировки iconДать определение понятию вулкан Дать определение понятию вулкан
Основной целью работы является исследование вулканов и вулканизма. В соответствии с поставленной целью в работе рассматриваются следующие...
Дать определение сортировки, Дать определение сортировки iconДать определение логарифма и основного логарифмического тождества Дать определение логарифма и основного логарифмического тождества
Научить видеть знакомое в незнакомом, развить интерес к истории математики и её приложениям
Дать определение сортировки, Дать определение сортировки iconВыяснить: что такое кометы и дать определение. Выяснить: что такое кометы и дать определение
Кометы это небесные тела, которые движутся по вытянутым орбитам и являются частью Солнечной системы
Дать определение сортировки, Дать определение сортировки iconДать определение оксидам, дать определение оксидам

Дать определение сортировки, Дать определение сортировки iconДать определение линейной функции; Дать определение линейной функции

Дать определение сортировки, Дать определение сортировки iconДать определение термину «универсальные учебные действия» (ууд); дать определение термину «универсальные учебные действия» (ууд)
«универсальные учебные действия»; познакомиться с понятием термина «универсальные учебные действия»
Дать определение сортировки, Дать определение сортировки iconДать определение квадратного корня из неотрицательного числа? Дать определение квадратного корня из неотрицательного числа?
«Три пути ведут к знанию: «Три пути ведут к знанию: путь размышления -это путь самый благородный, путь подражания- это путь самый...
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница