16 Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов. Свойства алгоритмов:

Дискретность (от лат. discretus — разделённый, прерывистый, раздельность) (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);

Детерминированность (от. лат. determinate – определенность, точность) (любое действие должно быть строго и недвусмысленно определено в каждом случае);

Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);

Массовость (один и тот же алгоритм можно использовать с разными исходными данными);

Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях). В качестве исполнителя алгоритмов в "докомпьютерную" эру подразумевался человек (в крайнем случае, животное - в цирке). Человек постоянно пользуется алгоритмами при решении задач, не задумываясь над этим, машинально (автоматически). Сегодня в качестве исполнителей алгоритмов человеку служат многие автоматические устройства и, прежде всего, конечно, компьютер. При этом составление алгоритма должно быть особенно ответственным и тщательным, так как машина не может домысливать и исправлять ошибки. В этом смысле она - идеальный исполнитель. При реализации алгоритма для ЭВМ его шаги становятся операторами, а вся их последовательность - программой. Для исполнителя всегда нужно определить те команды, которые он должен и может выполнять, чтобы совершать действия, предусмотренные алгоритмом. Набор таких команд называется системой команд исполнителя. Таких команд ограниченное число и их не может быть много. Чем меньше команд, тем легче построить техническое устройство в роли их исполнителя. Система команд исполнителя (СКИ) – это все команды, которые исполнитель умеет выполнять. Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаны pезультаты выполнения команды . Напpимеp, команда Pобота "ввеpх" может быть выполнена, если выше Pобота нет стены. Ее pезультат — смещение Pобота на одну клетку ввеpх.

После вызова команды исполнитель совеpшает соответствующе .

Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды.

• Среда исполнителя – обстановка, в которой функционирует исполнитель.

Исполнителями могут быть

машины: станки, роботы, компьютеры;

растения: подсолнечник (разворачивается на солнце), кувшинки (закрываются на ночь);

животные: дрессированная собака (санитар, розыскная, охотничья), кошка,

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

Хотя алгоритмы обычно предназначены для автома­тического выполнения, они создаются и разрабатывают­ся людьми. Поэтому перво­начальная запись алгоритма обычно производится в фор­ме, доступной для восприя­тия человеком.

Самой простой является словесная форма записи алго­ритмов на естественном язы­ке. В этом виде алгоритм представляет собой описание последовательности этапов обработки данных, изложен­ное в произвольной форме. Словесная форма удобна для человеческого восприятия, но страдает многословностью и неоднозначностью. Отказ от естественного языка требует частичной форма­лизации способа записи алгоритма и использования стан­дартных приемов построения алгоритмов в виде комбина­ций базовых алгоритмических структур. Таких базовых структур всего три: следование, ветвление и цикл. Харак­терной особенностью всех базовых структур является на­личие одного входа и одного выхода.

Графическая записьалгоритмов также предназначена для наглядного восприятия человеком. Она более формальна, чем запись в словесном виде. Алго­ритм изображается как последовательность функциональ­ных блоков, соответствующих одной или нескольким ко­мандам алгоритма. Такое графическое представление алгоритма называют блок-схемой. Элементы блок-схемы, блочные символы, — это геометрические фигуры. Они пред­ставляют базовые алгоритмические структуры.

 Блок-схема – это ориентированный граф, указывающий порядок исполнения команд алгоритма. Вершины такого графа могут быть одного из трех типов: функциональная, предикатная и объединяющая (рис). Термины метаязык или псевдокод используют в тех слу­чаях, когда запись алгоритма формализована частично. В таком случае она содержит как элементы естественного языка, так и формальные конструкции, описывающие ба­зовые алгоритмические структуры. Подобная запись алго­ритма предназначена для чтения человеком. Она не может использоваться для подготовки алгоритма к автоматиче­скому выполнению. Однако использование жестких языковых конструкций облегчает переход к формальной записи алгоритма. Формального определения псевдокода или строгих правил записи алгоритмов в таком формате не существует. Можно представить себе разные псевдоко­ды, использующие различные ключевые слова и способы представления базовых алгоритмических структур.

Термины алгоритмический язык и язык программирования часто используют как синонимы. При использовании этих языков запись алгоритма совершенно формальна. Синтак­сис языка однозначно определяет, что допустимо, а что нет.

Алгоритмические языки считаются машинно-независимы­ми. Запись на алгоритмическом языке используют, напри­мер, при публикации алгоритмов.

