План 1. Определение алгоритма. 2. Свойства алгоритмов. 3. Способы описания алгоритма. 4. Базовые структуры схем алгоритма. 5. Структурированные схемы и их построение. 6. Линейные и разветвляющиеся структуры. 7. Циклические структуры. Типы циклов. 8. Предопределённые процессы. Рекурсия.
Упражнения Составить схемы 2-х задач (одна на одномерные массивы, вторая на двумерные) и описать решение каждой задачи на конкретном примере, т.е. поработать за компьютер.
1. Задача на одномерные массивы:
Задан целочисленный одномерный массив a из n элементов. Найти значение максимального элемента среди четных (по значению) элементов, расположенных до первого нечетного элемента. 2. Задача на двумерные массивы: Найти в матрице первую строку, все элементы которой равны нулю. Все элементы столбца с таким же номером уменьшить вдвое.
1) Определение алгоритма.
Алгоритм - конечная последовательность команд исполнителю для выполнения некоторой работы или решения задачи. Создание алгоритма доступно исключительно живым существам, а долгое время считалось, что только человеку. Другое дело – реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принять называть формальным исполнителем. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совершить исполнитель, называются его допустимыми действиями. Совокупность допустимых действий образуют систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.
2) Свойства алгоритмов.
Любой алгоритм должен обладать каждым из приведённых ниже свойств: 1. Понятность – каждая команда должна быть понятна исполнителю, т.е. входить в систему команд исполнителя. 2. Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных шагов). Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего. 3. Определенность (детерминированность) – каждое правило алгоритма должно быть четким, однозначным. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполнителю неясно, какая из команд алгоритма должна выполняться на следующем шаге. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче. 4. Результативность. Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определённый результат. Вывод о том, что решения не существует - тоже результат. 5. Массовость – алгоритм должен решать любую задачу из того класса задач, для решения которых он разработан. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма. Например, алгоритм решения квадратного уравнения должен решать любое квадратное уравнение. Алгоритмом также называется информационный процесс, обладающий следующими свойствами: - Наличие исполнителя преобразований (с его системой команд). - Разбиение всего процесса преобразования на отдельные команды (понятные исполнителю). - Определено начальное состояние объекта (над которым производится преобразование) и его требуемое конечное состояние (цель преобразования).
3) Способы описания алгоритма. Алгоритмы можно записывать не только при помощи слов. В настоящее время различают несколько способов описания алгоритмов: 1. Словесный способ, т.е. записи на естественном языке, описание словами последовательности выполнения алгоритма. Например: Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел. Алгоритм может быть следующим: задать два числа; если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма; определить большее из чисел; заменить большее из чисел разностью большего и меньшего из чисел; повторить алгоритм с шага № __. 2. Графический способ, т.е. с помощью блок-схем. Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным способом. При графическом исполнении алгоритм изображается в виде последовательности связанных между собой блочных символов, каждый из которых соответствует выполнению одного из действий. Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. Символы, наиболее часто употребляемые в блок-схемах. 3. Программный способ, т.е. тексты на языках программирования. cls input a, b c = a + b print c
4) Базовые структуры схем алгоритма. Базовые структуры алгоритмов — это определенный набор блоков и стандартных способов их соединения для выполнения типичных последовательностей действий. К основным структурам схем алгоритмов относятся: o Следование; o Ветвление (полное и не полное); o Повторение (цикл с предусловием или постусловием); o Вход; o Выход.
Следованием называются схемы алгоритмов, в которых действия осуществляются последовательно друг за другом. Стандартная блок-схема линейного алгоритма приводится ниже:
Ветвлением называется схема алгоритма, в которой действие выполняется по одной из возможных ветвей решения задачи, в зависимости от выполнения условий. В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в разветвляющиеся алгоритмы входит условие, в зависимости от выполнения или невыполнения которого выполняется та или иная последовательность команд (действий). В качестве условия в разветвляющемся алгоритме может быть использовано любое понятное исполнителю утверждение, которое может соблюдаться (быть истинно) или не соблюдаться (быть ложно). Такое утверждение может быть выражено как словами, так и формулой. Таким образом, алгоритм ветвления состоит из условия и двух последовательностей команд. В зависимости от того, в обеих ветвях решения задачи находится последовательность команд или только в одной разветвляющиеся алгоритмы делятся на полные и не полные (сокращенные). Стандартные блок-схемы разветвляющегося алгоритма приведены ниже:
Повторением называется схема алгоритма, в которой некоторая часть операций (тело цикла — последовательность команд) выполняется многократно. Однако слово «многократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности — получения результата за конечное число шагов. Перед операцией цикла осуществляются операции присвоения начальных значений тем объектам, которые используются в теле цикла. В цикл входят в качестве базовых следующие структуры: o блок проверки условия o блок, называемый телом цикла Каждая базовая структура имеет один вход и один выход.
5) Структурированные схемы и их построение. Блок-схема называется структурированной, если она построена на основе базисного множества базовых структур. Для построения структурированных блок-схем была разработана специальная технология, которая называется пошаговой детализацией. Пошаговая детализация представляет собой процесс дробления задачи на модули, т.е. исходя из общей задачи, вычленяются подзадачи, устанавливаются логические связи между ними. После этого переходят к уточнению выделенных подзадач. Этот процесс детализации продолжается до уровня позволяющего достаточно легко реализовать подзадачу на выбранном языке программирования. При пошаговой детализации используется принцип замещения, который состоит в замене любого функционального блока (прямоугольника) блок-схемы некоторой базовой структурой (следование, ветвление, повторение) из исходного базисного множества. Достоинство пошаговой детализации состоит в том, что она позволяет разработчику алгоритма упорядочить свои рассуждения. Пример. Построить структурированную блок-схему алгоритма для вычисления функции. На первом шаге задачу представим в виде одного блока, в котором запишем кратко условие задачи. На втором шаге функциональный блок преобразуем в развилку, где выделено вычисление Y при x<0. На последнем шаге функциональный блок предыдущей схемы заменяем развилкой. В итоге выполнения нескольких шагов мы получили структурированную блок-схему алгоритма решения задачи.
6) Линейные и разветвляющиеся структуры. Линейными называют алгоритмы, в которых операции выполняются последовательно одна за другой, в естественном и единственном порядке следования. В таких алгоритмах все блоки имеют последовательное соединение логической связью передачи информационных потоков. В них могут использоваться все блоки, за исключением блоков проверки условия и модификации. Линейные алгоритмы, как правило, являются составной частью любого алгоритмического процесса. Пример:
Разветвляющимися называют алгоритмы, в которых в зависимости от выполнения некоторого логического условия происходит разветвление вычислений по одному из нескольких возможных направлений, называют. Подобные алгоритмы предусматривают выбор одного из альтернативных путей продолжения вычислений. Каждое возможное направление вычислений называется ветвью. Логическое условие называют простым, если разветвляющийся процесс имеет две ветви, и сложным, если процесс разветвляется на три и более ветви. Любое сложное логическое условие может быть представлено в виде простых. Пример:
7) Циклические структуры. Типы циклов. Алгоритм циклической структуры – это алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий. На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз. Многократное повторение последовательности действий называется циклом, а многократно повторяющиеся действия – телом цикла. Изучение циклов демонстрирует главное преимущество компьютера перед человеком – выполнение большого числа действий за короткое время. Ведь даже весьма короткий циклический алгоритм, составить который не так уж долго, при исполнении может потребовать выполнения нескольких сотен действий, с которыми компьютер справится намного быстрее, чем человек. Существует три формы циклов: цикл с параметром, цикл с предусловием, цикл с постусловием. Нетрудно заметить, что эти циклы взаимозаменяемы и обладают некоторыми отличиями: 1. В цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием - после тела цикла; 2. В цикле с постусловием тело цикла выполняется хотя бы один раз, в цикле с предусловием тело цикла может не выполниться ни разу; 3. В цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием - условие выхода из цикла.
8) Предопределённые процессы. Рекурсия. Предопределенный процесс — процесс, определенный в системе заранее (до начала его прямого использования). Предопределенный процесс состоит из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в него данные. Например, в программировании − вызов процедуры или функции. Изображается следующим образом: . Рекурсией называется такая конструкция, при которой функция вызывает саму себя. Различают прямую и косвенную рекурсии. Функция называется прямо рекурсивной, если содержит в своем теле вызов самой себя. Если же функция вызывает другую функцию, которая в свою очередь вызывает первую, то такая функция называется косвенно рекурсивной Пример прямой рекурсии: Пример косвенной рекурсии: int a() a(){.....b().....} {.....a().....} . b(){.....c().....} c(){.....a().....}.
