Сколько раз отработает цикл?

1.

22 марта 2018

2.

Сколько раз отработает цикл? Чему
равно значение переменной A?
k:=4; a:=2;
repeat
a:=a+1;
k:=k-1;
until k=0;
a:=0;
for i:=1 to 3 do
for j:=1 to 2 do
a:=a+1;

3.

Чему равно значение
переменных a, b?
a:=5;
b:=6;
a:=b;
b:=a;
a=6 b=6
c:=a;
a:=b;
b:=c;

4.

1
A:
2
3
4
5
6
7
12 9 -1 4 47 20 -10
Назовите размерность массива
Назовите индексы нечетных элементов
Найдите a[3]+a[7]
Найдите максимальный элемент и его
индекс

5.

Сортировка
массива

6.

Сортировка массива – расстановка
его элементов в заданном порядке
по возрастанию, убыванию, последней цифре,
сумме делителей, по алфавиту, …
Алгоритмы:
•простые и понятные, но неэффективные
для больших массивов
•сложные, но эффективные

7.

Метод пузырьковый
• Идея: пузырек воздуха в стакане воды
поднимается со дна вверх.
• Для массивов – самый маленький
(«легкий» элемент перемещается вверх
(«всплывает»).

8.

Пузырьковый метод
program Sort;
const n=10;
var a:array[1..n] of
integer;
i,j,c: integer;
begin
{ввод массива}
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then
begin
c:=a[i];
a[i]:= a[j];
a[j]:=c;
end;
{вывод массива}
end.

9.

for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then
begin
c:=a[i];
a[i]:= a[j];
a[j]:=c;
end;

10.

repeat
k:=0;
for i:=1 to n-1 do
if a[i]>a[i+1] then
{сравнение попарно}
begin
c:=a[i];
a[i]:= a[i+1];
a[i+1]:=c;
k:=1;
end;
until k=0;

11.

Метод пузырька с флажком
program SortF;
const n=10;
var a:array[1..n] of
integer;
i,k,c: integer;
begin
{ввод массива}
repeat
k:=0;
for i:=1 to n-1 do
if a[i]>a[i+1] then {сравнение попарно}
begin
c:=a[i];
a[i]:= a[i+1];
a[i+1]:=c;
K:=1;
end;
until k=0;
{вывод массива}

12.

Метод выбора
• Идея: найти минимальный элемент и
поставить его на первое место.
for i:= 1 to N-1 do begin
{найти номер nMin минимального
элемента из A[i]..A[N]}
if i <> nMin then
begin
{поменять местами A[i] и A[nMin]}
end
end;

13.

Алгоритмы:
• простые и понятные, но неэффективные для больших
массивов
время
▫ метод пузырька
работы
▫ метод выбора
• сложные, но эффективные
▫ «быстрая сортировка» (QuickSort)
▫ сортировка «кучей» (HeapSort)
▫ сортировка слиянием (MergeSort)
N
▫ пирамидальная сортировка

14.

Алгоритмизация и программирование, Паскаль, 10 класс
14
Быстрая сортировка
78
L
6
82
67
55
44
34
R
34
6
82
L
67
55
44
R
78
34
6
44
67
L
55
R
82
78
34
6
44
55
R
67
L
82
78
!
L > R : разделение закончено!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

15.

Сравнение методов по времени
N
1000
Метод
пузырька
0,24 с
Метод
выбора
0,12 с
Быстрая
сортировка
0,004 с
5000
5,3 с
2,9 с
0,024 с
15000
45 с
34 с
0,068 с

16.

Домашнее задание
1. Прочитать п.64 учебника
2. Составить трассировочную таблицу
пузырькового метода для 7 элементов
3. Составить трассировочную таблицу метода
пузырька с флажком для 7 элементов
4. Составить программу сортировки методом
выбора
Задания 2-4 по выбору