ПРОГРАММИРОВАНИЕ. КОНТРОЛЬ И ОТЛАДКА ПРОГРАММЫ. РЕШЕНИЕ ЗАДАЧИ И АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ
Тема 14. ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ
1. Этапы решения задачи на ЭВМ
2. Основные свойства и способы представления алгоритма.
3. Базовые структуры программирования
1. При решении той или иной задачи на ЭВМ соответствующая информация подвергается необходимой арифметической и логической обработке. Однако непосредственному решению задачи на ЭВМ обычно предшествует значительная по трудоемкости подготовительная работа. При этом обычно выделяют следующие основные этапы:
1) постановка задачи;
2) анализ задачи и моделирование;
3) разработка алгоритма решения задачи;
4) программирование;
5) тестирование и отладка программы;
6) непосредственное решение задачи на ЭВМ и анализ полученных результатов
7) сопровождение программы.
Постановка задачи. Математическое описание и выбор метода решения
Вначале осуществляется постановка задачи, подлежащей решению на ЭВМ. На этой стадии определяются состав и характер исходных данных, устанавливаются требуемая форма исходных результатов и условия, которым они должны удовлетворять, выбирается общий подход к решению, осуществляется разбиение задачи на подзадачи, определяется последовательность их решения и т. д. Постановка задачи обычно завершается словесным описанием основных характеристик и особенностей решаемой задачи.
2. Затем необходимо дать математическое описание задачи, в результате чего постановка задачи становится формализованной, приобретает четкость и однозначное толкование.
|
|
|
Чтобы это осуществить, необходима математическая теория, которая описывает закономерности исследуемого явления с помощью математических формул. Такой набор формул называют математической моделью данного явления.
Математический аппарат, применяемый для описания задач, зависит от того, к какому классу принадлежат эти задачи. При этом могут быть использованы, например, обыкновенные дифференциальные уравнения или системы таких уравнений, дифференциальные уравнения в частных производных, системы линейных алгебраических уравнений и т. п.
Следует также иметь в виду, что математическая модель лишь в очень простых случаях позволяет по имеющимся исходным данным получить требуемые результаты. Другими словами, математическая модель далеко не всегда указывает однозначную последовательность расчета. Обычно она определяет искомые величины неявно, в виде системы математических зависимостей, которым должны удовлетворять эти величины. Такая система зависимостей в большинстве случаев неполна, она оставляет исследователю некоторую свободу выбора тех или иных путей достижения поставленной цели. Этот выбор необходимо проводить так, чтобы получить оптимальное значение определенного критерия. Указание такого критерия также входит в математическую модель. Когда критерий назначен и составлена полная система уравнений, описывающих исследуемое явление, задача становится математически сформулированной.
|
|
|
Вслед за математической постановкой задачи должен быть выбран метод ее решения. Этот метод устанавливает зависимость искомых результатов от исходных данных и реализуется путем разбиения вычислительного процесса на последовательность элементарных арифметических и логических операций, выполняемых в ЭВМ. Современная вычислительная математика располагает большим количеством численных методов для решения различных задач науки и техники. Если же для решения данной конкретной задачи отсутствуют такие методы, то их либо заново разрабатывают, либо несколько упрощают постановку задачи с тем, чтобы можно было воспользоваться известными математическими методами.
РАЗРАБОТКА АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ. ТИПЫ АЛГОРИТМОВ И СПОСОБЫ ИХ ОПИСАНИЯ
За математической постановкой задачи и выбором метода ее решения следует реализация выбранного метода на ЭВМ. На этой стадии возникает необходимость в достаточно полном, ясном и однозначном описании требуемого вычислительного процесса. Это описание должно содержать необходимые формулы, по которым выполняется расчет, определять последовательность их применения, условия, при которых используется та или иная формула, а также указывать правила перехода от одной части вычислительного процесса к другой части. Машине должны быть также даны необходимые инструкции по поводу любых обстоятельств, которые могут возникнуть в ходе вычислительного процесса.
|
|
|
Таким образом, при оформлении задания ЭВМ возникает необходимость в точном и полном описании вычислительного процесса или любой иной последовательности действий, выполняемых ЭВМ. Такое описание задается алгоритмом решения данной задачи. Поиск, разработка и описание алгоритма решения задачи называется алгоритмизацией.
ПРОГРАММИРОВАНИЕ. КОНТРОЛЬ И ОТЛАДКА ПРОГРАММЫ. РЕШЕНИЕ ЗАДАЧИ И АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ
Следующим этапом подготовки задач к решению на ЭВМ является программирование. На этом этапе составляется и вводится в память ЭВМ программа, состоящая из отдельных команд и определяющая последовательность выполняемых операций.
|
|
|
Программирование завершает формализованное описание выбранного метода и разработанного для него алгоритма решения задачи. Такое описание выполняется на некотором языке программирования. Наиболее полно учитывает особенности ЭВМ ее машинный язык, операторы которого состоят из машинных команд. Этот язык может быть непосредственно и однозначно воспринят ЭВМ в виде последовательности выполняемых операций.
Разнообразие существующих ЭВМ обусловило появление множества их машинных языков, специфичных для каждого типа машины. Это затрудняет работу программистов, пользующихся разными ЭВМ, осложняет создание типовых программ, которые можно использовать для большинства ЭВМ. Кроме того, программы, составленные на машинном языке, не наглядны, требуют большой и утомительной работы для их создания, затрудняют обнаружение и устранение неизбежных ошибок, допущенных в процессе написания программ. Поэтому в настоящее время машинные языки практически не применяются при программировании задач, за ними сохраняются лишь функции внутреннего языка ЭВМ. Для целей программирования стали в основном применять различные формальные языки, не зависящие от конкретной ЭВМ, а целиком ориентированные на особенности решаемых задач. Такие языки отражают в большей степени алгоритм решения задачи, поэтому их принято называть алгоритмическими языками.
Современный алгоритмический язык существенно отличается от внутреннего машинного языка конкретной ЭВМ, поэтому программа, составленная на алгоритмическом языке, не может быть непосредственно воспринята ЭВМ. Для этого необходимо перевести программу с алгоритмического языка на машинный язык данной ЭВМ. Такой перевод осуществляется самой машиной с помощью специальной программы, называемой программой-транслятором. Существуют три вида трансляторов: интерпретаторы, компиляторы и ассемблеры.
Обычно процессы трансляции и исполнения программы разделены во времени. Сначала вся программа транслируется, а затем исполняется. Трансляторы, работающие в таком режиме, называются компиляторами. То есть, компилятор преобразует (транслирует) всю программу в модуль на машинном языке, после этого программа записывается в память компьютера и лишь потом исполняется.
Благодаря трансляции получается более быстрая по времени работы программа, но выполняемый файл имеет большой объем. Кроме того, выполняемый файл запускается только на компьютере того типа, где программа была транслирована.
Трансляторы, в которых преобразование и выполнение каждого оператора исходного языка осуществляется последовательно, называют интерпретаторами. В таких трансляторах отдельные участки исходной программы выполняются сразу после трансляции, после чего та же процедура совершается для других участков программы и т. д.
Недостаток интерпретаторов заключается в неэффективном использовании машинного времени. При повторном выполнении программы или при многократном выполнении ее отдельных участков интерпретацию приходится каждый раз выполнять заново, в то время как компилятор позволяет выполнить трансляцию только один раз, а затем хранить программу в машинных кодах. По этой причине интерпретаторы применяются относительно редко.
Ассемблеры переводят программу записанную на языке ассемблера (автокода), в программу на машинном языке.
Любой транслятор решает следующие основные задачи:
- анализирует транслируемую программу, в частности определяет, содержит ли она синтаксические ошибки;
- генерирует выходную программу (ее часто называют объектной или рабочей) на языке команд ЭВМ (в некоторых случаях транслятор генерирует выходную программу на промежуточном языке, например, на языке ассемблера);
- распределяет память для выходной программы (в простейшем случае это заключается в назначении каждому фрагменту программы, переменным, константам, массивам и другим объектам своих адресов участков памяти).
Важным этапом в процессе подготовки и решения задачи на ЭВМ является отладка программы, в ходе которой обнаруживаются и устраняются ошибки, допущенные в процессе программирования. Ошибки в программах бывают двух видов.
1. Синтаксические ошибки — несоответствие формальным требованиям языка программирования. На них указывает транслятор при трансляции и линковщик при сборке программы.
2. Семантические ошибки — смысловые ошибки; при них программа «работает», но работает неправильно. Поиск этих ошибок происходит с помощью логического анализа работы программы и ее тестирования.
Одним из наиболее простых способов отладки является печать промежуточных результатов, по которым можно судить о правильности работы программы на данном этапе вычислений. При этом можно включить в программу дополнительные проверки, результат которых заранее известен. Если этот результат не совпадает с фактически полученным, то предусматривается так называемый контрольный останов с печатью необходимых данных.
Для целей отладки существуют также специальные отладочные программы, которые дают программисту детальную информацию о работе отлаживаемой программы, вплоть до печати данных о каждой выполненной команде. Работа с отладочной программой намного облегчает труд программиста.
После устранения ошибок, обнаруженных при автономной отладке, проводят комплексную отладку всей программы. То есть проводят тестирование — проверку правильности работы программы на заранее подготовленных тестах, для которых известен точный результат.
На завершающем этапе производится непосредственно решение задачи на ЭВМ с анализом полученных результатов.
2. Основные свойства и способы представления алгоритма
Алгоритм — точное описание способа решения задачи, устанавливающее состав операций и последовательность их выполнения.
Любой алгоритм должен обладать следующими основными свойствами:
—понятность для исполнителя — т.е. исполнитель алгоритма должен знать, как его выполнять.
—определенность — т.е. каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче;
—повторяемостью получаемого результата при многократных расчетах с одними и теми же исходными данными;
—результативностью — обязательным получением некоторого результата (числа, таблицы, текста, звука, изображения и т.д.) или сигнала о том, что данный алгоритм неприменим для решения поставленной задачи;
—массовостью — возможностью получения результата при различных исходных данных для некоторого класса сходных задач;
—дискретностью — возможностью разбиения алгоритма на отдельные элементарные действия.
Существуют следующие формы представления алгоритма:
• словесная (текстуальная);
• графическая;
• на языках программирования
• псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
Словесная форма записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Словесная форма представления алгоритма имеет ряд недостатков. Для достаточно сложных алгоритмов описание становится слишком громоздким и ненаглядным. Эта форма представления обычно используется лишь на начальных стадиях разработки алгоритма.
Приведем пример словесной формы описания алгоритма.
Чтобы перейти улицу, нужно посмотреть налево, убедиться в отсутствии приближающегося транспорта, дойти до середины улицы, посмотреть направо, убедиться в отсутствии близко идущего транспорта, продолжить движение через улицу. При наличии движущихся транспортных средств нужно ждать, когда транспорт проедет.
Графическая форма представления алгоритмов является более компактной и наглядной. При графическом представлении алгоритм изображается в виде последовательности связанных между собой блоков, каждый из которых соответствует выполнению одного или нескольких операторов. Такое графическое представление называется блок-схемой алгоритма.
Условные графические обозначения символов, используемых для составления блок-схемы алгоритма, стандартизированы. Некоторые, часто используемые обозначения, приведены в таблице 1. 
Отдельные блоки алгоритмов соединяются между собой линиями потоков информации, которые проводятся параллельно внешней рамке чертежа. Направления линий потока сверху-вниз и слева-направо принимаются за основные и, если линии потоков не имеют изломов, стрелками не обозначаются.
Этап вычисления изображается прямоугольником, внутри которого записывается содержание этого этапа. Проверка условия изображается ромбом. Ввод исходных данных и вывод результатов изображается параллелограммами, внутри которых пишутся слова «ввод» или «вывод» и перечисляются переменные, подлежащие вводу или выводу.
Представление алгоритма в виде блок-схемы является промежуточным, так как алгоритм в таком виде не может быть непосредственно выполнен ЭВМ. Составление блок-схемы алгоритма является важным и в большинстве случаев необходимым этапом решения задачи на ЭВМ, значительно облегчающим процесс составления программ. Алгоритм, записанный на языке программирования, называется программой.
Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.
Он занимает промежуточное место между естественным и формальным языками.
С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
Основные служебные слова
| алг (алгоритм) | сим (символьный) | дано | для | да |
| арг (аргумент) | лит (литерный) | надо | от | нет |
| рез (результат) | лог (логический) | если | до | при |
| нач (начало) | таб (таблица) | то | знач | выбор |
| кон (конец) | нц (начало цикла) | иначе | и | ввод |
| цел (целый) | кц (конец цикла) | все | или | вывод |
| вещ (вещественный) | длин (длина) | пока | не | утв |
3. Базовые структуры программирования
Алгоритм любой сложности может быть представлен комбинацией трех базовых структур:
• следование (линейный);
• разветвление (альтернатива, если-то-иначе);
• цикл (повторение).
Характерной особенностью этих структур является наличие у них одного входа и одного выхода.
Базовая структура «следование» означает, что несколько операторов должны быть выполнены последовательно друг за другом и только один раз за время выполнения данной программы. Совокупность связанных базовых структур «следование» называется линейным вычислительным алгоритмом.
Под оператором понимается формальная запись предписания для выполнения некоторой последовательности действий.
Второй базовой структурой является «разветвление». Эта структура обеспечивает, в зависимости от результата проверки условия (истина или ложь), выбор одного из альтернативных путей работы алгоритма, причем каждый из путей ведет к общему выходу.
Возможные пути выполнения алгоритма помечают соответствующими метками: истина/ложь, да/нет, 1/0 и т.д.
В частном случае может оказаться, что для одного из выбранных путей действий предпринимать не нужно. Такая структура получила название "обход" или структура «если-то». Алгоритм, в состав которого входит базовая структура «разветвление», называется разветвляющимся.
Если в алгоритме имеется три и более направления ветвления, то его можно представить в виде совокупности нескольких базовых структур «если- то-иначе». Такую разновидность структуры «разветвление» часто называют «множественный выбор». Третья базовая структура «цикл» обеспечивает повторное выполнение или, другими словами, циклическую работу операторов.
Различают две разновидности этой структуры: «цикл — пока» и «цикл- до»
Группа операторов, повторяющаяся в цикле, называется телом цикла. Основное отличие структуры «цикл-пока» от структуры «цикл-до» заключается в том, что в первой структуре операторы тела цикла в зависимости от условия могут не выполняться совсем, тогда как в структуре «цикл-до» тело цикла будет выполняться хотя бы один раз. Легко заметить, что в структуре «цикл — пока» проверка выполнения условия осуществляется перед выполнением операторов тела цикла, а в структуре «цикл-до» — после прохождения тела цикла.
Циклы могут содержать внутри себя другие циклы. Такие структуры называются вложенными циклами.
Алгоритмы, имеющие в своем составе базовую структуру «цикл», называются циклическими.
Рассмотренные выше базовые структуры рекомендуется применять для соблюдения структурного подхода к разработке алгоритмов.
Реальные алгоритмы представляют собой совокупность всех рассмотренных базовых структур.
Дата добавления: 2021-12-10; просмотров: 33; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!