Основы программирования циклы ветвления

Алгоритм и свойства алгоритма¶

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

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

• Конечность. Должен заканчиваться за конечное число шагов.
• Элементарность (понятность). Каждый шаг алгоритма должен быть простым, чтобы устройство, выполняющее операции,могло выполнить его одним действием
• Дискретность. Процесс решения задачи представляется конечной последовательностью отдельных шагов, и каждый шаг алгоритма выполняется за конечное (не обязательно единичное) время.
• Детерминированность (определенность). Каждый шаг алгоритма должен быть однозначно и недвусмысленно определен и не должен допускать произвольной трактовки. После каждого шага либо указывается, какой шаг делать дальше, либо дается команда остановки, после чего работа алгоритма считается законченной.
• Результативность. Алгоритм имеет некоторое число входных величин — аргументов. Цель выполнения алгоритма состоит в получении конкретного результата, имеющего отношение к исходным данным.
• Массовость. Алгоритм должен быть применим для некоторого класса задач, различающихся лишь исходными данными.
• Эффективность. Необходимо приводить алгоритм к состоянию, чтобы он состоял из минимального числа шагов и при этом решение удовлетворяло бы условию точности и требовало минимальных затрат других ресурсов.

Типы алгоритмических моделей¶

1. Вычислительный алгоритм
2. Устройство, выполняющее примитивные операции
3. Формальные алгоритмы

Запись алгоритма на некотором языке представляет собой программу. Если программа написана на специальном алгоритмическом языке (например, на ПАСКАЛе или С++), то говорят об исходной программе. Программа, написанная на языке, который непосредственно понимает компьютер (как правило, это двоичные коды), называется машинной, или двоичной.

Основные способы записи алгоритмов¶

• вербальный — алгоритм описывается на человеческом языке;
• символьный — алгоритм описывается с помощью набора символов;
• графический — алгоритм описывается с помощью набора графических изображений.

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

Базовые алгоритмические структуры¶

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

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

Ветвление¶

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

1. Неполная форма ветвления (если…то, if…then)

1. Полная форма ветвления (если…то…иначе, if…then…else)

1. Выбор (select case)

Цикл¶

Форма организации действий, при которой одна и та же последовательность шагов алгоритма выполняется несколько раз или ни разу в зависимости от проверяемого условия

1. Цикл с параметром (for) – тело цикла выполняется для всех значений некоторой переменной (параметра цикла) в заданном диапазоне;

1. Цикл с предусловием (while) – тело цикла выполняется до тех пор, пока выполняется условие;

1. Цикл с постусловием (repeat…until) – тело цикла выполняется до тех пор, пока условие не выполняется;

1. Вложенные циклы

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

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

Данные и величины¶

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

Совокупность величин, с которыми работает компьютер.

По отношению к программе различают исходные, окончательные (результаты) и промежуточные данные, которые получают в процессе вычислений. Величина имеет три основных свойства: имя, значение и тип. На уровне команд процессора величина идентифицируется при помощи адреса ячейки памяти, в которой она хранится. В алгоритмах и языках программирования величины делятся на константы и переменные Костанта — неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.7, k, true и т.д. Переменная может изменять свои значения в ходе выполнения программы и представляется символическим именем — идентификатором, например: X, S2, cod 15.

определяет множество значений, которые может принимать переменная и множество допустимых опе:раций

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

Примеры алгоритмов¶

Линейный вычислительный алгоритм¶

Создать алгоритм деления обыкновенных дробей.

Математическая модель:

1. Числитель первой дроби умножить на знаменатель второй дроби.
2. Знаменатель первой дроби умножить на числитель второй дроби.
3. Записать дробь, числитель которой есть результат выполнения пункта 1, а знаменатель — результат выполнения пункта 2.

Блок — схема и текст на алгоритмическом языке (псевдокоде) выглядят следующим образом:

Данный алгоритм имеет линейную структуру. В нем все команды выполняются в строго однозначной последовательности, каждая по одному разу. Линейный алгоритм составляется из команд присваивания, ввода, вывода. При описании алгоритмов в блок-схемах типы, как правило,не указываются (но подразумеваются). В алгоритмах на АЯ для всех переменных типы указываются явно. Описание типов переменных производится сразу после заголовка алгоритма. В них используются следующие обозначения типов: цел — целый тип, вещ — вещественный тип, лит — символьный (литерный) тип, лог — логический тип. В алгоритме для деления дробей для всех переменных указан целый тип.

Ветвление¶

Составить алгоритм решения квадратного уравнения ax 2 + bx + c = 0

Математическая модель

Решением в общем случае будут два корня x₁, и x₂ , которые вычисляются по формуле:

Блок-схема алгоритма представлена на рисунке

Циклы¶

Дано целое положительное число п. Требуется вычислить n! (n-факториал).

Математическая модель

Таблица трассировки

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

Блок-схема В алгоритме используются три переменные целого типа: n — аргумент; i—промежуточнаяпеременная; F — результат. Для проверки правильности алгоритма построена трассировочная таблица.

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

Выполнение серии команд (тела цикла) повторяется, пока условие цикла истинно. Когда условие становится ложным, цикл заканчивает выполнение. Служебные слова нц и кц обозначают начало цикла и конец цикла соответственно.

Вспомогательные алгоритмы¶

Алгоритм, целиком используемый в составе другого алгоритма.

Составить алгоритм вычисления степенной функции с целым показателем у = х k , где к — целое число, не равное 0

Математическая модель

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

Дважды используется команда обращения к вспомогательному алгоритму с именем СТЕПЕНЬ. Это алгоритм возведения вещественного основания в целую положительную степень путем его многократного перемножения. Величины, стоящие в скобках в команде обращения к вспомогательному алгоритму, называются фактическими параметрами. Вспомогательные алгоритмы оформляются в виде процедур. Процедура СТЕПЕНЬ будет выглядеть так:

а и k — формальные параметры-аргументы, z — параметр-результат. Между формальными и фактическими параметрами процедуры должны выполняться следующие правила соответствия: * по количеству (сколько формальных, столько и фактических параметров); * по последовательности (первому формальному соответствует первый фактический параметр, второму — второй и т.д.); * по типам (типы соответствующих формальных и фактических параметров должны совпадать)

Обращение к процедуре инициирует следующие действия:

1. Значения параметров-аргументов присваиваются соответствующим формальным параметрам.
2. Выполняется тело процедуры (команды внутри процедуры).
3. Значение результата передается соответствующему фактическому параметру, и происходит переход к выполнению следующей команды основного алгоритма.

Использование процедур позволяет строить сложные алгоритмы методом последовательной детализации

Источник