Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Блок-схема алгоритма).pdf

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

Для примера 1 блок-схема будет выглядеть так:

начало

Инициализация константы Pi

Ввод переменной

R

S=Pi*R**2

Вывод S

конец

Псевдокод и программное представление алгоритма

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

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

Для примера 1 текст программы на «псевдоязыке» будет выглядеть так:

инициализация константы (Pi)

ввод переменной R

S=Pi*R**2

вывод S

На практике в качестве исполнителей алгоритмов используются специальные автоматы – компьютеры. Алгоритм для компьютера должен быть написан на «понятном» ему языке. Такой языке принято называть языком программирования, а запись алгоритма на таком языке – программой. Теперь мы можем написать полноценную программу. На языке Python программа для примера 1 будет выглядеть так:

Pi=3.14

R=float(input('Введите радиус круга '))

S=Pi*R**2

print ("Площадь круга равна: ", S)

Словесное описание алгоритма 
Данный способ получил значительно меньшее распространение из-за его 
многословности и отсутствия наглядности. 
Словесный способ не имеет широкого распространения по следующим причинам: 
• такие описания строго не формализуемы; 
• страдают многословностью записей; 
• допускают неоднозначность толкования отдельных предписаний.

Порядок разработки иерархической системы реализации алгоритмов

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

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

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

1. Условная конструкция. Этот блок включает проверку некоторого логического условия (Р), в зависимости от которого выполняется либо один (S1), либо другой (S2) операторы:

S2

S1

P

1. Блок обобщенного цикла. Этот блок обеспечивает многократное повторение выполнения оператора S пока выполнено логическое условие P

S

­P

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

Глава II

Ветвление и операторы выбора

В решениях задач по алгоритмизации одним из важнейших элементов является так называемое «ветвление».

Начало

Ввод данных

Условие

Нет

Действия «нет»

Да

Действия «да»

Вывод

Конец

Если условие, указанное в блоке «Условие», выполняется, то далее производятся действия, соответствующие «ветви ДА», иначе выполняются действия, соответствующие «ветви НЕТ». Условия нужно составлять так, чтобы результат проверки любого условия допускал только два исхода – условие либо выполняется, либо не выполняется.

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

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

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

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

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

В языках программирования для обеспечения проверки условий используется специальный составной оператор IF («если»). В этом операторе указывается условие, которое нужно проверить, и действия для ветвей «ДА» и «НЕТ».

Начало

Ввод Данных

Условие 1

Условие 2

Действия «да» 1

Условие N

Действия «да» 2

Действия «да» N

Действия «Нет»

Вывод результатов

Конец

Пример 2. Можно ли из бревна, имеющего диаметр поперечного сечения D, выпилить квадратный брус шириной A?

Постановка задачи: Исходными данными является значение диаметр бревна R, и ширина бруса А. Максимальную ширину бруса для заданного диаметра бревна можно определить из формулы радиуса описанной возле квадрата со стороной А окружности: . Необходимо сформировать строку S. При . S="брус можно выпилить" иначе S="брус нельзя выпилить".

Текст программы на «псевдоязыке»:

ввод D

ввод A

из D получаем R=D/2

если ( ) то

S=”брус можно выпилить”

иначе

S=”брус нельзя выпилить”

конец если

вывод S (рис)

Начало

D , A

R = D/2

A <2*R

Нельзя

Можно

Конец

Текст на Python:

from math import sqrt

D=float (input("Введите диаметр бревна") )

R=D/2

a=float(input("Введите ширину бруса") )

if a<R*sqrt(2):

S="брус можно выпилить"

else:

S="брус нельзя выпилить"

print (S)

Пример 3. На том же примере 2 мы так же можем предоставить выбор единицы измерения: метр (“m”), или миллиметр (“mm”), для чего вводим флаг F.

Текст программы на «псевдоязыке»:

Ввод F

ввод D

ввод A

из D получаем R=D/2

если ( ) то

S=”брус можно выпилить”

иначе

S=”брус нельзя выпилить”

конец если

вывод S (рис)

Текст программы на Python:

from math import sqrt

F=input ("Какую единицу измерения хотите использовать? Введите m - метр, mm - миллиметр ")

D=float (input("Введите диаметр бревна "))

R=D/2

a=float(input("Введите ширину бруса "))

if a<R*sqrt(2):

if F=="m":

S=["брус шириной",a, "m", "можно выпилить "]

elif F=="mm":

S=["брус шириной",a, "mm","можно выпилить "]

else:

if F=="m":

S=["брус шириной",a, "m","нельзя выпилить "]

elif F=="mm":

S=["брус шириной",a, "mm", "нельзя выпилить "]

print (S[0],S[1],S[2],S[3])

Пример работы программы:

Метры

Какую единицу измерения хотите использовать? Введите m - метр, mm - миллиметр m

Введите диаметр бревна 2

Введите ширину бруса 1

брус шириной 1.0 m можно выпилить

>>>

Миллиметры

Какую единицу измерения хотите использовать? Введите m - метр, mm - миллиметр mm

Введите диаметр бревна 200

Введите ширину бруса 160

брус шириной 160.0 mm нельзя выпилить

>>>

Операторы ввода-вывода

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

Прямоугольным параллелепипедом называется прямой параллелепипед, основания которого прямоугольники (рис. 5).

Рис. 5. Прямоугольный параллелепипед.

Площадь его поверхности: S = 2*(ab+ac+bc), (3)

где a, b, c - длина, ширина и высота параллелепипеда.

2.3 АЛГОРИТМ программы

Приведем текстовую интерпретацию алгоритма. Программа состоит из следующих шагов:

Шаг 1 - ввод исходных данных - параметров фигур.

Шаг 2 - открытие цикла с предусловием (while) по высоте шарового сегмента.

Шаг 3 - вычисление площади поверхности шарового сегмента и радиуса его основания.

Шаг 4 - открытие второго, вложенного цикла также с предусловием по стороне параллелепипеда с.

Шаг 5 - вычисление площади поверхности параллелепипеда.

Шаг 6 - проверка условия, что если текущее значение высоты меньше минимального и одновременно (оператор &) площадь поверхности шарового сегмента не меньше площади поверхности параллелепипеда, то считать текущее значение высоты и радиуса основания сегмента минимальным

Шаг 7 - наращивание счетчика вложенного цикла

Шаг 8 - если параметр вложенного цикла не удовлетворяет условию c<=c2, то выход из цикла.

Шаг 9 - наращивание счетчика внешнего цикла

Шаг 10 - если параметр этого цикла не удовлетворяет условию h>=h2, то выход из цикла.

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

Шаг 12 - завершение работы программы.

Примечание: цикл с предусловием выполняется, пока условие верно.

Глава III

Циклы. Обработка последовательностей и одномерных и двумерных массивов

Циклом называется фрагмент алгоритма или программы, который может повторяться несколько раз (в том числе и нуль раз). Каждая циклическая конструкция начинается заголовком цикла и заканчивается конечным оператором. Между ними располагаются операторы, называемые «телом цикла».

Рис. 2.9: Пример блок-схемы цикла с параметром.

Начало

Ввод данных

i от N1 до N2 шаг K

Вывод результатов

Действия 1

Действия N

Конец

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

Для организации циклов с параметром в языках программирования используется составной оператор FOR («для»), а в циклах с условием чаще всего используется составной оператор WHILE («пока»).

n = int(input())

factorial = 1

while n > 1:

factorial *= n

n -= 1

Пример работы программы: