ОСНОВЫ ПРОГРАММИРОВАНИЯ Раздел 2. Математические основы программирования Логические алгоритмы Старший преподаватель Кафедры ВС, к.т.н. Поляков Артем Юрьевич 1 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Рассматриваемые вопросы Алгоритмы поиска значения в последовательности Алгоритмы сортировки Алгоритмы поиска наибольшего общего делителя 2 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Алгоритм последовательного поиска 3 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n, a, A i = 0 НАЧАЛО i < n AND a i A i = i + 1 i < n ДА i НЕТ нет КОНЕЦ НЕТ ввод n, a, A i = 0 пока i < n AND a i A делать i = i + 1 конец пока если i < n то вывод i иначе вывод ошибка конец если

Алгоритм последовательного поиска (пример) 4 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» ЭлементЧисло шагов ( ) / 11 = 66/11 = = 6 Число шагов в среднем?

Алгоритм двоичного поиска (пример) 5 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» ЭлементЧисло шагов ЭлементЧисло шагов Последовательный поискДвоичный поиск

Двоичное дерево поиска 6 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Шаг 1 Шаг 2 Шаг 3 Шаг 4 (1*1 + 2*2 + 4*3 + 4*4)/11 = 33/ 11 = = 3 Число шагов в среднем

Алгоритм двоичного поиска 7 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Входные данные: 1) последовательность a, упорядоченная по возрастанию; 2) n: размер a; 3) искомое значение A. Выходные данные: целое число i. Если i 0, то это номер искомого элемента A, в противном случае элемент во входной последовательности отсутствует. Принцип работы (словесное описание): 1. На каждом шаге рассматривается последовательность a lk =a l,…,a k. (изначально l=0, k=n-1). 2. Центральный элемент a f (f=(k-l)/2) последовательности a lk сравнивается с искомым. Если a f =A, то алгоритм закончен, если a f >A, то поиск продолжается в последовательности a l(f-1), в противном случае – в a (f+1),k. 3. Если kl, то искомого значения в a нет.

Алгоритм двоичного поиска (блок-схема) 8 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n, a, A l=0, k=n-1, i=0 НАЧАЛО k l AND a i A f =[(k-l)/2] a i = A ДА i НЕТ нет КОНЕЦ НЕТ a f >A ДА НЕТ k = f-1l = f+1 a f l) 2.Убрать проверку a i A ДА НЕТ

Алгоритм двоичного поиска* (псевдокод) 9 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» ввод n, a, A l = 0, k = (n-1), i = 0 пока k l AND a i A делать f =[(k-l)/2] если a i > A то l = f+1 иначе если a i < A то k = f-1 иначе i=f конец если конец пока если a i = A то вывод i иначе вывод не найдено иначе конец пока

Алгоритм двоичного поиска (псевдокод) 10 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» ввод n, a, A l = 0, k = (n-1), i = 0 пока k l AND a i A делать f =[(k-l)/2] если a i > A то k = f-1 иначе если a i < A то l = f+1 иначе i=f конец если конец пока если a i = A то вывод i иначе вывод не найдено иначе конец пока

Алгоритм сортировки методом пузырька (анимация) 11 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Проход Проход Проход Проход

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

Алгоритм сортировки методом пузырька 13 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Входные данные: 1) последовательность a; 2) n: размер a. Выходные данные: последовательность a, элементы которой упорядочены по возрастанию. Принцип работы (словесное описание): 1. Алгоритм состоит из ? проходов. На i-м проходе просматриваются элементы от 0-го до ?. 2. В рамках одного прохода выполняется сравнение пар соседних элементов, начиная с 0 и 1. Для соседних элементов проверяется условие a n < a n+1. Если данное условие не выполняется, то элементы меняются местами. 3. Условие завершения алгоритма?

