Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Дисциплины "ЯЗЫКИ ПРОГРАММИРОВАНИЯ" "ПРОГРАММИРОВАНИЕ" Примеры алгоритмов обработки массивов

План лекции © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 1. Задача сортировки и алгоритмы ее решения 1.1. Мера упорядоченности последовательности 1.2. Задача сортировки 1.3. Алгоритм сортировки выбором 1.4. Алгоритм сортировки вставками 1.5. Алгоритм сортировки методом пузырька 2. Задача поиска простых чисел в заданном диапазоне 2.1. Линейный алгоритм 2.2. Алгоритм Эратосфена

Задача сортировки и алгоритмы ее решения © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3

Мера упорядоченности последовательности © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

Количественная мера упорядоченности © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 5 Инверсией элементов i и j последовательности a называется ситуация, когда a[i] > a[j] и i < j a[4] = 29, a[9] = 8: 4 8. Общее количество инверсией определяет степень упорядоченности последовательности. Для вычисления этого показателя элементы последовательности перебираются слева направо, для каждого элемента вычисляется количество его инверсий с элементами, расположенными правее.

Количественная мера упорядоченности (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ) a[1] – a[3] : количество инверсий 0; 2) a[4] = 29: инверсии с элементами a[5] – a[9] = 5; 3) a[5] – a[8]: инверсия с элементом a[9], в сумме = 4; 4) a[9]: инверсий нет. 5) a[10]: инверсий нет. Итого: 9 инверсий.

Мера упорядоченности последовательности © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» абсолютное: 16 инверсий относит: 0,356 абсолютное: 0 инверсий относит: 0 абсолютное: 9 инверсий относит: 0,2 абсолютное: 24 инверсий относит: 0,533 абсолютное: 45 инверсий относит: 1

Задача сортировки (sorting problem) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 Дано: последовательность из n чисел a 1, a 2, a 3, …, a n Необходимо: переставить элементы последовательности так, чтобы для любых элементов новой последовательности a' 1, a' 2, a' 3, …, a' n выполнялось соотношение: a' 1 a' 2 a' 3 … a' n (сортировка по возрастанию) Алгоритм сортировки выбором

© Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Суть алгоритма заключается в последовательном формировании упорядоченной последовательности слева направо. На каждом шаге рассматривается фрагмент массива c i по n-й элементы. Среди них выбирается наименьший, который занимает первое место диапазона (на место i-го элемента). При этом i-й элемент перемещается на позицию, в которой найден минимум: После этого считается, что элементы массива с 1 по i отсортированы. Поэтому далее процедура повторяется для диапазона элементов с i+1 по n.

