Разработка алгоритма решения задачи
Вслед за математической постановкой задачи и выбором метода ее решения требуется дать полное и однозначное описание вычислительного процесса для ЭВМ. Это описание должно содержать необходимые формулы, по которым выполняется расчет, определять последовательность их применения, условия, при которых используется та или иная формула, а также указывать правила перехода от одной части вычислительного процесса к другой. Компьютеру должны быть даны все необходимые инструкции по поводу любых обстоятельств, которые могут возникнуть в ходе вычислительного процесса.
Такое описание задается алгоритмом решения данной задачи. Поиск, разработка и описание алгоритма решения задачи называется алгоритмизацией. Алгоритмизация - это сложный процесс, носящий в значительной степени творческий характер. Сложность и ответственность реализации данного этапа объясняется тем, что для решения одной и той же задачи, как правило, существует множество различных алгоритмов, отличающихся друг от друга уровнем сложности, объемами вычислительных работ, составом необходимой исходной и промежуточной информации и другими факторами, которые оказывают существенное влияние на эффективность вычислительного процесса. Ошибки, допущенные при разработке алгоритма, искажают ход вычислительного процесса и, следовательно, приводят к неверному результату.
71
Понятие алгоритма первоначально возникло в математике в результате поиска общих методов решения однотипных задач. Название "алгоритм" происходит от латинизированного воспроизведения арабского имени узбекского математика Аль - Хорезми, жившего в конце VIII - начале IX вв., который первым сформулировал правила, позволяющие систематически составлять и решать квадратные уравнения.
Развитие ЭВМ сделало понятие алгоритма одним из центральных в прикладной математике, так как возникла необходимость в определении общих способов формирования и единообразного решения различных классов задач управления на основе разработки комплексов универсальных алгоритмов.
Наряду с трактовкой алгоритма в соответствии с принятым стандартом (по ГОСТ 19.004 - 80 "Алгоритм - это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату") термин "алгоритм" может быть представлен более развернутым определением как конечный набор правил, однозначно раскрывающих содержание и последовательность выполнения операций для систематического решения определенного класса задач за конечное число шагов.
Любому алгоритму присущи следующие основные свойства: определенность, массовость, результативность и дискретность.
Свойство определенности характеризует однозначность толкования указаний алгоритма. Алгоритм строго определяет необходимую последовательность выполняемых действий. Благодаря определенности процесс реализации не зависит от конкретного исполнителя и может носить чисто механический характер.
Массовость алгоритма означает применимость данного алгоритма к любым допустимым значениям исходных данных. Иными словами, алгоритм служит для решения любой задачи из некоторого класса аналогичных задач при различных сочетаниях исходных данных.
Свойство результативности алгоритма заключается в возможности получения искомого результата для допустимых значений исходных данных за конечное число достаточно простых итогов.
Дискретность алгоритма означает возможность разбиения определенною алгоритмического процесса на отдельные элементарные действия, возможность реализации которых человеком или ЭВМ не вызывает сомнения.
Существует несколько способов описания алгоритма: словесный, формульно - словесный, графический и др.
Словесный способ описания алгоритма отражает содержание выполняемых действий средствами естественного языка К достоинствам этого способа следует отнести его общедоступность, а также возможность описывать алгоритм с любой степенью детализации. Недостатками способа можно назвать достаточно громоздкое описание (и. как следствие, относительно низкая наглядность) и отсутствие строгой формализации в силу неоднозначности
72
восприятия естественного языка, вытекающего из свойств синонимии, омонимии, полисемии.
Формульно - словесный способ описания алгоритма основан на записи содержания выполняемых действий с использованием изобразительных возможностей языка математики, дополненного необходимыми пояснениями средствами естественного языка. Данный способ, обладая всеми достоинствами словесного способа, более лаконичен, а значит, и более нагляден, имеет большую формализацию, хотя и не является строго формальным.
Графический способ описания алгоритмов основан на использовании языка структурных схем. Структурная схема алгоритма представляет собой графическое изображение последовательности действий при реализации данного алгоритма. Этапы решения задачи представляются в структурной схеме отдельными блоками, которые изображаются соответствующими символами: прямоугольниками, ромбами, овалами и т.д. ГОСТ 19.003 - 80 устанавливает перечень символов, применяемых в структурных схемах алгоритмов, форму и размеры этих символов, а также отображаемые ими функции (действия). Основные символы структурных схем алгоритмов и отображаемые ими функции приведены на рис. 4.2.
Рис. 4.2. Обозначения символов структурных схем алгоритмови отображаемые ими функции
73
Внутри символов структурной схемы указывается содержание соответствующих этапов вычислений. Символы структурной схемы соединяются стрелками, показывающими направления развития вычислительного процесса. Иногда около стрелок делаются надписи, указывающие на то, при каких условиях происходит выбор данного направления.
Для сложных задач рекомендуется сначала разрабатывать укрупненную структурную схему алгоритма, а затем детализировать более подробно ее отдельные блоки. Практически любой сложный алгоритм обычно строится из комбинации трех базовых структур: линейной, разветвляющейся и циклической.
Линейным называется такой алгоритмический процесс, при котором все этапы решения задачи выполняются в естественном порядке следования записи этих этапов.Для линейной структуры характерно, что порядок выполнения этапов не зависит ни от исходных данных, ни от результатов выполнения предыдущих этапов.
Разветвляющаяся структура обычно содержит блок проверки некоторого логического условия, например, а ? 0; а < в, а ? в и т.п. В зависимости от результата проверки выполняется та или иная последовательность действий, называемая ветвью.
В циклической структуре реализуются многократно повторяющиеся этапы обработки данных. Такая структура обычно содержит несколько типовых блоков. Основной блок, называемый телом цикла, производит требуемые линейные, разветвляющиеся или другие циклические структуры, а также сочетания этих структур. Кроме тела цикла, в циклической структуре используются также вспомогательные блоки, в которых устанавливаются начальные и новые значения данных, проверяются условия окончания цикличности процесса и т.д.
74
71 :: 72 :: 73 :: 74 :: Содержание
