1 Алгоритмы: основные понятия, примеры практической разработки. - презентация

1 1 Алгоритмы: основные понятия, примеры практической разработки

2 2 Интуитивное понятие алгоритма. Под алгоритмом понимают точное предписание (набор инструкций) о выполнении в определенной последовательности (порядке) некоторой системы операций для решения всех задач некоторого заданного типа. Входные данные для задач одного типа Вычислитель, пользующийся алгоритмом решения задачи данного типа Результат В математике серия однотипных задач считается решенной, когда для ее решения (при любых начальных данных) установлен алгоритм.

3 3 Алгоритмы: основные понятия, примеры практической разработки Простейшие алгоритмы - правила выполнения основных арифметических действий для десятичных чисел. В IX веке сформулированы Мухамедом бен Муссой по прозвищу Аль-Хорезми (сам термин «алгоритм» отдаленно напоминает его имя). Согласно Аль-Хорезми, процедура сложения двух многозначных чисел разлагается в цепочку элементарных действий, при осуществлении которых вычислитель (исполнитель) обозревает лишь две цифры соответствующего разряда. Одна из этих цифр может быть снабженной специальной пометкой, указывающей на необходимость переноса единицы в следующий разряд. Эти элементарные операции бывают двух типов: 1)запись соответствующей цифры суммы; 2)пометка о переносе над соседней слева цифрой. При этом алгоритм предписывает надлежащий порядок выполнения этих операций: справа налево.

4 4 Алгоритмы: основные понятия, примеры практической разработки Формальный характер предписаний (команд алгоритма), т.е. их независимость от содержания, вкладываемого в используемые в операциях числа, дает возможность их применения для любых исходных данных. Ключевые понятия. Команда – это указание исполнителю совершить некоторое действие. Исполнитель (вычислитель) – устройство или живой существо, которое выполняет по определенным правилам составленный алгоритм. Исполнитель, который не понимает цели алгоритма, называется формальным исполнителем. Алгоритмом называется точная инструкция (набор команд) исполнителю, сформулированная в понятной для него форме и определяющая процесс достижения поставленной цели на основе имеющихся исходных данных за конечное число шагов.

5 5 Алгоритмы: основные понятия, примеры практической разработки Свойства алгоритма. 1. Универсальность (массовость) - применимость алгоритма к различным наборам исходных данных. 2. Дискретность - процесс решения задачи по алгоритму разбит на отдельные действия. 3. Конечность - каждое из действий и весь алгоритм в целом обязательно завершаются. 4. Результативность - по завершении выполнения алгоритма обязательно получается конечный результат. 5. Выполнимость (эффективность) - результата алгоритма достигается за конечное число шагов. 6. Детерминированность (определенность) - алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Т.е. одно и то же предписание после исполнения должно давать один и тот же результат. 7. Последовательность – порядок исполнения команд должен быть понятен исполнителю и не должен допускать неоднозначности.

6 6 Алгоритмы: основные понятия, примеры практической разработки Классы алгоритмов. - вычислительные алгоритмы, работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным; - информационные алгоритмы, представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных); - управляющие алгоритмы, генерирующие различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют. Классификация алгоритмов по типу передачи управления: Основные (главные выполняемые программы) и вспомогательные (подпрограммы). Вспомогательный алгоритм должен быть снабжен таким заголовком, который позволяет вызывать этот алгоритм из других алгоритмов (например, основных).

7 7 Алгоритмы: основные понятия, примеры практической разработки Способы записи алгоритмов - Вербальный (словесный), когда алгоритм описывается на человеческом языке; - графический, когда алгоритм описывается с помощью набора графических изображений. - символьный, когда алгоритм описывается с помощью специального набора символов (специального языка); Словесная форма записи алгоритмов обычно используется для алгоритмов, ориентированных на исполнителя-человека. Команды такого алгоритма выполняются в естественной последовательности, если не оговорено противного.

8 8 Алгоритмы: основные понятия, примеры практической разработки Графическая запись с помощью блок-схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Написание алгоритмов с помощью блок-схем регламентируется ГОСТом.

9 9 Алгоритмы: основные понятия, примеры практической разработки Алгоритмы линейной структуры: действия выполняются последовательно одно за другим. Алгоритмы разветвленной структуры: в зависимости от выполнения или невыполнения какого- либо условия производятся различные последовательности действий.

10 10 Алгоритмы: основные понятия, примеры практической разработки Алгоритмы циклической структуры: в зависимости от выполнения или невыполнения какого-либо условия выполняется повторяющаяся последовательность действий, называющаяся телом цикла. Различают циклы с предусловием и постусловием :

11 11 Алгоритмы: основные понятия, примеры практической разработки Языки программирования содержат операторы цикла со счетчиком. Они используются, когда изначально известно, сколько итераций (проходов) цикла необходимо выполнить. Модель цикла со счетчиком может быть описана с помощью классического цикла с предусловием. Инициализация переменной счетчика Тело цикла Изменение счетчика Условие на значение счетчика да нет Продолжение выполнения

12 12 Алгоритмы: основные понятия, примеры практической разработки Язык машинных команд применялся до создания языков программирования высокого уровня (50-60 годы прошлого века). В машине БЭСМ была принята трехадресная система команд. Каждая команда в этой системе представляла из себя последовательность четырех десятичных двухзначных чисел : aa xx yy zz где aa - указывало номер предписываемой операции; xx и yy - адреса двух ячеек, над содержимым которых совершается данная операция; zz - определяло адрес ячейки, в которую необходимо поместить результат. Последовательность цифр представляет собой зашифрованную команду: «Сложить (операция 01) числа из ячеек с адресами 11 и 12, результат поместить в ячейку с адресом 15». Чтобы оперировать адресами хотя бы 255 ячеек памяти, размер самой ячейки в трехадресной команде (а также и ячеек с самими данными) должен быть как минимум 4 байта, по одному байту (8 бит) на каждую часть команды. Соответственно размер чисел с таким размером ячейки памяти мог достигать 31 двоичных разрядов для целых чисел (крайний левый бит, как правило отдавался под знак числа), т.е. максимальное целое число могло быть 2 32 – 1. Для действительных чисел еще один бит отдавался для десятичной точки, соответственно максимальная точность (размер мантиссы) мог составлять 29 двоичных разрядов.

13 13 Алгоритмы: основные понятия, примеры практической разработки 1. АРИФМЕТИЧЕСКИЕ КОМАНДЫ: А) 01 xx yy zz – Сложить число из ячейки с адресом xx с числом из ячейки с адресом yy и сумму отправить в ячейку с адресом zz. Б) 02 xx yy zz – Вычесть из числа из ячейки с адресом xx число из ячейки с адресом yy и разность отправить в ячейку с адресом zz. В) 03 xx yy zz – Умножить число из ячейки с адресом xx с числом из ячейки с адресом yy и произведение отправить в ячейку с адресом zz. Г) 04 xx yy zz – Разделить число из ячейки с адресом xx на число из ячейки с адресом yy и частное отправить в ячейку с адресом zz. 2. КОМАНДЫ ПЕРЕДАЧИ УПРАВЛЕНИЯ: Д) zz – Переходить к команде, хранящейся в ячейке с адресом zz (безусловная передача управления). Е) yy zz – Переходить к команде, хранящейся в ячейке с адресом zz при условии, что в ячейке с адресом yy хранится положительное число. Ж) yy zz – Переходить к команде, хранящейся в ячейке с адресом zz при условии, что в ячейке с адресом yy хранится отрицательное число. 3. КОМАНДА ОСТАНОВКИ: Команды выполнялись в том порядке, в каком они были записаны в ячейках памяти, если, конечно, данный порядок не менялся в результате выполнения команды передачи управления.

14 14 Алгоритмы: основные понятия, примеры практической разработки Псевдокод занимает промежуточное место между естественным, машинным и формальным языком (языками программирования). Структура программы на псевдокоде следующая. прог имя (арг ) линк список имен внешних подпрограмм; лог список имен логических переменных; цел список имен целых переменных; вещ список имен вещественных переменных; строка имя(длина); массив имя[размерность] тип значений ; функция имя(параметры) { возврат значение; } подпрог имя(параметры); { } нач кон

15 15 Алгоритмы: основные понятия, примеры практической разработки 1. Операторы ввода, вывода ввод (список переменных); вывод («строка», список переменных); 2. Операторы цикла: нц пока (условие выполнения) { тело цикла } кц пока // комментарии нц до { тело цикла } кц до (условие завершения) // комментарии нц для (инициализация счетчика; условие завершения; шаг) { тело цикла } кц для 3. Условный оператор: если (условие) то {последовательность действий} иначе {последовательность действий} 4. Операторы инкремент и декремент: «++» увеличивает целую переменную на 1; «--« уменьшает целую переменную на 1. Используются: знаки арифметических операций: «+», « - «, «/», «*» в выражениях, оператор присвоить «=». В логических выражениях будут применяться следующие операторы «==» - равно, «!=» - не равно; « » - больше; «>=» - больше или равно. Для объединения логических условий будем использовать логические операторы «И» - «&», «ИЛИ» - «||». Чтобы присвоить логической переменной значения будем использовать литералы ИСТИНА или ЛОЖЬ. Операторы будут отделяться «;». Группы операторов мы будем заключать в фигурные скобки «{» и «}». Ключевые слова отличаются от имен переменных русским написанием и снабжаются подчеркиванием.

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

