Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Презентации / Презентация по информатике. Программирование. Методы сортировки массивов. Линейная сортировка.

Презентация по информатике. Программирование. Методы сортировки массивов. Линейная сортировка.


  • Информатика

Поделитесь материалом с коллегами:

МЕТОДЫ СОРТИРОВКИ МАССИВОВ ЛИНЕЙНАЯ СОРТИРОВКА Кондраткова Татьяна Алексеевна...
УСЛОВИЯ ИГРЫ 	Шары с написанными на них числами лежат в последовательных ячей...
ИСПОЛНИТЕЛЬ - РОБОТ Система команд исполнителя и элементарные действия сравни...
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1 Горит зелёный свет ИСХОДНОЕ...
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1 Начинается перестановка шаро...
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 7 5 4 12 10 1 23 Проверка лампочки Робот доше...
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 7 5 4 12 10 1 23 Зажечь зелёный свет Начинает...
АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 2 1 4 3 5 7 10 12 23 Горит зелёный свет Проверка...
ФОРМАЛИЗАЦИЯ АЛГОРИТМА Ограничения, наложенные на действия робота, однозначно...
ФОРМАЛИЗАЦИЯ АЛГОРИТМА Сортировка происходит за несколько проходов по массиву...
Описание переменных 	program linsort; 		{заголовок программы, не обязателен}...
Порядок работы: Разработка, отладка и тестирование программы: Программа должн...
РАЗРАБОТКА АЛГОРИТМА ЛИНЕЙНАЯ СОРТИРОВКА (массив целых чисел сортируется по н...
Блок формирования массива BEGIN Write(’ N= ’); ReadLn(N); FOR I:=1 TO N DO 	b...
Блок печати массива WriteLn; FOR I:=1 TO N DO Write(A[ I ] , ’ ’); WriteLn;
АЛГОРИТМ ЛИНЕЙНОЙ СОРТИРОВКИ
ОСНОВНАЯ ЧАСТЬ ПРОГРАММЫ Repeat F:=0; FOR I:=1 TO N-1 DO IF A[I]>A[I+1] THEN...
После завершения сортировки ещё раз вывести на экран значения элементов масси...
Куда ставить счётчики? CS:=0; CP:=0; Repeat F:=0; FOR I:=1 TO N-1 DO begin...
Внимание! Переменные-счётчики нужны только для проведения эксперимента. Они н...
1 из 29

Описание презентации по отдельным слайдам:

№ слайда 1 МЕТОДЫ СОРТИРОВКИ МАССИВОВ ЛИНЕЙНАЯ СОРТИРОВКА Кондраткова Татьяна Алексеевна
Описание слайда:

МЕТОДЫ СОРТИРОВКИ МАССИВОВ ЛИНЕЙНАЯ СОРТИРОВКА Кондраткова Татьяна Алексеевна ГБОУ Лицей № 82 СПб

№ слайда 2 УСЛОВИЯ ИГРЫ 	Шары с написанными на них числами лежат в последовательных ячей
Описание слайда:

УСЛОВИЯ ИГРЫ Шары с написанными на них числами лежат в последовательных ячейках. Имеется одна пустая вспомогательная ячейка. Робот находится у начала ряда и должен упорядочить шары по возрастанию чисел слева направо. Робот может: сравнить два соседних числа, перейти на одну ячейку вправо, взять один шар во вспомогательную ячейку, положить шар из вспомогательной ячейки в свободную ячейку ряда, сдвинуть шар на одну позицию в свободную ячейку ряда, переместиться в исходное положение к началу ряда. Когда робот находится в исходном положении, у него зажигается зеленая лампочка, и он начинает работу. Если робот переложил хотя бы один шар, то зажигается красная лампочка. Робот отключается, если в конечном положении у него горит зеленая лампочка иначе (горит красная лампочка) возвращается к началу ряда и продолжает работу.

№ слайда 3 ИСПОЛНИТЕЛЬ - РОБОТ Система команд исполнителя и элементарные действия сравни
Описание слайда:

ИСПОЛНИТЕЛЬ - РОБОТ Система команд исполнителя и элементарные действия сравнить два соседних числа, перейти на одну ячейку вправо, взять один шар во вспомогательную ячейку, положить шар из вспомогательной ячейки в свободную ячейку ряда, сдвинуть шар на одну позицию в свободную ячейку ряда, переместиться в исходное положение к началу ряда.

№ слайда 4 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1 Горит зелёный свет ИСХОДНОЕ
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1 Горит зелёный свет ИСХОДНОЕ ПОЛОЖЕНИЕ – робот в начале массива.

№ слайда 5 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1 Начинается перестановка шаро
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1 Начинается перестановка шаров - Зажигается красный свет

№ слайда 6 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1

№ слайда 7 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1

№ слайда 8 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1

№ слайда 9 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1

№ слайда 10 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1

№ слайда 11 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1

№ слайда 12 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1

№ слайда 13 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1

№ слайда 14 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 12 5 7 4 23 10 1

№ слайда 15 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 7 5 4 12 10 1 23 Проверка лампочки Робот доше
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 7 5 4 12 10 1 23 Проверка лампочки Робот дошел до конца (сравнил все пары) Горит красный свет

№ слайда 16 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 7 5 4 12 10 1 23 Зажечь зелёный свет Начинает
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 3 2 7 5 4 12 10 1 23 Зажечь зелёный свет Начинается новый проход

№ слайда 17 АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 2 1 4 3 5 7 10 12 23 Горит зелёный свет Проверка
Описание слайда:

АЛГОРИТМ РАБОТЫ ИСПОЛНИТЕЛЯ 2 1 4 3 5 7 10 12 23 Горит зелёный свет Проверка лампочки СОРТИРОВКА ЗАВЕРШЕНА! Робот дошел до конца (сравнил все пары)

№ слайда 18 ФОРМАЛИЗАЦИЯ АЛГОРИТМА Ограничения, наложенные на действия робота, однозначно
Описание слайда:

ФОРМАЛИЗАЦИЯ АЛГОРИТМА Ограничения, наложенные на действия робота, однозначно приводят к алгоритму метода линейной сортировки. Запишите числа исходного ряда на бумаге и опишите алгоритм сортировки используя следующие обозначения: сравнение чисел - двойная стрелка сверху, перестановке чисел - двойная стрелка снизу . Вместо лампочки введите переменную-счетчик, при каждой перестановке переписывайте

№ слайда 19 ФОРМАЛИЗАЦИЯ АЛГОРИТМА Сортировка происходит за несколько проходов по массиву
Описание слайда:

ФОРМАЛИЗАЦИЯ АЛГОРИТМА Сортировка происходит за несколько проходов по массиву А (в данном случае 9 проходов) Пусть N количество элементов в массиве. Флаговая переменная (счётчик) F устанавливается в нуль в начале каждого прохода F:=0 . Переменная цикла I меняется от 1 до N-1 (Цикл с параметром). В цикле сравниваются два соседних элемента (первый и второй, второй и третий,… предпоследний и последний) A[I] и A[I+1]. Если значения элементов стоят не в порядке сортировки, то элементы меняются местами. L дополнительная переменная для обмена. Обмен происходит в три действия: L:=A[I+1]; A[I+1]:=A[I]; A[I]:=L; При каждой перестановке значение переменной F увеличивается на единицу. F:= F+1 (Условный оператор). В конце каждого прохода проверяется значение переменной F. Если F=0, то сортировка завершена, иначе делается ещё один проход (Цикл с постусловием).

№ слайда 20 Описание переменных 	program linsort; 		{заголовок программы, не обязателен}
Описание слайда:

Описание переменных program linsort; {заголовок программы, не обязателен} TYPE {секция описания типов} MASS= array [1..30] of integer; {объявляется тип} var {секция описания переменных} N:1..30; {размер массива } A: MASS; {массив из N целых чисел} I:1..30; {переменная цикла } L:integer; {переменная для обмена} F:0..30; {флаговая переменная} CS: integer; {счётчик числа сравнений} CP: integer; {счётчик числа перестановок}

№ слайда 21 Порядок работы: Разработка, отладка и тестирование программы: Программа должн
Описание слайда:

Порядок работы: Разработка, отладка и тестирование программы: Программа должна: Сформировать массив (ввод данных с клавиатуры); Вывести массив на экран для просмотра данных; Произвести сортировку массива по алгоритму «Линейная сортировка»; Вывести массив на экран для просмотра результата. После того, как Вы убедились, что программа работает правильно Определить эффективность метода: Поставить счётчики в программу; Запустить программу на выполнение; Снять показания счётчиков на первом входном массиве; Записать показания счётчиков в бланк лабораторной работы; Запустить программу и снять показания счётчиков на втором и третьем входных массивах. Описать дополнительное рабочее поле ОЗУ в бланке лабораторной работы.

№ слайда 22 РАЗРАБОТКА АЛГОРИТМА ЛИНЕЙНАЯ СОРТИРОВКА (массив целых чисел сортируется по н
Описание слайда:

РАЗРАБОТКА АЛГОРИТМА ЛИНЕЙНАЯ СОРТИРОВКА (массив целых чисел сортируется по не убыванию элементов)

№ слайда 23 Блок формирования массива BEGIN Write(’ N= ’); ReadLn(N); FOR I:=1 TO N DO 	b
Описание слайда:

Блок формирования массива BEGIN Write(’ N= ’); ReadLn(N); FOR I:=1 TO N DO begin Write(’ A[ ’ , I , ’ ]= ’); ReadLn(A[ I ]) end;

№ слайда 24 Блок печати массива WriteLn; FOR I:=1 TO N DO Write(A[ I ] , ’ ’); WriteLn;
Описание слайда:

Блок печати массива WriteLn; FOR I:=1 TO N DO Write(A[ I ] , ’ ’); WriteLn;

№ слайда 25 АЛГОРИТМ ЛИНЕЙНОЙ СОРТИРОВКИ
Описание слайда:

АЛГОРИТМ ЛИНЕЙНОЙ СОРТИРОВКИ

№ слайда 26 ОСНОВНАЯ ЧАСТЬ ПРОГРАММЫ Repeat F:=0; FOR I:=1 TO N-1 DO IF A[I]>A[I+1] THEN
Описание слайда:

ОСНОВНАЯ ЧАСТЬ ПРОГРАММЫ Repeat F:=0; FOR I:=1 TO N-1 DO IF A[I]>A[I+1] THEN begin L:=A[I+1]; A[I+1]:=A[I]; A[I]:=L; F:=F+1; end; Until F=0;

№ слайда 27 После завершения сортировки ещё раз вывести на экран значения элементов масси
Описание слайда:

После завершения сортировки ещё раз вывести на экран значения элементов массива, чтобы проверить, что сортировка прошла успешно. WriteLn; FOR I:=1 TO N DO Write(A[ I ] , ’ ’); ReadLn; END. { конец программы}

№ слайда 28 Куда ставить счётчики? CS:=0; CP:=0; Repeat F:=0; FOR I:=1 TO N-1 DO begin
Описание слайда:

Куда ставить счётчики? CS:=0; CP:=0; Repeat F:=0; FOR I:=1 TO N-1 DO begin CS:=CS+1; IF A[I]>A[I+1] THEN begin CP:=CP+3; L:=A[I+1]; A[I+1]:=A[I]; A[I]:=L; F:=F+1; end; end; Until F=0; WriteLn(’ CS=’ ,CS); WriteLn(’ CP=’ ,CP); Обнулить счётчики до начала сортировки Увеличить на 1 значение счётчика числа сравнений Увеличить на 3 значение счётчика числа перестановок Обратите внимание на то, что после добавления оператора в тело цикла с параметром необходимо поставить операторные скобки. Вывести на экран значения счётчиков после завершения сортировки

№ слайда 29 Внимание! Переменные-счётчики нужны только для проведения эксперимента. Они н
Описание слайда:

Внимание! Переменные-счётчики нужны только для проведения эксперимента. Они не влияют на алгоритм сортировки и во время сортировки не задействованы. Эти переменные не должны учитываться как дополнительная рабочая память.


Автор
Дата добавления 25.11.2015
Раздел Информатика
Подраздел Презентации
Просмотров227
Номер материала ДВ-191761
Получить свидетельство о публикации

Похожие материалы

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