Алгоритм сортировки методом пузырька 14 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Входные данные: 1) последовательность a,; 2) n: размер a. Выходные данные: последовательность a, элементы которой упорядочены по возрастанию. Принцип работы (словесное описание): 1. Алгоритм состоит не более, чем из n-1 проходов. На i-м проходе просматриваются элементы от 0 до ( n-i-1 ). 2. В рамках одного прохода выполняется сравнение пар соседних элементов, начиная с 0 и 1. Для соседних элементов проверяется условие a n < a n+1. Если данное условие не выполняется, то элементы меняются местами. 3. Алгоритм завершается, если на очередном проходе не было ни одного обмена. В худшем случае после (n-1) шагов.

Алгоритм сортировки методом пузырька (блок-схема)* 15 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n, a i = 0, c = 1 НАЧАЛО c > 0 AND i (n-1) c = 0, j = 0 нет КОНЕЦ НЕТ ja j+1 t=a j a j =a j+1 a j+1 =t ДА

Алгоритм сортировки методом пузырька (блок-схема) 16 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n, a i = 0, c = 1 НАЧАЛО c > 0 AND i (n-1) c = 0, j = 0 нет КОНЕЦ НЕТ ja j+1 t=a j a j =a j+1 a j+1 =t ДА i=i+1 j=j+1 Псевдокод?

Алгоритм сортировки методом пузырька (число операций) 17 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 1.В лучшем случае? 2.В худшем случае? Если последовательность уже упорядочена При каких условиях будет худший случай? Если массив упорядочен по убыванию. Какое будет количество операций на i-м проходе? Сравнений: Присваиваний: n-i-1 3*(n-i-1) Какое будет общее количество операций? Сравнений: Присваиваний: n-1 0

Алгоритм сортировки методом пузырька (число операций в худшем случае) 18 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Число операций в худшем случае: n раз i=1: 1 i=2: 1 1 i=3: i=4: …. i=n: …1

Сумма ряда (графическое доказательство) 19 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» i=1: i=2: i=3: i=4: …. i=n: ) Графически S кв : n 2, S тр : n 2 /2 ДИАГОНАЛЬ! 1) n 2 /2 включает лишь половину диагонали 2) длина диагонали: n 3) необходимо включить диагональ дважды 4) получаем прямоуголь- ник со сторонами: (n+1) и n. Искомая площадь равно половина его площади: (n+1)·n/

Метод математической индукции 20 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Суть метода: 1) Доказать, что утверждение справедливо для n=1 => P(1) – спр. 2) Доказать, что если справедливо P(n-1), то справедливо P(n) Если пп. 1 и 2 верны, то: P(1) – спр. => P(2) – спр. => P(3) - спр. => … => P(n-1) – спр. => P(n) - спр.

Сумма ряда (доказательство, метод мат. индукции) 21 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 3) Учитывая, что: Доказательство: 1) P(1): n=1, (n+1) n/2 = 1 4) Получим: 2) P(n): Пусть справедливо P(n-1), тогда:

Наибольший общий делитель 22 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. Принятые обозначения НОД чисел m и n: НОД(m, n) (m, n) gcd(m, n) (от англ. Greatest Common Divisor) Пример: для n=70, m=105, НОД(n,m) = 35. НОД существует и однозначно определён, если хотя бы одно из чисел m или n не ноль. ? НОД(n, m) = НОД(m, n) ?

Поиск НОД простым перебором 23 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n m 0 m n = 1 => НОД(n, m) = m 2. m = 1 => НОД(n, m) = n 3. n = m => НОД(n, m) = n или m 4. m НОД(n, m) m 5. n = m·q => НОД(n, m) = m 6. m НОД(n, m) < m

Поиск НОД простым перебором (2) 24 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n m m < n, n = m·d + q, m НОД(m, n), 1. d 1, иначе m n 2. Пусть l = НОД(m, n), тогда l [1, m] 3. Однако m = l d 1, т.к. l = НОД(m, n) => d 1 2, при d 1 = 1, m = l НОД(m, n) 4. Следовательно l [1, [m/2] ] l m 0 lm/2

