2. Технология подготовки и решения задач с использованием компьютера

Сегодня огромное количество задач решается с использованием компьютерной техники. Прежде, чем приступить к решению вычислительной задачи с помощью компьютера, надо представлять себе, в какой последовательности и как более целесообразно подготовить задачу к решению. Подготовку можно разбить на ряд последовательных этапов:

Постановка задачи. Задача должна быть сформулирована в четкой и доступной форме: исходные данные (понятия) и конечные цели задачи.

Математическое описание. Для того, чтобы решить поставленную задачу, должны быть определена методика ее решения, то есть совокупность математических операций или уравнений (математический аппарат), определяющих решение задачи на компьютере. Другими словами, на данном этапе выбираются математические методы решения задачи.

Разработка алгоритма. Данный этап требует разложения решения задачи на отдельные этапы; установления порядка их выполнения; описания содержания каждого этапа решения. То есть – это этап детализации задачи.

Разработка программы. Для того, чтобы задача могла быть решена с помощью ЭВМ, алгоритм ее решения должен быть представлен в форме, доступной для понимания машиной. Алгоритм описывается на специальном языке (языке программирования) и заносится в память ЭВМ.

Отладка программы – поиск возможных ошибок. Составленная программа в редких случаях начинает правильно работать с первого раза, и, как правило, требуется кропотливая работа по поиску возможных ошибок. Ошибки могут возникать как синтаксические (связанные с точностью описания команд языка программирования), так и смысловые (уводящие в сторону от конечного результата или приводящие к неправильному решению задачи), которые могут быть связаны с неточностью описания методики решения задачи.

Решение задачи. После отладки программы, когда появится уверенность, что она обеспечит получение правильных результатов, можно непосредственно приступать к решению задачи на ЭВМ. В этом случае применять программу уже сможет любой пользователь ЭВМ, не имеющий навыков программирования.

3. Понятие алгоритма.

Алгоритмом называется четкое описание последовательности действий, которые необходимо выполнить для решения задачи. Решение практически любой задачи требует получение результата по заданным исходным данным. То есть алгоритм описывает последовательный процесс преобразования исходных данных в результат.

Свойства алгоритма

Для того, чтобы составленный алгоритм обладал достаточной эффективностью при решении задач он должен обладать рядом свойств:

Дискретность. Каждый этап алгоритма должен представлять собой законченное действие. Это свойство состоит в том, что алгоритм должен представлять процесс решения задачи, как последовательное выполнение конечного числа простых шагов (этапов), каждый из которых начинается только после завершения предыдущего.

Определенность. Это свойство состоит в том, что каждое правило (действие) алгоритма должно быть четким, однозначным и не оставлять места для иного толкования. Нарушение этого принципа приводит к ошибке типа "не понимаю", или "не могу выполнить".

Результативность (конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.

Массовость. Это свойство состоит в том, что алгоритм решения задачи разрабатывается в общем виде, то есть он должен быть применим для некоторого класса задач, различающихся лишь исходными данными.

Формы записи алгоритма

Разработанный алгоритм можно записать несколькими способами:

• на естественном языке (вербально), когда алгоритм решения задачи описывается в виде обыкновенного текста, в котором формулируется содержание и последовательность выполнения каждого этапа решения;

• на специальном языке для записи алгоритмов (алгоритмическом языке). Результатом такого описания алгоритма является программа, составленная на любом языке программирования. Подобная запись алгоритма является, пожалуй, наиболее неудобной для его понимания.

• в виде схемы. Схемой называется наглядное графическое изображение алгоритма, когда отдельные действия (этапы) алгоритма записываются при помощи различных геометрических фигур (блоков), а связи между этапами (последовательность выполнения этапов) указываются при помощи стрелок, соединяющих эти фигуры. Изображение алгоритма в виде схемы является доступной к пониманию и наиболее наглядной. Такое графическое представление называется схемой алгоритма или блок-схемой.

Типовые блоки схем алгоритмов

Правила выполнения схем алгоритмов определены Государственным стандартом (ГОСТом). Этих правил необходимо придерживаться при оформлении программной документации. Полный перечень установленных правил и условных обозначений можно найти в ГОСТ 19.002-80 и ГОСТ 19.003-80.

Рассмотрим блоки, наиболее часто используемые в схемах и отображающие различные действия алгоритмов.

Начало/Конец (пуск-останов)

Блоком изображается начало или конец любого вычислительного процесса, вход в подпрограмму или выход из нее. Внутри блока в соответствии с назначением записывается слово "начало" или "конец" .

Блоком "начало" всегда начинается описание схемы любого составляемого алгоритма. Блок всегда имеет только одну выходящую линию. Входящие линии отсутствуют.

Для блока "конец" количество входящих линий не ограничено. Выходящие линии отсутствуют. Этим блоком заканчивается описание каждой блок-схемы алгоритма.

Ввод/Вывод

Ввод исходных данных и вывод результатов изображается параллелограммом. Внутри блока записывается слово "Ввод" или "Вывод" и перечисляются переменные, подлежащие вводу (задаваемые) или выводу (результаты). Для вывода может использоваться и текстовая информация.

Количество входящих линий для блока не ограничено. Выходящая линия может быть только одна.

Вычисление (Процесс)

Блок включает одно или несколько вычислительных действий, в том числе и присвоение. С помощью этого блока записывается любая математическая операция (в том числе и операция присвоения, например x=2.3) или группа операций. Внутри блока записывается содержание текущего этапа (вычислительного действия).

Количество входящих линий для блока принципиально не ограничено. Выходящая линия может быть только одна .

вычисление присвоение

В примере с квадратным уравнением подобный блок может быть использован для описания вычисления дискриминанта или корней уравнения.

Проверка условия (логический блок, решение)

Блок проверки логического условия. Используется в тех случаях, когда при описании алгоритма требуется проверка какого-то логического условия. Изображается блок ромбом. Внутри ромба записывается проверяемое условие.

Количество входящих линий для блока не ограничено. Выходящих линий всегда две, каждая из которых соответствует одному из возможных вариантов проверки логического условия. Таким образом, блок позволяет выполнять в схеме разветвление.

В результате проверки условия осуществляется выбор одного из двух возможных путей вычислительного процесса. Выбор направления выполнения алгоритма или программы зависит от условия. Если условие, записанное внутри блока, выполняется (истинно), то переход к следующему этапу алгоритма осуществляется по стрелке, обозначаемой словом "да" (или "+"). Переход к этапу, не отвечающему условию, сформулированному внутри логического блока (условие логически ложно) осуществляется по стрелке "нет" (или "").

Модификация (счетчик)

Блок управляет процессом при изменении управляющей переменной. Блок используется при организации циклов, для которых известны начальное и конечное (пороговые) значения переменной, а также шаг ее изменения, то есть при выполнении расчетов или других действий, повторяющихся определенное количество раз.

Например: вычислить функцию y=f(x) при изменении переменной x от x_нач до x_кон c шагом x (x_нач  х  x_кон). Здесь x_нач и x_кон – пороговые значения изменяемой переменной.

Управление циклом осуществляется на основании сравнения текущего значения переменной с заданным порогом. Переменную называют параметром цикла, а сам цикл - циклом с параметром. Переменная цикла (изменяемая) записывается внутри блока с указанием через запятую ее пороговых значений и шага изменения, например x=х_нач, х_кон,х.

Количество входящих линий для блока не ограничено. Выходящих линий всегда две: линия перехода к этапам (телу) цикла и линия выхода из цикла (после его завершения).

Особенностью применения данного блока в схемах алгоритмов заключается в том, что изменяемой переменной цикла обязательно присваиваются ее пороговые значения в начале и в конце цикла (x=х_нач и x=х_кон). Поэтому использовать блок в задачах с условиями, содержащими строгое неравенство (например: x_нач < х x_кон или x_нач  х < x_кон или x_нач < х < x_кон), нельзя!

Соединитель

Блок применяется в местах разрыва схемы. В случае большого количества пересекающихся линий блок-схемы, большой их длины и многократных направлениях, когда схема становится мало наглядной или в тех случаях, когда размеры схемы не позволяют изобразить ее на одном листе, допускается разрывать линии потока информации (соединительные линии), размещая на обоих концах разрыва специальный символ "соединитель".

Таким образом, блок всегда используется только парой – в месте разрыва линии и в месте ее продолжения. Изображается блок в виде окружности. Внутри каждого блока одной пары, фиксирующих разрыв одной и той же линии, ставится одинаковая маркировка в виде буквенной или буквенно-цифровой координаты.

Подпрограмма (предопределенный процесс)

Данный блок позволяет использовать в схеме ранее созданные и описанные схемы алгоритмов (подпрограммы).

При разработке алгоритмов или написании программ часто приходится выполнять одну и ту же последовательность действий (группу блоков) в разных местах схемы. Чтобы избавиться от необходимости повторного написания одних и тех же блоков, была предложена концепция подпрограмм.

Подпрограмма – это поименованная законченная группа блоков, которую можно вызвать для выполнения по имени любое количество раз из различных мест схемы.

Таким образом, подпрограмма представляет собой участок повторяющихся блоков, описанных в каком-либо месте (вне схемы алгоритма) и получивших свое имя. Блок "подпрограмма" предназначен для обращения к этому участку блоков из основной схемы алгоритма.

В нутри блока записывается имя подпрограммы (т.е. группы блоков, которые будут выполняться в данном месте схемы) и, при необходимости, параметры, при которых подпрограмма должна быть выполнена.

Типовые структуры алгоритмов

В настоящее время существует технология разработки программ без использования схем. Однако независимо от этого на начальном этапе изучения программирования использование схем при разработке алгоритма целесообразно. Конечно же опытные программисты пишут программы без использования схем алгоритмов. Однако на начальном этапе изучения основ программирования схемы принесут определенную пользу, облегчая процесс написания программы.

Типовые структуры алгоритмов - это ограниченный набор блоков и стандартных способов их соединения для выполнения типовых последовательностей действий.

Приводимые ниже структуры рекомендуются при разработке алгоритмов и программ. Структурный подход предполагает использование только нескольких основных структур, комбинация которых дает все многообразие алгоритмов и программ.

Линейная структура

Линейная (арифметическая) структура - последовательное размещение блоков и групп блоков, выполняемых друг за другом. Каждый этап вычислений сводится к реализации арифметических операций, которые в процессе вычислений выполняются однократно. Традиционный набор элементов линейной структуры включает: начало алгоритма, ввод исходных данных, вычисление, вывод результатов, конец алгоритма.

П ример 1: Вычислить общее сопротивление электрической цепи

Решение:

Л юбая блок-схема начинается с блока "начало" (1).

Для вычисления общего сопротивления необходимо задать исходные данные – значения R₁ , R₂ , R₃ (если в условии не даны их численные значения). Для этого в схеме используется блок ввода (2).

Суммарное сопротивление участка цепи с параллельно включенными сопротивлениями R₁ и R₂ рассчитывается, исходя из следующей формулы:

Общее сопротивление цепи .

Все эти вычисления можно выполнить в одном блоке "вычисление" (3).

Блок "вывод" (4) используется для вывода результатов (в нашей задаче – это общее сопротивление электрической цепи R) на экран монитора, принтер или другие устройства.

Заканчивается любая блок-схема обязательным блоком "конец" (5).

Ветвящаяся структура

Применяется, когда в зависимости от условия нужно выполнить либо одно, либо другое действие.

Указанная структура имеет следующий смысл (рис.а): “Если Условие выполняется, то выполнить Действие1, иначе выполнить Действие2". Действие1 или Действие2 могут в свою очередь содержать несколько блоков.

Частным случаем разветвления является обход, когда одна ветвь не содержит никаких действий (рис.б.): “Если Условие выполняется, то выполнить Действие1, иначе ничего не выполнять".

И, наконец, еще одним вариантом ветвящейся структуры является схема выбора (рис.в), когда различные действия выполняются в зависимости от наступления одного из условий: “ Действие1 выполняется только при выполнении Условия1, Действие2 выполняется только при выполнении Условия2 и т.д.". Количество условий в схеме не ограничено.

Таким образом, вычислительный процесс называется разветвляющимся, если в нем происходит выбор одного из нескольких возможных путей вычислений.

П ример 2: найти действительные корни квадратного уравнения Ax²+Bx+C=0; коэффициенты A,B,C задать с клавиатуры. При отрицательном дискриминанте вывести сообщение “Решения нет”.

Решение.

Дискриминант:

Корни уравнения: ,

Циклическая структура

Очень часто при разработке программ необходимо, чтобы один или группа операторов выполнялись два или более раз. Такие алгоритмы называют циклическими. Большинство программ, составляемых для вычислительной техники, являются именно такими.

Циклическая структура обеспечивает многократное выполнение некоторой совокупности действий (группы блоков), которая называется телом цикла. Для всех циклических структур характерно изменение параметра (управляющей переменной) цикла. Управляющая переменная – переменная, изменяемая в цикле.

Рассмотрим основные циклические структуры. Для циклических структур свойственна одна из трех базовых блок-схем.

Цикл с постусловием (цикл типа "ДО")

Структура применяется при необходимости выполнить какие-либо действия несколько раз ДО наступления некоторого условия. Особенность цикла в том, что он всегда выполняется хотя бы один раз, т.к. первая проверка условия происходит после выполнения тела цикла. Это наиболее распространенная структура в циклических алгоритмах.

Основными составляющими цикла являются :

Подготовка цикла (начальные присвоения, блок начальных параметров). На этом этапе цикла происходит присвоение изменяющейся переменной цикла ее начального значения x= x_нач (выполняется до входа в цикл).

Тело цикла - та последовательность действий (блоков), которая выполняется многократно (в цикле) для различных значений переменной цикла. Часто в циклических задачах тело цикла включает вычисление искомой функции для текущего значения изменяемой переменной y=F(x).

Модификация (изменение) переменной цикла на величину приращения x = x  х (выполняется внутри цикла);

Проверка условия продолжения или окончания цикла. Условие выхода из цикла проверяется сравнением текущего значения изменяемой переменной х с ее конечным значением x  x_кон (,=,<,>) на выходе из цикла. Если выполняется условие продолжения цикла, идет обратный переход к телу цикла.

Пример 3: Вычислить функцию при изменении переменной x в пределах с шагом .

Цикл с предусловием (цикл типа "ПОКА")

Циклическая структура алгоритма с предусловием отличается от цикла "ДО" тем, что проверка условия проводится до выполнения тела цикла (условие предшествует циклу). Все действия в цикле выполняются до тех пор, ПОКА не наступит условие выхода из цикла. Если условие выхода из цикла выполняется при первой же проверке, то тело цикла не будет пройдено ни разу.

Составляющие цикла такие же, как и для цикла "ДО", но в другой последовательности.

П ример 4: Для заданных значений коэффициентов A, B, C вычислить функцию , где .

Цикл с параметром

Цикл с параметром (цикл со счетчиком) - это цикл с заданным числом повторений. Число повторений тела цикла подсчитывается с помощью специальной переменной (счетчика), для которой известны начальное и конечное (пороговые) значения, а также шаг ее изменения. Параметры цикла указываются в блоке модификации в виде: x_нач, x_кон, х (рис.13).

Управление циклом осуществляется на основании сравнения текущего значения счетчика x с заданным порогом x_кон: "Если переменная-счетчик не превышает пороговое (конечное) значение, то выполнять действие 1, иначе переходить к действию 2".