Чтобы выполнить вычислительный алгоритм на компью­тере, его записывают на языке программирования. Для под­готовки алгоритма, записанного на языке программирова­ния, к выполнению, применяют автоматические средства. Специальная программа – транслятор переводит каждую команду алгоритма в последовательность инструкций про­цессора. Получается программа на машинном языке, кото­рая уже может быть выполнена.

Отдельная инструкция языка программирования называ­ется оператором. Программа — это упорядоченная после­довательность операторов. Способ отделения операторов друг от друга определяется правилами языка. Во многих ранних языках программирования существовало правило: новая строка — новый оператор.

Современные языки программирования обычно позволяют поместить на одну строку несколько операторов или, на­оборот, разбить оператор на несколько строк. В этом слу­чае для отделения операторов друг от друга используется символ-разделитель. В большинстве других языков программирования (Пас­каль, Си) в качестве разделителя используется точка с запятой (;).

Запись операторов в языках программирования обычно производится с помощью ключевых слов, хотя некоторые операторы их не требуют. Конкретные ключевые слова различны в разных языках программирования. Обычно это слова английского языка, значение которых примерно со­ответствует назначению оператора. Говоря об операторах, обычно указывают их назначение (оператор присваивания, условный оператор, оператор цикла, оператор положительно сказывается на степени использовании ресурса ОЗУ. Динамические

вызова под­программы и т.п.).

