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

Понятие алгоритма, свойства алгоритма. Блок-схема алгоритма

5.1.1. Понятие алгоритма

Алгоритм - точное предписание исполнителю совеpшить определенную последовательность действий для достижения поставленной цели за конечное число шагов.

Происхождение самого термина «алгоритм» связано с с зарождением математики. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787 – 850) выдающегося математика средневекового Востока. В своей книге "Об индийском счете" он описал способы выполнения арифметических действий над многозначными числами. Само слово алгоритм возникло в Европе после перевода на латынь книги этого математика.

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

При этом:

-- исходные данные изменяются в определённых пределах;

-- процесс применения инструкций и правил к исходным данным определён однозначно в виде последовательности шагов;

-- на каждом шаге известно, что считать результатом.

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

Процесс решения задач на ЭВМ предполагает выполнение следующих этапов:

1. формулировка задачи

2. выбор метода решения задачи

3. составление алгоритма

4. решение задачи на ЭВМ по заданной программе.

Алгоритм это не что-то абстрактное и присущее лишь процессу использования ЭВМ, а неотъемлемая часть повседневной жизни. Любые инструкции, любые распоряжения могут быть сформулированы в виде алгоритма. Цель исполнения алгоритма – получение определённого результата, если в результате исполнения алгоритма не достигнута определённая цель, значит алгоритм либо не верен, либо не завершён.

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

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

· Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

· Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.

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

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

Существуют несколько способов описания алгоритма:

· словесное

· псевдокод

· блок-схема

· программа.

Словесное описание представляет структуру алгоритма на естественном языке. Запись алгоритма осуществляется в произвольной форме, никаких правил не существует.

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

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

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

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

Программный, т.е. тексты на языках программирования. Алгоритм, записанный на языке программирования называется программой.

Словесная и графическая форма записи алгоритма предназначены для человека. Алгоритм, предназначенный для исполнителя на компьютере записывается на языке программирования (языке, понятном ЭВМ). Сейчас известно несколько сот языков программирования. Наиболее популярные: Бейсик, Си, Паскаль, Пролог, и т.д.

5.1.4. Основные блоки, входящие в схемы алгоритмов

РИС. (5.1)39 Основные блоки, входящие в схемы алгоритмов и их назначение

5.2.1. Линейная алгоритмическая конструкция. Программы линейной структуры

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

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

РИС. (5.2)40 Блок-схема линейного алгоритма

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

5.2.2. Разветвляющаяся алгоритмическая конструкция. Операторы ветвления.

Алгоритм разветвленной структуры - алгоритм, содержащий хотя бы одно условие, в результате которого обеспечивается переход на один из нескольких возможных шагов (ветвей). В основе организации разветвления лежит проверка логического условия, которое может быть истинно или ложно. Частный вид логического условия – это операции типа =, ≠, ≥, >, ≤, <.

РИС. (5.2)41 Неполное ветвление (если-то) Полное ветвление (если-то-иначе)

В программах разветвляющейся конструкции присутствует условный оператор IF-THEN-ELSE (если – то – иначе) – применяется для выбора из двух альтернатив (в алгоритме неполного ветвления ветвь [ELSE <on 2>] может отсутствовать.)

IF <выражение> THEN <on 1> [ELSE <on 2>]

<выражение> - выражение арифметического типа (условие)

5.2.3. Алгоритмическая конструкция «Цикл». Операторы цикла

Алгоритм циклической структуры - алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий для различных значений данных. Эту последовательность называют циклом. Цикл – многократное повторенние одного или нескольких действий (тел цикла, серии команд)

Циклический алгоритм м.б.

· с параметром

· с условием

Цикл с параметром, (Цикл Для, цикл с известным числом повторений) - означает повторение действий несколько раз, сколько умещается между начальным (а), и конечным (в) значениями переменной величины (h), которая задаёт число повторений и называется параметром цикла (счётчиком).

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

РИС. (5.2)42 Графическое изображение цикла с параметром

Цикл с известным числом повторений FOR (цикл с параметрами)

FOR <переменная> = <выр-1> TO <выр-2> [STEP <выр-3>]

<тело цикла>

NEXT <переменная>

FOR, TO, STEP, NEXT – ключевые слова

<выр-1>, <выр-2>, <выр-3> - арифметические выражения, определяющие соответственно начальное значение параметра, конечное и шаг. Шаг м.б. положительным и отрицательным. Если он =1, то часть оператора в квадратных скобках – пропускают.

<тело цикла> - любое количество пронумерованных строк программы, содержащих повторяющиеся операторы

NEXT – признак окончания цикла.

Циклы с условием подразделяются на:

· циклы с предусловием - условие прекращения проверяется в начале (Цикл Пока – действия повторяются до тех пор, пока выполняется определённое условие)

· циклы с постусловием - условие прекращения проверяется в конце (Цикл Пока не – действия повторяются до тех пор, пока не выполнится определённое условие)

РИС. (5.2)43 Цикл с предусловием Цикл с предусловием

Цикл с неизвестным числом повторений (итерационный цикл)

Цикл с предусловием (WHILE-WEND) – осуществляется проверка условия цикла, а потом, если оно истинно, выполняется тело цикла

WHILE <выражение>

<тело цикла>

Дата добавления: 2017-02-01