Попов И.И., Матвеев А.А., Максимов Н.В. Архитектура электронно-вычислительных машин и систем (2004) (1186255), страница 9
Текст из файла (страница 9)
Первоначально в качествечисла М принимается a1, т. е. полагаем М = a1, после чего М сравниваемс последующими числами массива, начиная с а2. Если М < а2, то Мсравнивается с а3, если М <a3, то М сравнивается с а4, и так до тех пор,пока найдется число at < М. Тогда полагаем М = at и продолжаемсравнение с М последующих чисел из массива, начиная с at+1 и так дотех пор, пока не будут просмотрены п чисел. В результате просмотравсех п чисел М будет иметь значение, равное наименьшему числу измассива (I — текущий номер числа из массива).
Этот процесс можетбыть записан в виде следующей системы последовательных указаний:1. Полагаем i = 1 и переходим к следующему указанию.2. Полагаем х = ai и переходим к следующему указанию.3. Сравниваем i с п; если i < п, переходим к 4 указанию, если i = п,процесс поиска останавливаем.4. Увеличиваем i на 1 и переходим к следующему пункту.5. Сравниваем ai с М. Если М≥ai то переход к указанию 3, иначе(М<ai ) переход к пункту 2.В первом алгоритме в качестве элементарных операций используются простейшие арифметические операции умножения, которыемогли бы быть разложены на еще более элементарные операции.
Мытакого разбиения не делаем в силу простоты и привычностиарифметических правил.Алгоритмы, в соответствии с которыми решение поставленныхзадач сводится к арифметическим действиям, называются численнымиалгоритмами.Алгоритмы, в соответствии с которыми решение поставленныхзадач сводится к логическим действиям, называются логическимиалгоритмами. Примерами логических алгоритмов могут служитьалгоритмы поиска минимального числа, поиска пути на графе, поискапути в лабиринте и др.Алгоритмом, таким образом, называется последовательностьчетких однозначных указаний, которые, будучи применены копределенным имеющимся данным, обеспечивают получениетребуемого результата. Данными называют все величины, участвующиев решении задачи.
Данные, известные перед выполнением алгоритма,являются начальными, исходными данными. Результат решения задачи— это конечные, выходные данные. В задачах нахождения максимума изсписка чисел, или их произведения, исходными данными являютсясписки чисел; результат, или конечное данное - соответственно с и М.Каждое указание алгоритма предписывает исполнителювыполнить одно конкретное законченное действие. Исполнитель неможет перейти к выполнению следующей операции, не закончивполностью выполнения предыдущей. Предписания алгоритма надовыполнять последовательно одно за другим, в соответствии с указанным44порядком их записи. Выполнение всех предписаний гарантируетправильное решение задачи.Поочередное выполнение команд алгоритма за конечное числошагов приводит к решению задачи, к достижению цели.
Разделениевыполнения решения задачи на отдельные операции (выполняемыеисполнителем по определенным командам) — важное свойствоалгоритмов, называемое дискретностью.Анализ примеров различных алгоритмов показывает, что записьалгоритма распадается на отдельные указания исполнителю выполнитьнекоторое законченное действие. Каждое такое указание называетсякомандой. Команды алгоритма выполняются одна за другой. Послекаждого шага исполнения алгоритма точно известно, какая командадолжна выполняться следующей.
Алгоритм представляет собойпоследовательность команд (также - инструкций, директив),определяющих действия исполнителя (субъекта или управляемогообъекта).Таким образом, выполняя алгоритм, исполнитель может невникать в смысл того, что он делает, и вместе с тем получать нужныйрезультат. В таком случае говорят, что исполнитель действуетформально, т. е. отвлекается от содержания поставленной задачи итолько строго выполняет некоторые правила, инструкции.Это очень важная особенность алгоритмов.
Наличие алгоритмаформализовало процесс, исключило рассуждения. Если обратиться кпримерам других алгоритмов, то можно увидеть, что и они позволяютисполнителю действовать формально. Таким образом, созданиеалгоритма дает возможность решать задачу формально, механическиисполняя команды алгоритма в указанной последовательности.Построение алгоритма для решения задачи из какой-либо областитребует от человека глубоких знаний в этой области, бывает связано стщательным анализом поставленной задачи, сложными, иногда оченьгромоздкими рассуждениями. На поиски алгоритма решения некоторыхзадач могут быть потрачены многие годы. Но когда алгоритм создан,решение задачи по готовому алгоритму уже не требует каких-либорассуждений и сводится только к строгому выполнению командалгоритма.Всякий алгоритм составляется в расчете на конкретногоисполнителя с учетом его возможностей.
Для того чтобы алгоритм могбыть выполнен, нельзя включать в него команды, которые исполнительне в состоянии выполнить. У каждого исполнителя имеется свойперечень команд, которые он может исполнить. Совокупность команд,которые могут быть выполнены исполнителем, называется системойкоманд исполнителя.Каждый алгоритм строится в расчете на некоторого исполнителя.Для того чтобы исполнитель мог решить задачу по заданному алгоритмунеобходимо, чтобы он был в состоянии понять и выполнить каждое45действие, предписываемое командами алгоритма. Каждая командаалгоритма должна определять однозначное действие исполнителя. Такоесвойство алгоритмов называется определенностью (или точностью)алгоритма.Алгоритм, составленный для конкретного исполнителя, долженвключать только те команды, которые входят в его систему команд.
Этосвойство алгоритма называется понятностью. Алгоритм не долженбыть рассчитан на принятие каких-либо самостоятельных решенийисполнителем, не предусмотренных составлением алгоритма.Еще одно важное требование, предъявляемое к алгоритмам, —результативность (или конечность) алгоритма. Оно означает, чтоисполнение алгоритма должно закончиться за конечное число шагов.Массовость.
Разработка алгоритмов - процесс творческий,требующий умственных усилий и затрат времени. Поэтомупредпочтительно разрабатывать алгоритмы, обеспечивающие решениявсего класса задач данного типа. Например, если составляется алгоритмрешения кубического уравнения ax 3 + bx 2 + cx + d = 0 , то он должен бытьвариативен, т. е. обеспечивать возможность решения для любыхдопустимых исходных значений коэффициентов a, b, c, d.
Про такойалгоритм говорят, что он удовлетворяет требованию массовости.Свойство массовости не является необходимым свойством алгоритма.Оно скорее определяет качество алгоритма; в то же время свойстваточности, понятности и конечности являются необходимыми (иначе этоне алгоритм).Запись алгоритмов в виде блок-схемАлгоритмы можно записывать по-разному. Форма записи, состав иколичество операций алгоритма зависят от того, кто будет исполнителемэтого алгоритма.
Если задача решается с помощью ЭВМ, алгоритмрешения задачи должен быть записан в понятной для машины форме, т.е. в виде программы. Всякий алгоритм может быть:- записан на естественном языке;- изображен в виде блок-схемы;- записан на алгоритмическом языке;Схема алгоритма – графическое представление алгоритма,дополняется элементами словесной записи. Каждый пункт алгоритмаотображается на схеме некоторой геометрической фигурой – блоком.Причем правило выполнения схем алгоритмов регламентирует ГОСТ19.002–80 (единая система программной документации) см. табл.
5.Блоки на схемах соединяются линиями потоков информации.Основное направление потока информации идет сверху вниз и слеванаправо (стрелки могут не указываться), снизу–вверх и справа налево —стрелка обязательна. Количество входящих линий для блока не46ограничено. Выходящих линий – одна, за исключением логическогоблока.Таблица 5Основные элементы блок-схем№п/пСимволНаименование1.Блок вычислений2.Логический блок3.4.5.СодержаниеВычислительные действия илипоследовательность действий.Выборнаправлениявыполненияалгоритмавзависимости от некоторогоусловия.Блокиввода- 1. Общие обозначения вводавывода данных(вывода)данных(внезависимости от физическогоносителя)2. Вывод данных, носителемкоторых является документ.Начало (конец)Начало или конец алгоритма,вход или выход в программу.6.Процесспользователя(подпрограмма)Блок модификации7.Соединитель8.МежстраничныесоединенияВычисление по стандартнойпрограмме или подпрограммеФункция выполняет действия,изменяющиепункты(например, заголовок цикла)алгоритма.Указание связи прерваннымилиниями между потокамиинформациивпределаходного листа.Указаниесвязимеждуинформациейнаразныхлистах.47Размеры поГОСТ19.003–80(ЕСПД):а=10,15,20ммb=1.5*аБазовые структуры алгоритмов - это определенный наборблоков и стандартных способов их соединения для выполнениятипичных последовательных действий.
К основным структурамотносятся следующие - линейные (Рис. 5.а), разветвляющиеся (Рис. 5.б),циклические (Рис. 5.в).Рис. 5. Базовые структуры алгоритмов и программЛинейными называются алгоритмы, в которых действияосуществляются последовательно друг за другом.
Стандартная блоксхема линейного алгоритма приводится на Рис. 6 а (вычисление суммыдвух чисел - А и В).Разветвляющимся называется алгоритм, в котором действиевыполняется по одной из возможных ветвей решения задачи, взависимости от выполнения условий. В отличие от линейныхалгоритмов, в которых команды выполняются последовательно одна задругой, в разветвляющиеся алгоритмы входит условие, в зависимости отвыполнения или невыполнения которого выполняется та или инаяпоследовательность команд (серий).В качестве условия в разветвляющемся алгоритме может бытьиспользовано любое понятное исполнителю утверждение, котороеможет соблюдаться (быть истинно) или не соблюдаться (быть ложно).Такое утверждение может быть выражено как словами, так и формулой.Таким образом, команда ветвления состоит из условия и двухпоследовательностей команд.Примеромможетявлятьсяразветвляющийсяалгоритм,изображенный в виде блок-схемы (Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