17. 1.Линейные алгоритмы  Линейным называется алгоритм, в котором все этапы решения задачи выполняются строго последовательно. Т.е. линейный алгоритм выполняется в естественном порядке его написания и не содержит разветвлений и повторений.  Рассмотрим составление схем линейных алгоритмов на конкретных примерах.  Пример . Даны переменные А и В. Требуется обменять их значения, т.е. переменная А должна получить значение В, а В - значение А.  Решение.  1.Исходные данные: А, В. Вспомогательная переменная DOP. Результат: А, В.  2.Метод решения задачи: В ЭВМ каждая величина хранится в отдельном участке памяти (переменной). Поэтому задача заключается в том, чтобы поменять местами содержимое двух ячеек.  Давайте решим следующую задачу: имеется два стакана, в одном из них вода, в другом молоко. Требуется поменять содержимое стаканов. Житейский опыт подсказывает, что нам для решения данной проблемы потребуется ещё один стакан. В него мы перельём воду из первого, затем в первый стакан (из второго) нальём молоко, а из вспомогательного стакана во второй нальём воду.  Рассмотрим теперь запись этого алгоритма с помощью псевдокода. Напомню, что Псевдокоды это интерпретация шагов алгоритма на обычном языке, которая описывает действие команды. При записи алгоритма с использованием псевдокодов знаки арифметических операций будем обозначать так: + , - , / , *. Знак := (двоеточие и равно) означает операцию присвоения выбранной переменной некоторого значения.  К инструкциям линейных алгоритмов относятся инструкции ввода-вывода информации и инструкция присваивания. На языке псевдокода эти инструкции обозначаются следующим образом:  Инструкция ввода - Ввод (x, y, z); *Здесь в скобках перечислены имена элементов, которые надо ввести. Инструкция вывода - Вывод (x, y);  Инструкция присваивания - x := 32;  *Читается: "х присвоить значение 32".  2.Алгоритмы ветвящейся структуры.  выбирается один из нескольких возможных путей (вариантов) вычислительного процесса. Ветвью алгоритма называется каждый подобный путь. Признаком разветвляющегося алгоритма является наличие операций условного перехода, когда происходит проверка истинности некоторого логического выражения (проверяемое условие) и в зависимости от истинности или ложности проверяемого условия для выполнения выбирается та или иная ветвь алгоритма. Алгоритм предполагает выполнение Действия 1, если записанное условие истинно (выполняется), и выполнение Действия 2 ( если условие ложно (не выполняется). В частном случае может отсутствовать один из блоков "Действие 1" или "Действие 2". Пусть, например, В - проверяемое условие, а s1, s2 - некоторые выполняемые инструкции (действия). Тогда: Если условие В выполняется (истинно), то выбрать для исполнения s1, иначе выбрать для исполнения s2  3. Циклический алгоритм.  Реализует повторение некоторых действий. Иными словами Циклические алгоритмы включают в себя циклы. Циклом называется последовательность действий, выполняемых много-кратно, каждый раз при новых значениях параметров.  Примеры циклических алгоритмов может служить алгоритм покраски забора. Действительно, рассмотрим этот алгоритм в словесно-формульном виде:  Шаг I. Подготовить исходные данные (забор, краску, кисть);  Шаг II. Подойти к забору;  Шаг III. Обмакнуть кисть в краску;  Шаг IV. Нанести краску кистью на поверхность забора;  Шаг V. Если забор еще не весь окрашен, то повторить алгоритм, начиная с пункта ( Шаг III). Существует несколько видов циклических инструкций, с помощью которых можно организовать циклы. a. Инструкция "цикл с параметром" (цикл с заданным количеством повторений).  Обозначим: x - параметр цикла (является счетчиком количества повторений);  a, b - соответственно начальные и конечные значения параметра цикла;  h - шаг, с которым изменяется параметр цикла;  S - Оператор (инструкция), повторяемый в цикле;  Общий вид структуры цикла с параметром будет: ДЛЯ х: =а до в с шагом h повторять  S b.Инструкция "цикл с предусловием" (цикл-"пока"). c. Инструкция "цикл с постусловием" (цикл-"до").

18. Основные алгоритмические конструкции:

Линейный алгоритм.

В алгоритмическом языке линейным является алгоритм, состоящий из команд,

выполняющихся одна за другой. Они в записи алгоритма располагаются в том

порядке, в каком должны быть выполнены предписываемые ими действия. Такой

порядок выполнения называется естественным. Последовательность команд

образует составную команду «цепочка», которая в записи блок-схемой имеет вид,

приведенный на рисунке 1. В математике к линейным алгоритмам относятся алгоритмы, представленные

формулами. Они наиболее просты для программирования. Заметим, что

естественный способ кодировки формул делает программу легкочитаемой, но

нередко приводит к лишним вычислениям, поэтому, чтобы избежать повторных

вычислений и сократить общее количество операций выполняйте тождественные

преобразования выражений. С другой стороны, надо знать, что не всегда следует

осуществлять оптимизацию, поскольку она является не правилом, а исключением.

Этому есть три причины, главная из которых состоит в том, что оптимизация

ухудшает наглядность программ, вторая - выгоды компактна, наглядна и

от оптимизации должны быть

существенными и третья - современные системы, как правило, имеют

удовлетворительные оптимизирующие компиляторы.

Основные алгоритмические конструкции:

Ветвящийся алгоритм.

При исполнении алгоритмов приходится не только находить значения величин, но

и анализировать их свойства, сравнивать их друг с другом и в зависимости от

результата сравнения выбирать ту или иную ветвь алгоритма. Алгоритмы, имеющие

несколько ветвей, называются нелинейными. К таким относятся разветвляющиеся и

циклические алгоритмы. Для их записи применяются составные команды.

Базовая структура "ветвление". Определяет выполнение действий в зависимости

от выполнения условия. Каждый из путей ведет к общему выходу, так что работа

алгоритма будет продолжаться независимо от того, какой путь будет выбран. Циклический алгоритм.

Повторяющееся выполнение действий (групп действий),зависящее от выполнения

условия, называется циклом.

Любой цикл состоит из трех частей: начала, проверки и тела цикла. Начало –

всегда первая часть цикла. Главная его функция – подготовить цикл. Проверка

определяет момент выхода из цикла.

Базовая структура "цикл". Обеспечивает многократное выполнение некоторой

совокупности действий, которая называется телом цикла. Основные разновидности

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

Для реализации вспомогательных алгоритмов служат подпрограммы или процедуры. Подпрограмма — самостоятельный фрагмент программы, оформленный в виде, допускающем многократное обращение к нему из разных точек программы. Обращение к подпрограмме — переход к выполнению подпрограммы с заданием информации, необходимой для ее выполнения и возврата.

Существует два вида подпрограмм: процедуры и функции. Разница между ними состоит в том, что функция через свое имя возвращает одно значение определенного типа и может, использоваться в выражениях наряду со встроенными функциями

Процедура Вызов процедуры из основной программы производится оператором вызова процедуры: <имя процедуры>(<список значеиий>).

В процедуру могут передаваться параметры, то есть некоторые переменные, которые могут использоваться внутри процедуры. При вызове процедуры с помощью оператора вызова этим переменным присваиваются значения, указанные в этом операторе. Параметры, описанные в заголовке процедуры, называются формальными значения, которые присваиваются этим параметрам в процессе вызова —фактическими параметрами.

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

Для того чтобы передать параметр по ссылке, в Паскале в описании формальных параметров в теле процедуры используется ключевое слово var:

procedure SubTest(a,b:integer; var c:real, var d:integer);

здесь параметры а и b передаются по значению, а параметры с и d — по ссылке.

Функции

Функции по своей сути похожи на процедуры, но возвращают одно значение через свое имя.

Алгоритмом ветвящейся структуры будем называть такой алгоритм, котором