Алгоритм сортировки выбором (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» i = 1, min(a[k], k = i…n) = 2 inv = 22 i = 2, min(a[k], k = i…n) = 4 inv = i = 3, min(a[k], k = i…n) = 5 inv = i = 4, min(a[k], k = i…n) = 6 inv = i = 5, min(a[k], k = i…n) = 7 inv = i = 6, min(a[k], k = i…n) = 10 inv = 4

Алгоритм сортировки выбором (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» i = 7, min(a[k], k = i…n) = 15 inv = i = 8, min(a[k], k = i…n) = 17 inv = i = 9, min(a[k], k = i…n) = 19 inv = i = 6, min(a[k], k = i…n) = 10 inv = 4

Проход алгоритма сортировки выбором © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» i = 3, min(a[k], k = i…n) = 5 Основной подзадачей, возникающей в процессе сортировки, является поиск индекса минимального элемента в диапазоне с i по n (в примере на рис. диапазон – с 3 по 10). Для решения этой задачи можно воспользоваться уже известным алгоритмом поиска минимального элемента: m i, k i + 1 while k n do if a[k] < a[m] then m k k k + 1 t a[i], a[i] a[m], a[m] t Приведенный фрагмент называется "проходом" данного алгоритма.

Алгоритм сортировки выбором (4) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 13 После каждого прохода алгоритма сортировки выбором размер отсортированной части увеличивается на 1 элемент: Поэтому, учитывая, что на последнем проходе рассматривается один элемент, количество проходов составляет n –

Алгоритм сортировки выбором (псевдокод) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 14 i 1 while i < n do m i, k i + 1 while k n do if a[k] < a[m] then m k k k + 1 t a[i], a[i] a[m], a[m] t i i + 1 Учитывая, что на последнем проходе рассматривается один элемент, количество проходов для получения полностью отсортированной последовательности составляет n – 1.

Алгоритм сортировки вставками © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 15 Суть данного алгоритма (аналогично предыдущему) заключается в последовательном формировании упорядоченной последовательности слева направо. Однако, в отличие от сортировки вставками, основная работа осуществляется в отсортированной части массива. На каждом шаге имеется отсортированная часть последовательности с 1 по (i – 1) и не отсортированная – с i по n элементы. Для первого не отсортированного элемента с номером i в отсортированной части ищется подходящая позиция, как показано на рисунке:

Алгоритм сортировки вставками (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» inv = 22 inv = 20 inv = 18 inv = 14 inv = 8 inv = 7 inv = 0 inv = 7

Проход алгоритма сортировки вставками © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» t 6 Основной подзадачей, возникающей в процессе сортировки, является поиск для очередного элемента правильного места в уже отсортированной части массива и вставка его на эту позицию. Решение этой задачи можно разбить на следующие шаги: 1. Поиск индекса подходящей позиции k для элемента a[i]. 2. Запоминание элемента a[i] во временной ячейке t: t = a[i]. 3. Сдвиг элементов a[k], a[k+1], …, a[i–1] на один элемент вправо, т.е. в ячейки a[k+1], a[k+2], …, a[i] соответственно. 4. Поместить значение из ячейки t в a[k]: a[k] = t

Проход алгоритма сортировки вставками (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Поиск индекса подходящей позиции k для элемента a[i]. 2. Запоминание элемента a[i] во временной ячейке t: t = a[i]. 3. Сдвиг элементов a[k], a[k+1], …, a[i–1] на один элемент вправо, т.е. в ячейки a[k+1], a[k+2], …, a[i] соответственно. 4. Поместить значение из ячейки t в a[k]: a[k] = t. На практике поиск элемента часто объединяют со сдвигом элементов: a[5] > a[4] => сдвиг не нужен t = a[5] 1) t < a[4], сдвиг: a[5] = a[4]; 2) t < a[3], сдвиг: a[3] = a[4]; 3) t > a[2], стоп: a[3] = t; t 9

Проход алгоритма сортировки вставками (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 19 Псевдокод одного прохода алгоритма сортировки вставками выглядит следующим образом: t a[i], k i – 1 while k 1 и a[k] > t do a[k+1] a[k] k k – 1 a[k+1] t Приведенный фрагмент называется "проходом" данного алгоритма k = 5 a[6] = a[5] k = 4 a[5] = a[4] k = 3 a[4] = a[3] k = 2 a[3] = t

Алгоритм сортировки вставками (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 20 Таким образом для сортировки всей последовательности требуется n – 1 проход. После каждого прохода алгоритма сортировки выбором размер отсортированной части увеличивается на 1 элемент:

Алгоритм сортировки вставками (псевдокод) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 21 i 2 while i < n do t a[i], k i – 1 while k 1 и a[k] > t do a[k+1] a[k] k k – 1 a[k+1] t Таким образом для сортировки всей последовательности требуется n – 1 проход. t a[i], k i – 1 while k 1 и a[k] > t do a[k+1] a[k] k k – 1 a[k+1] t

Алгоритм сортировки методом пузырька © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 22 Суть данного заключается в том, что на каждом проходе определяется наибольший элемент, который выводится на последнее место рассматриваемой подпоследовательности и исключается из дальнейшего рассмотрения. Важным отличием данного алгоритма от ранее рассмотренных является то, что в процессе выведения наибольшего элемента участвуют все элементы и количество инверсий сокращается более, чем на вклад наибольшего элемента. Проход алгоритма заключается в попарном сравнении соседних элементов и устранении "локальных" инверсий. В результате такого прохода наибольший элемент (пузырек наибольшего размера) выдвигается в крайнюю правую позицию

Проход алгоритма сортировки методом пузырька © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» inv = 22 inv = 17

Алгоритм сортировки методом пузырька (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» inv = 22 inv = 17 inv = inv = inv = inv = inv = 1

Алгоритм сортировки методом пузырька (4) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» inv = inv = inv = inv = 0 Особенностью алгоритма сортировки методом пузырька является то, что существует возможность досрочного прекращения сортировки при условии, что на очередном проходе не было выполнено ни одного обмена.

Проход алгоритма сортировки методом пузырька (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 26 j 1 while j (n – i) do if a[k+1] < a[k] then t a[k+1] a[k+1] a[k] a[k] t j j

Алгоритм сортировки методом пузырька (5) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 27 Таким образом для сортировки всей последовательности требуется n – 1 проход. После каждого прохода алгоритма сортировки методом пузырька наибольший размер отсортированной правой части увеличивается на 1 элемент: inv = 22 inv = inv = 0

Алгоритм сортировки методом пузырька (псевдокод) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 28 i = 1 while i < n – 1 do j 1 while j (n – i) do if a[k+1] < a[k] then t a[k+1] a[k+1] a[k] a[k] t j j + 1 Таким образом для сортировки всей последовательности требуется n – 1 проход. j 1 while j (n – i) do if a[k+1] < a[k] then t a[k+1] a[k+1] a[k] a[k] t j j + 1

Алгоритм сортировки методом пузырька c досрочным выходом (псевдокод) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 29 i = 1, f 1 while i 0 do j 1, f 0 while j (n – i) do if a[k+1] < a[k] then t a[k+1] a[k+1] a[k] a[k] t f 1 j j + 1 Таким образом для сортировки всей последовательности требуется n – 1 проход.

Задача поиска простых чисел в заданном диапазоне © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 30

Простые числа © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 31 Простое число – это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Примеры простых чисел: 2, 13, 59, 101, 431, 733, 1153, 2069 и др. Все остальные натуральные числа, кроме единицы, называются составными. Все натуральные числа больше единицы разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел. Список первых 500 простых чисел:

Задача поиска простых чисел в заданном диапазоне © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» n–1nn+1... Дан диапазон натуральных чисел [2, N]. Требуется выбрать из него только те числа, которые являются простыми: N n–1nn+1...N

Линейный алгоритм поиска простых чисел в заданном диапазоне © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» n–1nn+1...N Наиболее простым алгоритмом решения задачи является перебор всех чисел диапазона [2, N] и проверка каждого из них на простоту линейным алгоритмом. Для того, чтобы проверить, является ли число x простым достаточно проверить, делится ли оно на одно из чисел диапазона [2, x/2]. Упрощенный вариант этого алгоритма уже рассматривался при изучении циклов. Числа, прошедшие проверку на простоту могут быть помещены в специально отведенный для этого массив, размерность которого совпадает с исходным (пессимистическое выделение памяти).

Проверка на простоту © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 34 j [х/2] ДА НЕТ j = 2, f = 0 f = f или (x mod j 0) j = j + 1 f = f или (x mod j 0) j = j + 1 не f... x – целое число, которое проверяется на простоту. На каждой итерации проверяется потенциальный делитель j [2, [x /2] ]. Если x mod j = 0 (делится нацело), то переменная-флаг f = 1. На выходе значение флага f определяет результат: если f = 0 ((не f ) = 1), то среди чисел диапазона [2, [x /2] ] не нашлось ни одного делителя – число простое. иначе f = 1 ((не f )= 0) – число составное.

Проверка на простоту (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 35 j [х/2] ДА НЕТ j = 2, f = 0 f = f или (x mod j 0) j = j + 1 f = f или (x mod j 0) j = j + 1 не f... На выходе значение флага f определяет результат: если f = 0 ((не f ) = 1), то среди чисел диапазона [2, [x /2] ] не нашлось ни одного делителя – число простое. иначе f = 1 ((не f )= 0) – число составное j [2, [x /2] ]

Линейный алгоритм поиска простых чисел в заданном диапазоне © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 36 x 2, n 0 // x – проверяемые числа, n – счетчик простых чисел while x N do // j – потенциальные делители, f – флаг, 0 => простое число j 2, f 0 while j (x div 2) do if (x mod j = 0) then // если x делится на j – x не простое! f 1 j j + 1 // перейти к следующему делителю if f = 0 then // если флаг f = 0, то x – простое число n n + 1 // счетчик n – первый свободный элемент primes[n] x x x + 1 Как исключить ненужные операции?

Пути оптимизации © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Если обнаружен хотя бы один делитель, число уже не является простым и дальнейшую проверку проводить не требуется. 2. Чтобы проверяемое число было простым достаточно, чтобы оно не делилось ни на одно из ранее найденных простых чисел.

Линейный алгоритм поиска простых чисел в заданном диапазоне (версия 2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 38 x 2, n 0 // x – проверяемые числа, n – счетчик простых чисел while x N do // j – потенциальные делители, f – флаг, 0 => простое число j 2, f 0 while j (x div 2) и f 1 do if (x mod j = 0) then // если x делится на j – x не простое! f 1 j j + 1 // перейти к следующему делителю if f = 0 then // если флаг f = 0, то x – простое число n n + 1 // счетчик n – первый свободный элемент primes[n] x x x + 1

Линейный алгоритм поиска простых чисел в заданном диапазоне (версия 3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 39 x 2, n 0 // x – проверяемые числа, n – счетчик простых чисел while x N do // j – потенциальные делители, f – флаг, 0 => простое число j 1, f 0 while j n и f 1 do if (x mod primes[j] = 0) then f 1 j j + 1 // перейти к следующему делителю if f = 0 then // если флаг f = 0, то x – простое число n n + 1 // счетчик n – первый свободный элемент primes[n] x x x + 1

Решето Эратосфена © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 40 Решето Эратосфена алгоритм нахождения всех простых чисел до некоторого целого числа N, который приписывают древнегреческому математику Эратосфену Киренскому. 1.Выписать подряд все целые числа от двух до N (2, 3, 4, …, N). 2.Пусть переменная p изначально равна двум – первому простому числу. 3.Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …). 4.Найти первое незачеркнутое число в списке, большее чем p, и присвоить значению переменной p это число. 5.Повторять шаги 3 и 4, пока незачеркнутое число есть.

Решето Эратосфена. Алгоритм © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Выписать подряд все целые числа от двух до N (2, 3, 4, …, N). 2. Пусть переменная p = 2 (первому простому числу). 3. Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …). 4. Найти первое незачеркнутое число в списке, большее чем p, и присвоить значению переменной p это число: p = Повторять шаги 3 и 4, пока незачеркнутое число есть … N step= … N 2*step 3*step 4*step 5*step 6*step 7*step

Решето Эратосфена. Алгоритм © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Выписать подряд все целые числа от двух до N (2, 3, 4, …, N). 2. p = 3 3. Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …). 4. Найти первое незачеркнутое число в списке, большее чем p, и присвоить значению переменной p это число: p = Повторять шаги 3 и 4, пока незачеркнутое число есть … N step= … N 2*step3*step4*step5*step

Иллюстрация алгоритма Эратосфена © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 43

Псевдокод алгоритма Эратосфена © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 44 for i 1 to (N – 1) do // Заполнить массив числами диапазона primes[i] i + 1 i 1 while i < N do // основной цикл s primes[i] p i + s while p < N do // Вычеркивание (обнуление) не простых чисел primes[p] 0 p p + s i i + 1 while i < N и primes[i] = 0 do // Первое невычеркнутое i i + 1

Псевдокод алгоритма Эратосфена (оптимизир.) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 45 for i 1 to (N – 1) do // Заполнить массив числами диапазона primes[i] i + 1 i 1 while i 2 < N do // основной цикл s primes[i] p i + s while p < N do // Вычеркивание (обнуление) не простых чисел primes[p] 0 p p + s i i + 1 while i < N и primes[i] = 0 do // Первое невычеркнутое i i + 1

Другие алгоритмы поиска простых чисел © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 46 В математике решето Сундарама детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа N. Разработан индийским студентом С. П. Сундарамом в 1934 году. Из ряда натуральных чисел исключаются числа вида i + j + 2ij, где i < j. В математике решето Аткина быстрый современный алгоритм нахождения всех простых чисел до заданного целого числа N. Основная идея алгоритма состоит в использовании неприводимых квадратичных форм (представление чисел в виде ax² + by²).