Линейный алгоритм поиска НОД (блок-схема) 25 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n, m НАЧАЛО n < m n m НЕТДА n % m НЕТ ДА l=m l =S(n, m) n, m НАЧАЛО n%l0 m%l 0 НЕТ ДА l = m S(n, m): l=[m/2] l = l-1 l КОНЕЦ

Линейный алгоритм поиска НОД (псевдокод) 26 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» ввод n, m если m > n то t = n, n = m, m = t конец если если n % m = 0 то l = m иначе l = S(n, m) конец если вывод l процедура S(n, m) l = [m/2] пока m % l 0 AND n % l 0 делать l = l - 1 конец цикла вывод l конец процедуры

Алгоритм Евклида поиска НОД 27 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Для данных n и m строится последовательность чисел: n > m > r 1 > r 2 > … > r n, элементы r i которой определяются следующим образом: 1) n = m·d 0 + r 1 ; 2)m = r 1 ·d 1 + r 2 ; 3) r 1 = r 2 ·d 2 + r 3 ; … n-1) r n-1 = r n ·d n + 0 ; тогда r n = НОД(n, m) 1) r 1 = n % m; 2)r 2 = m % r 1 ; 3) r 3 = r 1 % r 2 ; … n-2) r n = r n-2 % r n-1.

Математическая основа алгоритма Евклида 28 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 1) n > m 2) n = m · d + q 3) Пусть l = НОД(m, n), т.е. n % l = 0 И m % l = 0, тогда (n % l) = (m % l) · d + (q % l) 0 = 0 · d + (q % l) q % l = 0 1 q m

Анализ алгоритма Евклида* 29 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n = m · d + q, m > q 1) Пусть (m значительное уменьшение числа рассматриваемых вариантов (п. 2). 2) Пусть (m ~ n), тогда q = n-m на следующем шаге ситуация, соответствующая п. 1. 3) Пусть (m>n/2, m~n/2), тогда q=(n-m)~m => на следующем шаге ситуация, соответствующая п. 2. 4) Пусть (m

Анализ алгоритма Евклида 30 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n = m · d + q, m > q 1) Пусть (m значительное уменьшение числа рассматриваемых вариантов (п. 2). 2) Пусть (m ~ n), тогда q = n-m на следующем шаге ситуация, соответствующая п. 1. 3) Пусть (m>n/2, m~n/2), тогда q=(n-m)~m => на следующем шаге ситуация, соответствующая п. 2. 4) Пусть (m

Алгоритма Евклида (блок-схема)* 31 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n, m НАЧАЛО n%m 0 ? НЕТ ДА ? КОНЕЦ

Алгоритма Евклида (блок-схема)* 32 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n, m НАЧАЛО n%m 0 l=n%m n=m m=l НЕТ ДА ? КОНЕЦ

Алгоритма Евклида (блок-схема) 33 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n, m НАЧАЛО n%m 0 l=n%m n=m m=l НЕТ ДА m КОНЕЦ

Алгоритма Евклида (псевдокод)* 34 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n, m НАЧАЛО n%m 0 l=n%m n=m m=l НЕТ ДА m КОНЕЦ ПСЕВДОКОД??

Алгоритма Евклида (псевдокод) 35 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» n, m НАЧАЛО n%m 0 l=n%m n=m m=l НЕТ ДА m КОНЕЦ ввод n, m пока n%m 0 делать l = n%m n = m m = l конец цикла вывод l

ИТОГИ 36 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Рассмотрено 5 логических алгоритмов Линейный и двоичный алгоритм поиска значения в последовательности – Вычислено количество шагов в среднем и в худшем случае Алгоритм пузырьковой сортировки – Определено число операций, требуемое для выполнения сортировки в худшем случае Линейный алгоритм поиска наибольшего общего делителя и алгоритм Евклида – Проведено сравнение количества шагов, требуемых каждому из алгоритмов