ОКП КР1 вариант 13

Содержание

1. Определение алгоритма.

2. Свойства алгоритмов.

3. Способы описания алгоритма.

4. Базовые структуры схем алгоритма.

5. Структурированные схемы и их построение.

6. Линейные и разветвляющиеся структуры.

7. Циклические структуры. Типы циклов.

8. Предопределенные процессы. Рекурсия.

9. Алгоритм решения задачи №1

10. Алгоритм решения задачи №2

1. Определение алгоритма

Алгоритм - это конечная последовательность команд исполнителю для выполнения некоторой работы или решения задачи. Создание алгоритма, пусть даже самого простого – процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. Другое дело – реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принять называть формальным исполнителем. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совершить исполнитель, называются его допустимыми действиями. Совокупность допустимых действий образуют систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.

2. Свойства алгоритма

Разработать алгоритм решения задачи означает разбить задачу на последовательно выполняемые шаги, причем результаты выполнения предыдущих этапов могут использоваться при выполнении последующих. При этом должны быть четко указаны как содержание каждого шага, так и порядок выполнения шагов, т.к. компьютер – формальный исполнитель.  Свойства:  1. Понятность – каждая команда должна быть понятна исполнителю, т.е. входить в систему команд исполнителя.

2. Дискретность(прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных шагов). Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.  3. Определенность(детерминированность) – каждое правило алгоритма должно быть четким, однозначным. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполнителю неясно, какая из команд алгоритма должна выполняться на следующем шаге. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

4. Результативность. Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определённый результат. Вывод о том, что решения не существует - тоже результат.  5. Массовость – алгоритм должен решать любую задачу из того класса задач, для решения которых он разработан. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма. Например, алгоритм решения квадратного уравнения должен решать любое квадратное уравнение.

3. Способы описания алгоритма

Для описания алгоритмов существует множество способов. Основные способы описания следующие:

1. словесный;

2. алгоритмический язык; 

3. схема; 

4. псевдокод. 

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

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

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

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

4. Базовые структуры блок-схем

Базовые алгоритмические структуры. Используя исходные элементы блок-схем можно собрать более крупные кирпичики, которые называют базовыми структурами.

Базовые структуры (конструкции): 

1. следование;

2. ветвление (полное и не полное);

3. повторение (цикл с предусловием или постусловием);

4. вход; 

5. выход.

Каждая базовая структура имеет один вход и один выход. Схемы основных базовых алгоритмических структур:

Следование Повторение (Цикл )

Ветвление (полное)

Выбор (оператор switch)

5. Структурированные блок схемы и их построение

Блок-схема называется структурированной, если она построена на основе базисного множества базовых структур.

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

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

Пример. Построить структурированную блок-схему алгоритма для вычисления функции

На первом шаге задачу представим в виде одного блока, в котором запишем кратко условие задачи.

На втором шаге функциональный блок преобразуем в развилку, где выделено вычисление Y при x<0.

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

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

6. Линейные и разветвляющиеся структуры

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

Пример:

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

Любое сложное логическое условие может быть представлено в виде простых. 

7. Циклические структуры. Типы циклов.

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

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

1. в цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием - после тела цикла; 

2. в цикле с постусловием тело цикла выполняется хотя бы один раз, в цикле с предусловием тело цикла может не выполниться ни разу;  3. в цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием - условие выхода из цикла.

8. Предопределенные процессы. Рекурсия.

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

Пример прямой рекурсии:

Int a()

{.....a().....}  Пример косвенной рекурсии:

a(){.....b().....}  b(){.....c().....}  c(){.....a().....} .  Предопределенный процесс — это символ, который отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле). Изображается следующим образом: