Основы алгоритмизации и программирования. Основы алгоритмизации и программирования Этапы решения задач на компьютере
 Скачать 92.36 Kb.
|
|
1 2
Основы алгоритмизации и программирования Этапы решения задач на компьютере Компьютер – это универсальное (многофункциональное) программно управляемое устройство для хранения, обработки и передачи информации. Человек использует компьютер для решения самых разнообразных информационных задач: работа с текстами, создание графических изображений, получение справок из базы данных, табличные расчеты, решения математических задач, расчет технических конструкций. Для их решения имеется обширное программное обеспечение (ПО): системное ПО, ядром которого является операционная система; прикладное ПО; и системы программирования (средства для создания программ на языках программирования). Исходя из условия задачи, пользователь решает для себя вопрос о том, каким программным средством он воспользуется. Если в составе доступного прикладного ПО имеется программа, подходящая для решения данной задачи, то пользователь выбирает ее в качестве инструмента (СУБД, табличный процессор, математический пакет). В случае же, если готовым прикладным ПО воспользоваться нельзя, приходится прибегать к программированию на универсальных языках. Работа по решению прикладной задачи на компьютере проходит следующие этапы:
Эту последовательность называют технологической цепочкой решения задачи на ЭВМ. Постановка задачи. На этом этапе должно быть четко определенно, что дано и что требуется найти. Так, если задача конкретная (например, решить уравнение 2х2+3х+5=0, где коэффициенты уравнения – константы), то под постановкой задачи понимает ответ на два вопроса: какие исходные данные известны и что требуется определить. Если задача обобщенная (например, решить квадратное уравнение aх2+bx+c=0), то при постановке задачи понадобится еще ответ на третий вопрос: какие данные допустимы. Математическая формализация. Компьютер решает задачу, выполняя команды заданного алгоритма, выраженные на языке программирования. В памяти компьютера команды имеют вид электрических сигналов, соответствующих двоичному способу кодирования. Поэтому обработка этих сигналов, выполнение требуемых операций происходит в компьютере по законам арифметических действий в двоичной системе счисления и булевой алгебры. Следовательно, выполнение операций будет возможно, если все необходимые для решения задачи действия формализованы, т.е. представлены как математические операции и соотношения между входящими в них переменными. Задача переводится на язык математических формул, управления, отношений. Далеко не всегда эти формулы очевидны. Нередко их приходится выводить самому или отыскивать в специальной литературе. Если решение задачи требует математического описания какого-то реального объекта, явления или процесса, то формализация равносильна получению соответствующей математической модели. В случае большого числа параметров, ограничений, возможных вариантов исходных данных модель явления может иметь очень сложное математическое описание. Поэтому часто построение математической модели требует упрощения требований задачи. Например, для решения квадратного уравнения, когда необходимо получить значения его корней (если они есть), мы можем воспользоваться известными из курса алгебры формулами для x1 и х2. На уроках математики доказывалась правильность метода решения квадратного уравнения путем вычисления по формулам:  .Доказано, что этот метод решения дает искомые значения корней при любых доступных значениях исходных данных – коэффициентов а, b, c. В данном случае алгоритм строится, основываясь на этом методе решения. Построение алгоритма. Разрабатывать алгоритм можно лишь тогда, когда ясно, какой способ, метод решения наиболее адекватно будет соответствовать реальным явлениям и процессам. Алгоритм решения данной задачи кладется в основу программы для компьютера. Алгоритм – это система точных и понятных предписаний (команд) о последовательности действий, позволяющая за конечное число их шагов получить результат. Алгоритм отражает всю логику рассуждений при решении задачи. Он должен обладать свойствами дискретности, понятности, детерминированности, результативности, массовости. Алгоритм составляется в форме, допустимой для конкретного типа алгоритма, чаще всего в графической (блок-схема) ввиду ее наглядности и универсальности применения. Составление программы. Компьютер может многое, однако, это всего лишь автомат, хотя и совершенный. Он решает задачи, быстро и точно выполняя последовательность команд, хранимых в памяти компьютера в виде программы. Современные языки программирования (инструментальные программы) предоставляют возможность писать программы для задач различной сложности. Отладка и тестирование программы. Под отладкой программы понимается процесс испытания работы программы и исправления обнаруженных при этом ошибок. Как правило, инструментальные программы снабжены транслятором, который помогает обнаружить ошибки в программе. Пользователь получает сообщение об ошибке, исправляет ее и снова повторяет испытание программы. Проверка на компьютере правильности алгоритма производится с помощью тестов. Тест – это конкретный вариант значений исходных данных, для которого известен ожидаемый результат. Прохождение теста – необходимое условие правильности программы. На тестах проверяется правильность реализации программой запланированного сценария. Например, если это программа решения квадратного уравнения, то нужно проверить ее работоспособность как для варианта значений коэффициентов а, b, с, при которых получается неотрицательный дискриминант (D2=b2-4ас)?0, так и для варианта значений коэффициентов а, b, с, когда D<0. Что означает проверку возможности работы всех альтернативных ветвей программы:
Анализ результатов. Анализируя получаемые результаты контрольного расчета, в случае их правильности можно сделать вывод о правильности всех предшествующих программированию этапов. Для определения правильности решения задачи в зависимости от ее класса применяют разные подходы:
После проведения тех или иных правомерных сравнений может возникнуть необходимость уточнения метода или модели, составления нового алгоритма и соответствующей ему программы и повторения процедуры компьютерных расчетов, причем до тех пор, пока анализ получаемых результатов не подтвердит их приемлемость. Последний этап – это использование уже разработанной программы для получения искомых результатов. Программы, имеющие большое практическое или научное значение, используется длительное время. Иногда в процессе эксплуатации программы исправляются, дорабатываются. Понятие алгоритма. Исполнители алгоритмов. Свойства алгоритмов Понятие алгоритм так же фундаментально для информатики, как и понятие информации. Само слово «алгоритм» происходит от имени выдающегося математика средневекового Востока Мухаммеда Аль-Хорезми. Им были предложены приемы выполнения арифметических вычислений с многозначными числами. Позже в Европе эти приемы назвали алгоритмами от «algorithmi» – латинского написания имени Аль-Хорезми. В наше время понятие алгоритма понимается шире, не ограничиваясь только арифметическими вычислениями. Термин «алгоритм» стал достаточно распространенным не только в информатике, но и в быту. Под алгоритмомпонимают систему точных и понятных предписаний (команд) о содержании и последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа, определяющих действия исполнителя (субъекта или управляемого объекта). Всякий алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Для того чтобы алгоритм был реализуем, нельзя включать в него команды, которые исполнитель не в состоянии выполнить. У каждого исполнителя имеется свой перечень команд, которые он может исполнить – система команд исполнителя алгоритмов (СКИ). Свойства алгоритмов (требования к алгоритмам): 1 Дискретность. Процесс решения задачи должен быть разбит на последовательность отдельных шагов. Таким образом, формируется упорядоченная совокупность отдельных друг от друга команд (предписаний) Образованная структура алгоритма оказывается прерывной (дискретной): только выполнив одну команду, исполнитель сможет приступить к выполнению следующей 2. Точность (определенность, детерминированность). Каждая команда алгоритма должна определять однозначное действие исполнителя. Недопустимы ситуации, когда после выполнения очередной команды исполнителю не ясно, какую команду выполнять на следующем шаге. Нарушение составителем алгоритма этих требований приводит к тому, что одна и та же команда после выполнения разными исполнителями дает неодинаковый результат. 3. Понятность. Алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в его систему команд, которые исполнитель в состоянии выполнить. Алгоритм не должен быть рассчитан на принятие каких-либо самостоятельных решений исполнителем, не предусмотренных составлением алгоритма. 4. Конечность (результативность). Исполнение алгоритма должно завершиться за конечное число шагов и при этом должен быть получен определенный постановкой задачи ответ. 5. Массовость. Разработка алгоритмов – процесс интересный, творческий, но непростой, требующий многих умственных усилий и затрат времени. Поэтому предпочтительно разрабатывать алгоритмы, обеспечивающие решения всего класса задач данного типа. Алгоритм должен быть вариативен, т.е. обеспечивать возможность решения задачи для любых допустимых исходных значений. Это требование определяет качество алгоритма. Для правильного исполнения алгоритма нужно иметь полный набор данных. Для алгоритма строго не определяется форма его представления. Алгоритм можно изображать графически (блок-схемы), словесно, специальными значками, понятными только автору. Типы алгоритмов и формы их представления Известны три типа алгоритмов: линейный, ветвящийся, циклический. Тип алгоритма определяется характером решаемой в соответствии с его командами задачи. Применяют три формы представления алгоритмов: табличную, словесную, графическую, но не все три формы возможны для любого из алгоритмов. Форма представления алгоритма зависит от его типа. Линейный тип алгоритма. Алгоритм, в котором команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий, является алгоритмом линейного типа. Таким будет, например, алгоритм вычислений по самым простейшим, безальтернативным формулам, не имеющим ограничений на значения входящих в них переменных. Запишем условие одной из задач, решение которой потребует составления алгоритма линейного типа, и сделаем постановку задачи. При постановке задачи необходимо указать переменные, значения которых потребуются в качестве исходных, и переменные, значения которых необходимо найти, а также формализованную связь между ними. Задача: вычислить площадь круга. Дано: R – радиус круга. Требуется: S – площадь круга. Связь: S=3,14*R2. Алгоритм решения такой задачи – по типу линейный допускает любую из трех форм представления. Табличная форма представления алгоритмов применяется только для линейных вычислительных алгоритмов.
Словесная форма представления (для всех типов алгоритмов).
Если использовать команду присвоения, то словесная форма представления этого алгоритма станет более компактной: 
Во всех записях алгоритма можно применять другой порядок действий: вычислять сначала значение R , которое затем умножать на коэффициент – значение числа ?. Графическая форма представления (применима для алгоритмов всех типов) основана на замене (кодировании) типичных алгоритмических команд определенными геометрическими фигурами. Ветвящийся тип алгоритма – условие задачи предусматривает в ходе ее решения возможность выбора в зависимости от выполнения некоторых условий. Он допускает две формы представления: словесную и графическую. Циклический тип алгоритма используется, если требуется многократное повторение одних и тех же действий (циклов). Форма представления может быть выбрана как словесная, так и графическая. На практике чаще всего встречаются алгоритмы смешанного типа, у которых можно выделить участки (блоки), имеющие структуру линейного, ветвящегося или циклического типа. Алгоритм любой степени сложности можно построить с помощью блоков основного базового набора, имеющих линейную, ветвящуюся или циклическую структуру. Каждая из этих структур имеет только один вход и только один выход, что позволяет соединять между собой в процессе разработки алгоритма любое количество элементов базовых структур в любой последовательности. Разработка алгоритмов методом пошаговой детализации. Вспомогательный алгоритм Эффективным методом построения алгоритмов является метод пошаговой детализации (последовательного построения). При этом сложная задача разбивается на ряд более простых. Для каждой подзадачи составляется свой, относительно решения основной задачи, вспомогательный алгоритм. Требования к ним продиктованы необходимостью, как решения подзадач, так и последующей их «стыковки» в основном алгоритме. Эти подзадачи могут, в свою очередь, потребовать разбиения на еще более простые задачи, и т.д. В результате некоторые вспомогательные алгоритмы могут стать основными по отношению к вспомогательным алгоритмам более низкого уровня. Основной алгоритм содержит команды обращения к вспомогательным алгоритмам. Процесс пошаговой детализации заканчивается, когда задачи очередного уровня окажутся совсем простыми. Метод пошаговой детализации универсален. Он применим для решения задач из разных областей жизни. Вспомогательные алгоритмы создаются, когда возникает необходимость разбиения задачина ряд более простых задач или когда есть необходимость многократного использованияодного и того же набора действий в одном или разных алгоритмах, вспомогательные алгоритмы, как уже отмечалось, должны быть состыкованы между собой в процессе «сборки» основного алгоритма. Для этого используют заголовки вспомогательных алгоритмов; с их помощью вызывают этот алгоритм (обращаются к его работе) из других вспомогательных или основного алгоритмов. При составлении и использовании вспомогательных алгоритмов важно знать, что является для них исходными данными (аргументами) и результатами. Иногда команды вызова вспомогательного алгоритма содержат указание на имена тех переменных, которые вносят в него исходные значения, а также переменных, в которые перед выходом из него попадут значения результата для дальнейшего использования вне вспомогательного алгоритма. Иногда результатом работы вспомогательного алгоритма может стать значение некоторой сигнальной переменной («флажка»), сообщающее об истинности какого-то условия или о наличии какого-либо факта. Записывая программу для компьютера на языке программирования, вспомогательные алгоритмы можно организовать, например, как подпрограммы. Правила обращения к ним и возврата из них в основную программу определяются конкретным языком программирования. Подпрограммы общего назначения могут объединяться в библиотеки подпрограмм, а иногда образовывать набор стандартных функций. Метод последовательной детализации путем разбиения задачи на подзадачи лежит в основе технологии структурного программирования и широко применяется при использовании структурных языков программирования, таких, как Паскаль или структурные версии Бейсика. Согласно концепции структурного программирования, вспомогательный алгоритм должен:
Таким образом, при проектировании основного алгоритма нужно сначала определить необходимый набор функций, а затем разработать вспомогательный алгоритмы. Методы последовательной детализации применяется при любом конструировании сложных объектов. Это естественная логическая последовательность мышления постановщика задачи: постепенное углубление в детали. Достаточно сложный алгоритм другим способом практически построить невозможно. Разветвляющиеся алгоритмы. Команда ветвления Существует широкий круг задач, при решении которых необходимо сделать определенный выбор в зависимости от выполнения некоторых условий. Процесс решения таких задач описывается алгоритмом, тип которого определяется как ветвящийся (разветвляющийся). В разветвляющихся алгоритмах принцип линейного автоматического перехода от команды к команде, от действия к действию в порядке естественного следования не является всеобщим, так как иногда возникает необходимость произвольного перехода к предписанию, то есть нарушения линейности переходов. Ветвящиеся алгоритмы допускают два способа представления – графический и словесный. При графическом представлении алгоритма ветвление (развилка, выбор дальнейших действий) организуется с помощью логического элемента (ромб с записанным внутри условием), имеющего один вход и несколько (в простейшем случае – два) выходов. Назначениелогического элемента – проверказаданного условия. В зависимости от выполнения (истинности) или невыполнения (ложности) проверяемого условия возможен выход соответственно на ветвь «Да» или «Нет». Пример: Задача: вычислить у =|х|. Дано: х – значение аргумента. Требуется: у - значение функции. Условие:  Составим алгоритм решения данной задачи в графической форме. На схеме наглядно проявляется важное свойство ветвящихся алгоритмов: их исполнение всегда проходит только по одному из возможных путей, который определяется конкретными текущими условиями, причем в каждом случае от начала алгоритма (входа) до его конца (выхода). Это свойство присуще всякому логически правильно составленному алгоритму и является признаком правильной организации ветвлений.  Циклические алгоритмы. Команда повторения При составлении алгоритмов решения достаточно большого круга задач нередко возникает потребность в неоднократном повторении одних и тех же команд. Алгоритм, составленный с использованием многократных повторений одних и тех же действий (циклов), называется циклическим. Однако «неоднократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма (так называемое «зацикливание»), является нарушением требования его результативности – получения результата за конечное число шагов. Рассмотрим графическое представление циклического блока алгоритма. В него входят в качестве базовых следующие структуры: логический элемент с проверкой условия Р и блок S, называемый телом цикла. Здесь тело цикла S расположено после проверки условия Р (цикл с предусловием), поэтому может случиться, что при определенных условиях блок S не выполнится ни разу. Такой вариант организации цикла, управляемый предусловием, называется цикл-пока. При словесном представлении алгоритма команда, организующая повторение в цикле-пока, имеет вид: Пока Р>0, повторять 8 Конец цикла Таким образом, если Р не выполняется, то предусмотрен выход из цикла на команду записанную после строки «Конец цикла». Здесь условие Р – это условие на продолжение цикла. Возможен другой случай, когда тело цикла S выполняется по крайней мере один раз и будет повторяться до тех пор, пока не выполнится условие Р. Такая организация цикла, когда тело цикла, расположено перед проверкой условия Р, носит название цикла с постусловием или цикла-до. Истинность условия Р в этом случае – причина окончания цикла. Словесная форма команды, организующая цикл-до, приведена ниже: Повторять S пока не Р Конец цикла   Возможна ситуация с постусловием и при организации цикла-пока. Итак, цикл-до завершается, когда условие Р становится истинным, а цикл-пока – когда Р становился ложным, т.е. цикл-до выполнятся «до» истинности условия, а цикл-пока выполняется пока – указанное выражение остается истинным Современные языки программирования имеют достаточный выбор операторов, реализующих как цикл-пока, так и циклы-до. Отметим основное отличительное свойство циклических алгоритмов: количество действий, исполняемых в процессе выполнения алгоритма, может существенно превышать количество команд, из которых организован цикл. Чтобы в этом убедиться, достаточно алгоритм «проиграть», то есть выполнить его шаг за шагом при некоторых наборах допустимых исходных данных. Рассмотрим один из часто встречающихся вариантов цикла – так называемого цикла с параметром. Его характерная особенность – изменение управляющей переменной цикла с заданным шагом Для примера рассмотрим задачу табулирования функции на заданном интервале изменения ее аргумента Задача построить таблицу значений функции y=tgxна отрезке [А,В] с шагом Н. Дано: А – начальное значение аргумента; В – конечное значение аргумента; Н – шаг изменения аргумента. Требуется: у – значения функции. Условие: у = tg х, где х = А, А+Н,…, В. Представим алгоритм решения задачи табулирования функции в графическом виде (цикл с постусловием). Здесь тело цикла состоит из двух команд – вычисление у и печать значения аргумента х и соответствующего ему значения функции у. Команда х:= х+Носуществляет переход к следующему значению аргумента х, являющегося вместе с тем параметром цикла его управляющей переменной. Проверка условия, стоящая после выполнения тела цикла, показывает, что это цикл-до. Следовательно, это проверка на окончание работы цикла при достижении значений х > В.  Примеры создания алгоритмов
1 2
|