Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Понятие об алгоритмах)

Содержание:

ВВЕДЕНИЕ

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

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

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

Глава 1. Понятие об алгоритмах

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

Слово «Алгоритм» происходит от algorithmi – латинского написания имени аль-Хорезми. Под этим именем в средневековой Европе знали величайшего математика из Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783-850 гг.

В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком [1, с. 4].

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

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

К 1950 г. алгорисмус стал алгорифмом. С термином алгорифма чаще всего связывали алгорифмы Евклида [2, с. 8].

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

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

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

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

Каждый алгоритм создается в расчете на вполне конкретного исполнителя.

Те действия, которые может совершать исполнитель, называются его допустимыми действиями. Совокупность допустимых действий образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя [1, с. 4].

1.2. Данные и величины

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

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

Например, при решении квадратного уравнения ах 2 + Ьх + с = 0 исходными данными являются коэффициенты а, Ь, с; результатами — корни уравнения х 1и х 2 ; промежуточным данным — дискриминант уравнения D = Ь² — 4ас.

Для успешного освоения программирования необходимо усвоить следующее правило: всякая величина занимает свое определенное место в памяти ЭВМ (иногда говорят — ячейку памяти). Хотя термин «ячейка» с точки зрения архитектуры современных ЭВМ несколько устарел, однако в учебных целях его удобно использовать [5, с. 7-8].

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

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

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

Типы констант определяются по контексту (т.е. по форме записи в тексте), а типы переменных устанавливаются в описаниях переменных. Есть еще один вариант классификации данных — классификация по структуре. Данные делятся на простые и структурированные. Для простых величин (их еще называют скалярными) справедливо утверждение: одна величина — одно значение, для структурированных: одна величина — множество значений.

К структурированным величинам относятся массивы, строки, множества и т.д. [5, с. 8-9].

ЭВМ — исполнитель алгоритмов. Как известно, всякий алгоритм (программа) составляется для конкретного исполнителя в рамках его системы команд. О каком же исполнителе идет речь при обсуждении вопроса о программировании для ЭВМ? Ответ очевиден: исполнителем является компьютер. Точнее говоря, исполнителем является комплекс ЭВМ + Система программирования (СП). Программист составляет программу на том языке, на который ориентирована СП.

Независимо от того, на каком языке программирования будет написана программа, алгоритм решения любой задачи на ЭВМ может быть составлен из команд:

• присваивания;

• ввода;

• вывода;

• обращения к вспомогательному алгоритму;

• цикла;

• ветвления [5, с. 9-10].

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

Данное выше определение алгоритма нельзя считать строгим - не вполне

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

Такими свойствами являются:

Дискретность (прерывность, раздельность) - алгоритм должен представлять процесс решения задачи как последовательное выполнение простых

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

предыдущего.

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

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

дополнительных указаний или сведений о решаемой задаче.

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

задачи за конечное число шагов.

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

Само же выражение «свойства алгоритма» не совсем корректно. Свойствами обладают объективно существующие реальности. Можно говорить, например, о свойствах какого-либо вещества. Алгоритм – искусственная конструкция, которую мы сооружаем для достижения определенных целей. Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам.

Поэтому нужно говорить все же не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму [1, с. 5-6].

Первое правило – при построении алгоритма, прежде всего, необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные.

Это правило позволяет сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

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

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

В языках программирования распределение памяти осуществляется декларативными операторами (операторами описания переменных). При запуске программы транслятор языка анализирует все идентификаторы в тексте программы и отводит память под соответствующие переменные.

Третье правило – дискретность. Алгоритм строится из отдельных шагов

(действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно [1, с. 6-7].

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

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

Итак, алгоритм – неопределяемое понятие теории алгоритмов. Алгоритм

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

1.4. Виды алгоритмов и их реализация

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

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

Механические алгоритмы, или иначе детерминированные, жесткие (например, алгоритм работы машины, двигателя и т.п.);

Гибкие алгоритмы, например стохастические (вероятностные) и эвристические.

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

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

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

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

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

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

Цикл программы – последовательность команд (серия, тело цикла), которая

может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия.

Вспомогательный (подчиненный) алгоритм (процедура) – алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.

В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм [1, с. 7-9].

1.5. Методы изображения алгоритмов

На практике наиболее распространены следующие формы представления алгоритмов:

словесная (записи на естественном языке);

графическая (изображения из графических символов);

псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

программная (тексты на языках программирования).

Словесное описание алгоритма

Данный способ получил значительно меньшее распространение из-за его

многословности и отсутствия наглядности.

Рассмотрим пример на алгоритме нахождение максимального из двух значений:

Определим форматы переменных X, Y, M, где X и Y – значения для сравнения, M – переменная для хранения максимального значения;

получим два значения чисел X и Y для сравнения;

сравним X и Y.

если X меньше Y, значит большее число Y.

Поместим в переменную M значение Y.

Если X не меньше (больше) Y, значит большее число X.

Поместим в переменную M значение X [1, с. 9].

Рассмотрим еще пример алгоритма (вычисление корней квадратного уравнения) на естественном языке:

1. Ввести в компьютер числовые значения переменных а, b и с.

2. Вычислить дискриминант по формуле d = b² - 4ас.

3. Если d < 0, то напечатать сообщение «Корней нет» и перейти к

п.4. Иначе вычислить 𝑥₁ =(−𝑏+√D)/2𝑎, 𝑥₂ =(−𝑏−√D)/2𝑎 и напечатать

значения x₁ и x₂.

4. Прекратить вычисления [3, с. 7].

Уточним понятие словесного представления алгоритма на примере нахождения факториала числа n (c=n!), т.е. вычисления по формуле с=1*2*3*4…n:

1. Полагаем с равным 1 и переходим к следующему пункту.
2. Полагаем i равным 1 и переходим к следующему пункту.
3. Полагаем с=i*c и переходим к следующему пункту.
4. Проверяем, равно ли число i числу n. Если равно, то вычисления прекращаем. Если i<n, то увеличиваем i на 1 и переходим к пункту 3 [2, с. 8-9].

Словесный способ не имеет широкого распространения по следующим причинам:

такие описания строго не формализуемы;

страдают многословностью записей;

допускают неоднозначность толкования отдельных предписаний.

Блок-схема алгоритма

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

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

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

Можно встретить даже такое утверждение: «Внешне алгоритм представляет собой схему – набор прямоугольников и других символов, внутри которых записывается, что вычисляется, что вводится в машину и что выдается на печать и другие средства отображения информации». Здесь форма представления алгоритма смешивается с самим алгоритмом.

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

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

Вспомним основные условные обозначения, используемые при графической записи алгоритма [1, с. 11]:

Рис.1. Основные условные графические обозначения [1, с. 11]

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

уравнения, описанного выше [3, с. 8]:

Рис.2. Блок-схема алгоритма решения квадратного уравнения

Псевдокод

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

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

В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций [1, с. 11-12].

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

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

Однако на практике в качестве исполнителей алгоритмов используются

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

Следовательно, язык для записи алгоритмов должен быть формализован.

Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера [1, с. 12].

1.6. Классификация алгоритмов. Базовые структуры.

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

К основным структурам относятся следующие: линейные (рис 3, а), разветвляющиеся (рис 3, б), циклические (рис 3, в, г) [2, с. 13-14].

Рис.3. Базовые структуры алгоритмов и программ

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

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

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

Примером может являться разветвляющийся алгоритм, изображенный на рисунке 4, б.

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

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

Возможен другой случай, когда тело цикла выполняется хотя бы один раз, и будет выполняться до тех пор, пока не станет истинным условие. Такая организация цикла, когда тело цикла расположено до проверки условия, носит название цикл с постусловием [2, с. 14-16].

Пример цикла пока изображен на рисунке 4, в [2, с. 16].

Рис.4. Примеры структур алгоритмов

Глава 2. Основные структуры алгоритмов и их примеры

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

Линейный алгоритм. В котором все операции выполняются

последовательно одна за другой (рис. 5) [3, с. 9].

Рис.5. Блок-схема линейного алгоритма

Рассмотрим пример линейного алгоритма.

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

Пусть a, b, c – длины сторон треугольника. Необходимо найти S – площадь треугольника, P – периметр.

Для нахождения площади можно воспользоваться формулой Герона:

S = (r(r − a)(r − b)(r − c))^1/2,

где r – полупериметр.

Входные данные: a, b, c. Выходные данные: S, P.

Блок-схема алгоритма представлена на рис. 6 [3, с. 9-10].

Рис.6. Пример линейного алгоритма

Внимание! В этих блоках знак «=» означает не математическое равенство, а операцию присваивания. Переменной, стоящей слева от оператора, присваивается значение, указанное справа. Причем это значение может быть уже определено или его необходимо вычислить с помощью выражения. Например, операция r = (a+b+c)/2 – имеет смысл (переменной r присвоить значение (a+b+c)/2), а выражение (a+b+c)/2=r – бессмыслица [3, с. 9].

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

Он включает последовательное выполнение следующих этапов:

ввод исходных данных в память ЭВМ;

вычисление искомых величин по формулам;

вывод результатов из памяти ЭВМ на информационный носитель.

Пример. Составить алгоритм вычисления площади круга по формуле

S= πR². Решение показано на рис. 7 [1, с. 15]

Рис.7. Вычисление площади круга

2.2 Разветвленный алгоритм

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

В блок-схемах разветвленные алгоритмы изображаются так, как показано на рис. 8 [3, с. 10].

Рис.8. Полный и неполный разветвленный алгоритм

Рассмотрим пример разветвленного алгоритма.

Даны три числа а, b, с. Найти наибольшее из них.

Блок-схема алгоритма представлена на рис. 9 [3, с. 11].

Рис.9. Алгоритм поиска наибольшего из трех чисел

Пример 2. Составить алгоритм решения для функции F(x) = 1 при x > 0 и F(x) = 0 при x < 0. Блок - схема разветвляющегося алгоритма показана на рис.10 [1, с. 16].

Рис.10. Нахождение функции F

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

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

Существует два типа алгоритмов циклической структуры. На рис. 11 изображен цикл с предусловием, а на рис. 12 – цикл с постусловием [3, с. 11-12].

Рис.11. Алгоритм цикла с предусловием

Рис.12. Алгоритм цикла с постусловием

Эти циклы взаимозаменяемы и обладают некоторыми отличиями:

• в цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием – после тела цикла;

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

• в цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием – условие выхода из цикла.

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

Обязательные блоки для организации цикла:

1. Установка начального значения параметра цикла.

2. Проверка условия достижения конечного значения параметра цикла.

3. Изменение параметра цикла.

Рассмотрим пример циклического алгоритма на рис 13 [3, с. 11-13]:

Рис.13. Пример циклического алгоритма

Пример 2. Составить алгоритм решения задачи вычисления N первых членов геометрической прогрессии, используя формулу b_n+1 =b_n *q для любых b и q, где n - текущий член геометрической прогрессии.

Блок-схема алгоритма решения данного примера показана в двух вариантах: с использованием цикла "ДО" (рис. 14, а) и цикла "ПОКА" (рис. 14, б) [1, с. 18].

Рис.14. Вычисление членов геометрической прогрессии

Пример циклов с неизвестным числом повторений.

Примером циклов, число повторений которых не задано, являются итерационные вычислительные процессы. В них решение задачи реализуется путем последовательного приближения к искомому результату. Процесс является циклическим, поскольку заключается в многократных вычислениях. Начальное приближение Y0 выбирается заранее или задается по определенным правилам. Заканчивается итерационное вычисление при выполнении условия |Yi -Yi-1| <d , где d - допустимая ошибка вычисления.

Типовая структура алгоритма итерационных вычислений имеет вид, показанный на рис. 15 [1, с. 19]:

Рис.15. Типовая структура алгоритма итерационных вычислений

Пример. Составить алгоритм вычисления функции y=√x c точностью d,

используя рекуррентную формулу yi+1=0.5*(x/yi +yi).

Если начальное приближение y1=x, тогда на первом цикле вычисления будем иметь y=0.5*(x/y1 +y1).

Блок - схема алгоритма решения примера 4 приведена на рис. 16 [1, с. 20]:

Рис.16. Алгоритм вычисления функции y= √x c точностью d

Сложные циклы

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

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

y = x*z / (A + B) при изменении аргументов 1< x < 10 c шагом ∆x = 2 и

1< z <4 с шагом ∆z = 0.5.

Решение данного примера показано на рис. 17.

Внутренний цикл организован по переменной z , а внешний - по переменной x . На каждом шаге изменения переменной x (переменной внешнего цикла) переменная z (переменная внутреннего цикла) проходит весь заданный диапазон изменения от 1 до 4 с шагом 0.5.

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

Первая цифра внутри фигуры (рис. 19) определяет начальное значение переменной, вторая ее конечное значение, а третья - шаг изменения переменной. По умолчанию (при отсутствии последней цифры) шаг изменения переменной принимается равным 1 [1, с. 21-22].

Рис.17. Вычисление функции y [1, с. 21]

Рис.18. Вычисление функции y (модифицированная блок-схема) [1, с. 21]

Рис.19. Упрощенная блок-схема цикла [1, с. 22]

ЗАКЛЮЧЕНИЕ

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Аузяк А.Г., Богомолов Ю.А., Маликов А.И., Старостин Б.А. Программирование и основы алгоритмизации (учебное пособие) / А.Г. Аузяк, Ю.А. Богомолов, А.И. Маликов, Б.А. Старостин. – Казань: Изд-во Казанского национального исследовательского технического ун-та - КАИ, 2013. – 153 с.
2. Голицина О.Л., Попов И.И. Основы алгоритмизации и программирования / О.Л. Голицина, И.И. Попов – М: Форум, 2008. – 432 с.
3. Кадырова Г. Р. Основы алгоритмизации и программирования (учебное пособие) / Г. Р. Кадырова. – Ульяновск: УлГТУ, 2014. – 95 с.
4. Семакин И.Г., Шестаков А.П. Основы алгоритмизации и программирования: учебник для студ. учреждений сред. проф. образования / И.Г. Семакин, А.П. Шестаков. – М: Издательский центр «Академия», 2012, 400 с.
5. Семакин И.Г., Шестаков А.П. Основы программирования: учебник / И.Г. Семакин, А.П. Шестаков. – М: Мастерство, 2002, 432 с.

Приложения

Приложение 1

Таблица 1

Основные типы данных

Источник: Основы алгоритмизации и программирования: учебник для студ. учреждений сред. проф. образования / И.Г. Семакин, А.П. Шестаков. – М: Издательский центр «Академия», 2012, 400 с.