![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Проектирование алгоритмов и основные их типы ⇐ ПредыдущаяСтр 3 из 3
Способ записи алгоритма должен соответствовать следующим требованиям: · обеспечивать компактность и наглядность; · быть понятным широкому кругу лиц; · содержать строгие правила записи алгоритма; · обеспечивать простой и формальный перевод на языки программирования. При записи алгоритма любым способом существует общая методика: каждый алгоритм должен иметь имя, раскрывающее его смысл; необходимо обозначить начало и конец алгоритма; описать входные и выходные данные (результат работы алгоритма); предусмотреть команды, которые позволяют выполнять определенные действия над введенными данными, т.е. схематично алгоритм может иметь следующий вид.
Алгоритм, составленный для некоторого исполнителя, можно представить разными способами: с помощью словесного описания (записывается на натуральном, как правило, профессиональном языке предметной области в произвольной форме), формульно-словесного (здесь словесное описание дополняется математическими формулами), на алгоритмическом языке (выполняется по строгим правилам и особенностями построения конструкций конкретного алгоритмического языка), с помощью графики (изображений из графических символов) и др., например, операторные схемы (где каждый блок, выполняющий определенную функцию, обозначается символом-оператором, т.е. конкретной буквой, записываемой слева направо в последовательности выполнения, имеющей индекс порядкового номера), псевдокод (способ записи алгоритма с помощью операторов, близких к алгоритмическим языкам и предложений на естественном языке). Выделим графическое описание алгоритма, который называется блок-схемой (как наиболее компактный, наглядный и получивший широкое распространение).
На рисунке изображены «функциональная» (a) вершина, имеющая один вход и один выход; «предикатная» (б) вершина, имеющая один вход и два выхода. В этом случае функция Р передает управление по одной из ветвей в зависимости от значения Р (Т, т.е. true, означает «истина», F, т.е. false - «ложь»); «объединяющая» (в) вершина (вершина «слияния»), обеспечивающая передачу управления от одного из двух входов к выходу. Иногда вместо Т пишут «да» (либо знак +), вместо F- «нет» (либо знак -). На практике при составлении блок-схем оказывается удобным использовать и другие графические знаки, например:
Из данных элементарных блок-схем можно построить следующие базовые блок-схемы, имеющих особое значение для практики алгоритмизации.
Ветвящийся алгоритм - ход решения задачи определяется в зависимости от условия (переход и ветвление).
Да Проверка Нет условия
Выбор направления продолжения вычислительного процесса осуществляется проверкой выполнения заданного условия (в зависимости от этого в каждом конкретном случае вычислительный процесс реализуется только по одной ветви, выполнение остальных условий исключается). Ветвящиеся процессы описываются оператором IF: IF < условие> THEN < оператор1> ELSE < оператор2> - условный оператор; GOTO < номер строки> - безусловный переход; Вычислительный процесс называется ветвящимся, если для его реализации предусмотрено несколько направлений - ветвей (ветвящийся процесс, включающий в себя две ветви, называется простым, более двух - сложным). Каждое направление процесса обработки данных является отдельной ветвью вычислений. Выбор направления зависит от заранее определенного признака (который может относиться к исходным данным, к промежуточным или конечным результатам). Направление ветвления выбирается логической проверкой, в результате которой возможны два ответа: «да» - условие выполнено и «нет» - условие не выполнено. Циклический алгоритм – описывает повторяющиеся действия.
Проверка 100 условия
Да
Циклические процессы описываются следующим оператором: FOR х = 1 ТО n STEP h < оператор> NEXT x - циклическая конструкция. Операторы цикла организуют повторное выполнение одних и тех же команд несколько раз (при этом повторение происходит не в буквальном смысле, а каждый раз выполнение повторяемого участка программы происходит с использованием новых значений переменных). Автоматическое управление циклом осуществляет переменная, называемая параметром. Параметр цикла - управляющая переменная. Задаются первоначальное значение параметра цикла (например, Х = 1), конечное значение (например, Х =< 100), и увеличение параметра на каждом шаге повторения (например, Х = Х + 1). Любой циклический процесс включает в себя четыре обязательных шага: · подготовку к выполнению циклической части алгоритма; · рабочую часть цикла; · подготовку очередного шага цикла; · проверку окончания цикла. Существует две разновидности операторов цикла: оператор цикла с фиксированным числом повторений (детерминированный цикл) и операторы цикла с переменным числом повторений, зависящим от условий (итерационный цикл). При выполнении первых (с известным числом повторений) задаются: начальное и конечное значения параметров цикла; закономерность изменения параметра цикла на каждом шаге его повторения; необходимое число повторений цикла. При выполнении вторых (когда количество повторений цикла предварительно неизвестно) выход из цикла происходит при достижении заданной точности вычислений (заданной величины) или числа, равного предварительно заданному (этот метод называется методом последовательных приближений). По структуре циклы делятся на простые и сложные. Простые циклы не содержат внутри себя других циклов. Сложные циклы при этом имеют один или несколько внутренних циклов и называются внешними. Циклы, которые включены (входят) во внешние циклы, называются внутренними. Установленные выше свойства алгоритмов следует называть эмпирическими. Они выявлены на основе обобщения свойств алгоритмов различной природы и имеют прикладной характер. Этих свойств достаточно для практического программирования, для создания обширного круга программ для компьютеров, станков с ЧПУ, промышленных роботов и т.д. Однако, как фундаментальное научное понятие алгоритм требует более обстоятельного изучения. Оно невозможно без уточнения понятия «алгоритм», более строгого его описания или, как еще говорят, без егоформализации. Известно несколько подходов к формализации понятия «алгоритм» и один из них - теория конечных и бесконечных автоматов. Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. Рассмотрим формализацию понятия алгоритма в теории автоматов на примере машины Тьюринга. Заметим, что формально определенный любым из известных способов алгоритм не может в практическом программировании заменить то, что мы называли алгоритмами выше. Основная причина состоит в том, что формальное определение резко сужает круг рассматриваемых задач, делая многие практически важные задачи недоступными для рассмотрения. Машина Тьюринга. В 1937-1938 гг. Э.Пост и А.Тьюринг независимо один от другого доказали, что алгоритмические процессы есть процессы, которые может выполнять соответствующим образом построенная «машина» (на этой гипотетической машине оказалось возможным проверить, имитировать все алгоритмические процессы). Абстрактные (существующие лишь в воображении) машины Поста и Тьюринга, предназначены для доказательств различных утверждений о свойствах программ для них. Они представляют собой универсальных исполнителей, являющихся полностью детерминированными, позволяющих «вводить» начальные данные, и после выполнения программ «читать» результат. Машина Поста менее популярна, хотя она значительно проще машины Тьюринга. Абстрактная вычислительная машина Тьюринга (он доказал, что любая задача, которая имеет логическое решение, может быть разбита на ряд простых последовательных операций и эта идея легла в основу разработки компьютеров) - это условная (гипотетическая) машина, которая включает следующие части. 1. Информационную ленту, представляющую собой бесконечную (неограниченную) внешнюю память машины. Это может быть магнитная лента, перфолента. Информационная лента поделена на отдельные ячейки. В одной ячейке может помещаться только один символ, в том числе и ноль. 2. Головку считывания для просмотра содержимого ячеек. Относительно головки считывания информационная лента перемещается в обоих направлениях так, что в каждый момент времени головка находится в одной определенной ячейке ленты. 3. Устройство управления, которое в каждый рассматриваемый момент находится в каком-то «состоянии». В общем устройство управления (предполагаемое) может находиться в каком-то числе «состояний». Схематично машина Тьюринга показывается так:
0 1 2 3 k r – 1 r Лента разделена на клетки или ячейки. В каждой ячейке информационной ленты машины Тьюринга может находиться один из символов, какого-то конечного алфавита, а устройство управления может быть в одном из конечных состояний. Машина может выполнять какое-то конечное число приказов (команд).
|