17 17 Алгоритмы: основные понятия, примеры практической разработки подпрог sum2(rs строка(1), rq строка(1), rr строка(1), f лог) { f = ЛОЖЬ; если (rs == 0) то {rr = rq;} если (rq == 0) то {rr = rs;} если ((rs == 1) & (rq == 1)) то {rr = 2;} если ( ( ((rs == 1) & (rq == 2)) ) || ( ((rs == 2) & (rq == 1)) ) ) то {rr = 3;} если ( ( ((rs == 1) & (rq == 3)) ) || ( ((rs == 3) & (rq == 1)) ) ) то {rr = 4;} если ( ( ((rs == 1) & (rq == 4)) ) || ( ((rs == 4) & (rq == 1)) ) ) то {rr = 5;} если ( ( ((rs == 1) & (rq == 5)) ) || ( ((rs == 5) & (rq == 1)) ) ) то {rr = 6;} если ( ( ((rs == 1) & (rq == 6)) ) || ( ((rs == 6) & (rq == 1)) ) ) то {rr = 7;} если ( ( ((rs == 1) & (rq == 7)) ) || ( ((rs == 7) & (rq == 1)) ) ) то {rr = 8;} если ( ( ((rs == 1) & (rq == 8)) ) || ( ((rs == 8) & (rq == 1)) ) ) то {rr = 9;} если ( ( ((rs == 1) & (rq == 9)) ) || ( ((rs == 9) & (rq == 1)) ) ) то {rr = 0; f = ИСТИНА;} если ( ((rs == 2) & (rq == 2)) ) то {rr = 4; } если ( ( ((rs == 2) & (rq == 3)) ) || ( ((rs == 3) & (rq == 2)) ) ) то {rr = 5; } если ( ( ((rs == 2) & (rq == 4)) ) || ( ((rs == 4) & (rq == 2)) ) ) то {rr = 6; } если ( ( ((rs == 2) & (rq == 5)) ) || ( ((rs == 5) & (rq == 2)) ) ) то {rr = 7; } если ( ( ((rs == 2) & (rq == 6)) ) || ( ((rs == 6) & (rq == 2)) ) ) то {rr = 8; } если ( ( ((rs == 2) & (rq == 7)) ) || ( ((rs == 7) & (rq == 2)) ) ) то {rr = 9; } если ( ( ((rs == 2) & (rq == 8)) ) || ( ((rs == 8) & (rq == 2)) ) ) то {rr = 0; f = ИСТИНА;} если ( ( ((rs == 2) & (rq == 9)) ) || ( ((rs == 9) & (rq == 2)) ) ) то {rr = 1; f = ИСТИНА;} если ( ((rs == 3) & (rq == 3)) ) то {rr = 6; } если ( ( ((rs == 3) & (rq == 4)) ) || ( ((rs == 4) & (rq == 3)) ) ) то {rr = 7; } если ( ( ((rs == 3) & (rq == 5)) ) || ( ((rs == 5) & (rq == 3)) ) ) то {rr = 8; } если ( ( ((rs == 3) & (rq == 6)) ) || ( ((rs == 6) & (rq == 3)) ) ) то {rr = 9; } если ( ( ((rs == 3) & (rq == 7)) ) || ( ((rs == 7) & (rq == 3)) ) ) то {rr = 0; f = ИСТИНА;} если ( ( ((rs == 3) & (rq == 8)) ) || ( ((rs == 8) & (rq == 3)) ) ) то {rr = 1; f = ИСТИНА;} если ( ( ((rs == 3) & (rq == 9)) ) || ( ((rs == 9) & (rq == 3)) ) ) то {rr = 2; f = ИСТИНА;}

18 18 Алгоритмы: основные понятия, примеры практической разработки если ( ((rs == 4) & (rq == 4)) ) то {rr = 8; } если ( ( ((rs == 4) & (rq == 5)) ) || ( ((rs == 5) & (rq == 4)) ) ) то {rr = 9; } если ( ( ((rs == 4) & (rq == 6)) ) || ( ((rs == 6) & (rq == 4)) ) ) то {rr = 0; f = ИСТИНА;} если ( ( ((rs == 4) & (rq == 7)) ) || ( ((rs == 7) & (rq == 4)) ) ) то {rr = 1; f = ИСТИНА;} если ( ( ((rs == 4) & (rq == 8)) ) || ( ((rs == 8) & (rq == 4)) ) ) то {rr = 2; f = ИСТИНА;} если ( ( ((rs == 4) & (rq == 9)) ) || ( ((rs == 9) & (rq == 4)) ) ) то {rr = 3; f = ИСТИНА;} если ( ((rs == 5) & (rq == 5)) ) то {rr = 0; f = ИСТИНА;} если ( ( ((rs == 5) & (rq == 6)) ) || ( ((rs == 6) & (rq == 5)) ) ) то {rr = 1; f = ИСТИНА;} если ( ( ((rs == 5) & (rq == 7)) ) || ( ((rs == 7) & (rq == 5)) ) ) то {rr = 2; f = ИСТИНА;} если ( ( ((rs == 5) & (rq == 8)) ) || ( ((rs == 8) & (rq == 5)) ) ) то {rr = 3; f = ИСТИНА;} если ( ( ((rs == 5) & (rq == 9)) ) || ( ((rs == 9) & (rq == 5)) ) ) то {rr = 4; f = ИСТИНА;} если ( ((rs == 6) & (rq == 6)) ) то {rr = 2; f = ИСТИНА;} если ( ( ((rs == 6) & (rq == 7)) ) || ( ((rs == 7) & (rq == 6)) ) ) то {rr = 3; f = ИСТИНА;} если ( ( ((rs == 6) & (rq == 8)) ) || ( ((rs == 8) & (rq == 6)) ) ) то {rr = 4; f = ИСТИНА;} если ( ( ((rs == 6) & (rq == 9)) ) || ( ((rs == 9) & (rq == 6)) ) ) то {rr = 5; f = ИСТИНА;} если ( ((rs == 7) & (rq == 7)) ) то {rr = 4; f = ИСТИНА;} если ( ( ((rs == 7) & (rq == 8)) ) || ( ((rs == 8) & (rq == 7)) ) ) то {rr = 5; f = ИСТИНА;} если ( ( ((rs == 7) & (rq == 9)) ) || ( ((rs == 9) & (rq == 7)) ) ) то {rr = 6; f = ИСТИНА;} если ( ((rs == 8) & (rq == 8)) ) то {rr = 6; f = ИСТИНА;} если ( ( ((rs == 8) & (rq == 9)) ) || ( ((rs == 9) & (rq == 8)) ) ) то {rr = 7; f = ИСТИНА;} если ( ((rs == 9) & (rq == 9)) ) то {rr = 8; f = ИСТИНА;} } «вычислитель», обозревая два символа (цифры) rs и rq производит их «сложение», т.е. каждой возможной паре этих символов ставит в соответствие символ rr, являющийся результатом суммирования и переводит, если это необходимо, метку переноса разряда (логическая переменная f) в состояние «ИСТИНА».

19 19 Алгоритмы: основные понятия, примеры практической разработки Функция, которая, используя описанную выше подпрограмму, вычисляет сумму двух многозначных целых чисел одной длины (одинаковое число десятичных разрядов). функция sum(s[n] строка(1), q[n] строка(1), цел n) { цел j; массив rr[n+1] строка(1); массив fl[n] лог; // Поскольку при сложении может появиться дополнительный разряд слева, размерность рабочего массива прибавляется на 1. Логический массив для запоминания переносов разрядов. sum2(s[n], q[n], rr[n], fl[n]); // вычисляем справа налево суммы цифр нц для (j= n-1; j

20 20 Алгоритмы: основные понятия, примеры практической разработки Исходные данные (два числа) считываются потоком посимвольно, символ пробел означает конец числа в потоке. Тогда можно написать подпрограмму, которая считывает строку символов до первого пробела и заносит его в массив строк длины 1 размерности n. подпрог inp(s[*] строка(1), цел n) { цел i; строка ss(1); i=0; ss=; нц пока (ss != ) { ввод (ss); i++; s[i] = ss; } кц пока n = i--; } Программа, которая использует все разработанные ранее подпрограммы и функции и реализует алгоритм сложения двух чисел, считанных их входного потока данных (согласно блок-схеме). прог p1(арг ) линк inp(),max(), sum2(), sum(); нач цел n1; массив sv[*] строка(1); массив qv[*] строка(1); массив rv[*] строка(1); inp(sv,n1); inp(sq,n1); rv= sum(sv, sq, n1); вывод (Cумма, rv); кон

21 21 Алгоритмы: основные понятия, примеры практической разработки Пусть алгоритм сложения двух целых чисел реализован с помощью функции СУММ(цел x, цел y), которая принимает на входе два целых числа и выдает на выходе их сумму (целое число). Тогда фрагмент программы, которая выполняет умножение двух целых чисел n и m можно представить следующим образом. функция УМН(цел n, цел m) { цел j, rez; rez=0; j=1; нц пока (j

22 22 Алгоритмы: основные понятия, примеры практической разработки Алгоритм Евклида Решает все задачи следующего типа: Для двух данных натуральных чисел а и b найти их наибольший делитель. Очевидно, что различных задач такого типа существует столько, сколько имеется различных пар чисел а и b. Словесная форма записи алгоритма. Указание 1. Обозревай два числа: а и b. Переходи к Указанию 2. Указание 2. Сравни обозреваемые числа (либо а == b, либо а > b, либо а < b ). Переходи к Указанию 3. Указание 3. Если обозреваемые числа равны (а == b ), то каждое из них дает искомый результат. Процесс вычислений остановить. Если числа не равны, то переходи к Указанию 4. Указание 4. Если а < b, то переставь их местами и продолжай обозревать их. Переходи к Указанию 5. Указание 5. Вычитай второе из обозреваемых чисел из первого и обозревай два числа: вычитаемое и остаток. Переходи к Указанию 2.

23 23 Алгоритмы: основные понятия, примеры практической разработки Ввод исходных чисел а и b Начало алгоритма Инициализация рабочих переменных s=0 и r=0 а == b а < bа < b r = a – b; s=a; a=b; b=s; a = b; b = r; Вывод а Конец алгоритма Блок-схема алгоритма Евклида

24 24 Алгоритмы: основные понятия, примеры практической разработки Ввод исходных чисел а и b Начало алгоритма а != b а < bа < b a = a – b;b = b – a; Вывод а Конец алгоритма Блок-схема алгоритма Евклида (упрощение)

25 25 Алгоритмы: основные понятия, примеры практической разработки Программа на языке машинных команд, реализующая алгоритм Евклида. Пусть исходные данные (числа a и b) помещены в ячейки с адресами 12 и 13 соответственно, ячейки с адресами 14 и 15 будем использовать для промежуточных вычислений, а результат после остановки машины должен оказаться в ячейке с адресом 15. Номер (адрес) ячейки Содержание (шифр команды) Пояснение Посылка числа из ячейки с адресом 12 в ячейку с номером 15. Фактически производится суммирование содержимого ячейки 12 с нулевым значением, которое располагается в ячейке Производится разность содержимого ячеек 12 и 13, результат записывается в ячейку Переход к команде 06 при условии, что в ячейке 14 находится отрицательное число Переход к команде 09 при условии, что в ячейке 14 находится положительное число Остановка (нулевое числовое значение) Посылка числа из ячейки с адресом 13 в ячейку с номером 12. Фактически производится суммирование содержимого ячейки 13 с нулевым значением, которое располагается в ячейке 05. При этом предыдущее содержимое ячейки 12 теряется Посылка числа из ячейки с адресом 15 в ячейку с номером 13. Фактически производится суммирование содержимого ячейки 15 с нулевым значением, которое располагается в ячейке 05. При этом предыдущее содержимое ячейки 13 теряется Безусловный переход к команде, находящейся в ячейке с номером Посылка числа из ячейки с адресом 13 в ячейку с номером 12. Фактически производится суммирование содержимого ячейки 13 с нулевым значением, которое располагается в ячейке 05. При этом предыдущее содержимое ячейки 12 теряется Посылка числа из ячейки с адресом 14 в ячейку с номером 13. Фактически производится суммирование содержимого ячейки 14 с нулевым значением, которое располагается в ячейке 05. При этом предыдущее содержимое ячейки 13 теряется Безусловный переход к команде с номером 01.

26 26 Алгоритмы: основные понятия, примеры практической разработки Номер (адрес) ячейки Содержимое 12a 13b 14a – b 15a Если a – b = 0 (т.е. a = b), то команды 03 и 04 об условной передаче управления игнорируются (пропускаются) и выполняется команда 05, т.е. происходит остановка машины. К этому моменту в ячейке 15 находится искомый результат. Если a – b < 0 (т.е. a < b), то команда 03 передает управление команде 06, которая вместе со следующей за ней командой 07 переставляет местами числа a и b в ячейках 12 и 13, потом команда 08 обеспечивает безусловный переход к команде 01 и начинается следующий цикл работы алгоритма. Если a – b > 0 (т.е. a > b), то команда 03 пропускается, а следующая за ней команда 04, передает управление команде 09. Команды 09 и 10 пересылают в ячейки 12 и 13 прежнее вычитаемое и остаток от предыдущей разности, т.е. числа b и a – b. Затем команда 11 обеспечивает безусловный переход к команде 01 и начинается следующий цикл работы алгоритма. После выполнения первых двух команд:

27 27 Алгоритмы: основные понятия, примеры практической разработки функция НОД(цел n, цел m) { нц пока (n != m) { если (n > m) то {n = n – m;} иначе {m = m – n;} } кц пока возврат n; } прог p2(арг ) линк НОД(); { нач цел n1, n2, n3; ввод n1, n2; n3 = НОД (n1, n2); вывод («результат», n3); кон } Функция, нахождения НОД двух целых чисел Программа, реализующая алгоритм в соответствии с упрощенной блок-схемой

28 28 Алгоритмы: основные понятия, примеры практической разработки Поиск максимума в массиве чисел Словесная форма записи. Указание 1. Установи значение счетчика в 1, переходи к указанию 2. Указание 2. Установи значение результата, равное первому числу (элементу массива), переходи к Указанию 3. Указание 3. Увеличь значение счетчика на 1, переходи к Указанию 4. Указание 4. Сравни значение счетчика и количества чисел (размерность массива), переходи к указанию 5. Указание 5. Если значение счетчика больше заданного количества чисел (размерности массива), то остановка. Иначе переходи к указанию 6. Указание 6. Сравни значения результата и числа с номером, соответствующим текущему значению счетчика (текущего элемента массива), переходи к указанию 7. Указание 7. Если значение результата меньше или равно значению числа с номером, соответствующим текущему значению счетчика (текущего элемента массива), то переходи к указанию 8, иначе переходи к указанию 9. Указание 8. Присвой результату значение числа с номером, соответствующим текущему значению счетчика (текущего элемента массива), переходи к указанию 9. Указание 9. Переходи к Указанию 3.

29 29 Алгоритмы: основные понятия, примеры практической разработки Счетчик = 1; Результат = а[1]; Результат = a[Счетчик]; Счетчик++; Счетчик > N нет Результат

30 30 Алгоритмы: основные понятия, примеры практической разработки Для реализации циклических алгоритмов в языке машинных команд предусмотрены так называемые команды переадресации, с помощью которых можно запрограммировать повторяющиеся операции с использованием фиксированного набора ячеек. Условимся, что команды переадресации будут маркироваться числом 06 и их смысл будет заключаться в покомпонентном изменении адресов ячеек, участвующих в изменяемой команде. Например, если во вспомогательной ячейке переадресации с адресом 77 помещено значение , а исходная ячейка 33 имеет значение , то при выполнении команды переадресации значение переадресованной ячейки 33 станет равным Пусть в ячейке 12 расположено значение размерности массива N, уменьшенное на единицу (N-1), в ячейке 13 результаты промежуточных вычислений, в ячейке 14 - искомый результат, с 15 ячейки размещены элементы массива.

31 31 Номер (адрес) ячейки Содержание (шифр команды) Пояснение Присвоение ячейке 14 (результат алгоритма) значения первого элемента массива. Фактически производится суммирование содержимого ячейки 15 с нулевым значением, которое располагается в ячейке Вычисляется разность содержимого ячеек 16 (второго элемента массива) и 14, результат записывается в ячейку промежуточных вычислений с адресом Переход к команде 05 при условии, что в ячейке 13 находится отрицательное число Посылка числа из ячейки с адресом 16 (второй элемент массива) в ячейку с номером 14. Фактически производится суммирование содержимого ячейки 16 с нулевым значением, которое располагается в ячейке 09. При этом предыдущее содержимое ячейки 14 теряется Переадресация с использованием ячейки переадресации 10; содержимое ячейки 02 становится равным При следующих итерациях происходит увеличение адреса данной ячейки Переадресация с использованием ячейки переадресации 10; содержимое ячейки 04 становится равным Команда вычитает из значения ячейки 12 единицу (ячейка 11) и перезаписывает результат в ячейку Условный переход к команде 02 (уже с новыми адресами ячеек), если в ячейке 12 положительное число Остановка, когда выполнено N-1 итераций Ячейка переадресации, увеличивает на один номер первой ячейки в команде. 11Хранится значение 1 для счетчика итераций. 12Первоначально хранится число N-1 – размерность массива, уменьшенная на единицу. Затем в ячейке вычисляется число оставшихся итераций. 13В ячейку заносятся промежуточные вычисления (разность между текущим элементом массива и текущим результатом) 14Хранится текущий результат. На момент остановки в ячейке содержится искомый результат. 15Первый элемент массива 16Второй элемент массива и т.д.

32 32 Алгоритмы: основные понятия, примеры практической разработки функция МАКСМАС(цел n, массив а[n] цел ) { цел i, rez; i = 2; rez = a[1]; нц пока (i

33 33 Алгоритмы: основные понятия, примеры практической разработки Сортировка – упорядочение элементов в списке. Метод «пузырька». Самый популярный и достаточно медленный вид сортировки. Основан на методе перестановок, т.е. в данном алгоритме осуществляется постоянное сравнение текущего элемента с другими элементами и перестановка их при необходимости. Алгоритм состоит из двух вложенных циклов. Внешний цикл задает область поиска (диапазон индексов), а внутренний цикл внутри этого диапазона выполняет сравнение и перестановку элементов массива. На первом проходе внешнего цикла первый элемент сравнивается попарно со всеми остальными элементами, начиная со второго. При этом, если выполняется условие «>», то элементы переставляются местами и сравнения обновленного значения первого элемента массива с оставшимися элементами продолжаются до тех пор, пока внутренний цикл не дойдет до последнего элемента. В результате на месте первого элемента окажется минимальное среди всех значений. Второй проход внешнего цикла сокращает область действия внутреннего цикла – первый элемент уже стоит на своем месте. Происходят сравнения второго элемента массива с последующими и при необходимости замены их местами. И так далее. После n-1 проходов внешнего цикла (n размер массива) на последнем месте в массиве остается только один (максимальный) элемент и алгоритм завершается. 1/2*n*(n-1) - число сравнений. 3/4*n*(n-1) - среднее число перестановок. 3/2*n*(n-1) - максимальное возможное число перестановок.

34 34 Алгоритмы: основные понятия, примеры практической разработки Исходный массив - {15.0, -3.0, 10.0, 5.0, -9.0}. 1. Первый проход внешнего цикла: произведено 2 замены и на первом месте оказалось минимальное значение среди всех элементов массива – «-9.0». {-3.0, 15.0, 10.0, 5.0, -9.0} – первая замена 15 на -3; {-3.0, 15.0, 10.0, 5.0, -9.0} – замены нет; {-9.0, 15.0, 10.0, 5.0, -3.0} – вторая замена -3 на Второй проход внешнего цикла: произведено 3 замены и на втором месте слева оказался минимальный из оставшихся элементов массива – «-3.0». {-9.0, 10.0, 15.0, 5.0, -3.0} – первая замена 15 на 10. {-9.0, 5.0, 15.0, 10.0, -3.0} – вторая замена 10 на 5. {-9.0, -3.0, 15.0, 10.0, 5.0} – третья замена 5 на Третий проход внешнего цикла: произведено 2 замены. {-9.0, -3.0, 10.0, 15.0, 5.0} – первая замена 10 на 15. {-9.0, -3.0, 5.0, 15.0, 10.0} – вторая замена 5 на На четвертом (последнем) проходе внешнего цикла произведена 1 замена Это привело к получению искомого результата: {-9.0, -3.0, 5.0, 10.0, 15.0}. Массив отсортирован по возрастанию.

35 35 Алгоритмы: основные понятия, примеры практической разработки Блок-схема алгоритма «пузырьковой» сортировки I=1; J= I +1; I > N-1 J > N I++; D = A[J]; A[J] = A[I]; A[I] = D; A[J] < A[I] J++; Конец – + + – – + функция СОРТ1(цел n, массив а[n] цел ) { цел i, j, k; i = 1; нц пока (i

36 36 Алгоритмы: основные понятия, примеры практической разработки Рассмотренные нами алгоритмы относятся к группе так называемых вычислительных алгоритмов. На самом деле разрабатываются алгоритмы решения различных задач, в том числе и логических. Например, можно предложить схемы решения таких известных задач-головоломок, как решение игры 15, поиск кратчайшего пути в лабиринте (задача Тезей и Минотавр), а также разработать достаточно эффективные алгоритмы игры в шашки, шахматы и др. Создание эффективных алгоритмов, как и доказательство отсутствия разрешающего алгоритма для того или иного типа задач, является одной из ключевых проблем математики и сродни ИСКУССТВУ. Дональд Кнут «Искусство программирования», The Art of Computer Programming,. 2-е изд. М.: «Вильямс», с. В ней, в томе 3 «Сортировка и поиск», описывается большинство известных типов алгоритмов сортировки.