Алгоритмы
Исключительно важно использовать язык блок-схем при разработке алгоритма решения задачи. Решение одной и той же задачи может быть реализовано с помощью различных алгоритмов, отличающихся друг от друга как по времени счета и объему вычислений, так и по своей сложности. Запись этих алгоритмов с помощью блок-схем позволяет сравнивать их, выбирать наилучший алгоритм, упрощать, находить и устранять ошибки.
Отказ от языка блок-схем при разработке алгоритма и разработка алгоритма сразу на языке программирования приводит к значительным потерям времени, к выбору неоптимального алгоритма. Поэтому необходимо изначально разработать алгоритм решения задачи на языке блок-схем, после чего алгоритм перевести на язык программирования.
При разработке алгоритма сложной задачи используется метод пошаговой детализации. На первом шаге продумывается общая структура алгоритма без детальной проработки отдельных его частей. Блоки, требующие детализации, обводятся пунктирной линией и на последующих шагах разработки алгоритма продумываются и детализируются.
В процессе разработки алгоритма решения задачи можно выделить следующие этапы:
- Этап 1 . Математическое описание решения задачи.
- Этап 2 . Определение входных и выходных данных.
- Этап 3 . Разработка алгоритма решения задачи.
Базовые алгоритмические конструкции
В теории программирования доказано, что для записи любого, сколь угодно сложного алгоритма достаточно трех базовых структур:
- следование (линейный алгоритм);
- ветвление (разветвляющийся алгоритм);
- цикл-пока (циклический алгоритм).
Линейные алгоритмы
Линейный алгоритм образуется из последовательности действий, следующих одно за другим. Например, для определения площади прямоугольника необходимо сначала задать длину первой стороны, затем задать длину второй стороны, а уже затем по формуле вычислить его площадь.
Пример
ЗАДАЧА. Разработать алгоритм вычисления гипотенузы прямоугольного треугольника по известным значениям длин его катетов a и b.
На примере данной задачи рассмотрим все три этапа разработки алгоритма решения задачи:
Этап 1. Математическое описание решения задачи.
Математическим решением задачи является известная формула:
,
где с-длина гипотенузы, a, b – длины катетов.
Этап 2. Определение входных и выходных данных.
Входными данными являются значения катетов a и b. Выходными данными является длина гипотенузы – c.
Этап 3. Разработка алгоритма решения задачи.
На данной схеме цифрами указаны номера элементов алгоритма, которые соответствуют номерам пунктов словесного описания алгоритма.
Разветвляющиеся алгоритмы
Алгоритм ветвления содержит условие, в зависимости от которого выполняется та или иная последовательность действий.
Пример
ЗАДАЧА. Разработать алгоритм вычисления наибольшего числа из двух чисел x и y.
Этап 1. Математическое описание решения задачи.
Из курса математики известно, если x > y, то наибольшее число x, если x < y, то наибольшее число y, если x = y, то число x равно числу y.
Этап 2. Определение входных и выходных данных.
Входными данными являются значения чисел x и y. Выходным данными являются:
Для решения задачи нам необходимо знать значения x и y.
Этап 3. Разработка алгоритма решения задачи.
- Начало алгоритма.
- Ввод значений x и y.
- Сравниваем x и y. Если x = y, то переход к шагу 4, иначе к шагу 5.
- Вывод информации: числа x и y равны. Переход к шагу 8.
- Сравниваем x и y. Если x > y, то переход к шагу 6, иначе к шагу 7.
- Вывод информации: число x больше y. Переход к шагу 8.
- Вывод информации: число y больше x. Переход к шагу 8.
- Конец алгоритма.
В схеме алгоритма решения задачи цифрами указаны номера элементов алгоритма, которые соответствуют номерам шагов словесного описания алгоритма
В рассматриваемом алгоритме (рис.3) имеются три ветви решения задачи:
- первая: это элементы 1, 2, 3, 4, 8.
- вторая: это элементы 1, 2, 3, 5, 6, 8
- третья: это элементы 1, 2, 3, 5, 7, 8.
Выбор ветви определяется значениями x и y в элементах 3 и 5, которые являются условиями, определяющими порядок выполнения элементов алгоритма. Если условие (равенство), записанное внутри символа «решение», выполняется при введенных значениях x и y, то следующими выполняется элементы 4 и 8. Это следует из того, что они соединены линией с надписью «да» и направление (последовательность) вычислений обозначена стрелочкой.
Если условие в элементе 3 не выполняется, то следующим выполняется элемент 5. Он соединен с элементом 3 линией с надписью «нет». Если условие, записанное в элементе 5, выполняется, то выполняется элементы 6 и 8, в противном случае выполняются элементы 7 и 8.
Циклические алгоритмы
Циклический алгоритм – определяет повторение некоторой части действий (операций), пока не будет нарушено условие, выполнение которого проверяется в начале цикла. Совокупность операций, выполняемых многократно, называется телом цикла.
Алгоритмы, отдельные действия в которых многократно повторяются, называются циклическими алгоритмами, Совокупность действий, связанную с повторениями, называют циклом.
При разработке алгоритма циклической структуры выделяют следующие понятия:
- параметр цикла – величина, с изменением значения которой связано многократное выполнение цикла;
- начальное и конечное значения параметров цикла;
- шаг цикла – значение, на которое изменяется параметр цикла при каждом повторении.
Цикл организован по определенным правилам. Циклический алгоритм состоит из подготовки цикла, тела цикла и условия продолжения цикла.
В подготовку цикла входят действия, связанные с заданием исходных значений для параметров цикла:
- многократно повторяющиеся действия для вычисления искомых величин;
- подготовка следующего значения параметра цикла;
- подготовка других значений, необходимых для повторного выполнения действий в теле цикла.
В условии продолжения цикла определяется допустимость выполнения повторяющихся действий. Если параметр цикла равен или превысил конечное значение цикла, то выполнение цикла должно быть прекращено.
Пример
ЗАДАЧА. Разработать алгоритм вычисления суммы натуральных чисел от 1 до 100.
Этап 1. Математическое описание решения задачи.
Обозначим сумму натуральных чисел через S. Тогда формула вычисления суммы натуральных чисел от 1 до 100 может быть записана так:
где Xi – натуральное число X c номером i, который изменяется от 1 до n, n=100 – количество натуральных чисел.
Этап 2. Определение входных и выходных данных.
Входными данными являются натуральные числа: 1, 2, 3, 4, 5, …, 98, 99, 100.
Выходные данные – значение суммы членов последовательности натуральных чисел.
Параметр цикла – величина, определяющая количество повторений цикла. В нашем случае i – номер натурального числа.
Подготовка цикла заключается в задании начального и конечного значений параметра цикла.
- начальное значение параметра цикла равно 1,
- конечное значение параметра цикла равно n,
- шаг цикла равен 1.
Для корректного суммирования необходимо предварительно задать начальное значение суммы, равное 0.
Тело цикла. В теле цикла будет выполняться накопление значения суммы чисел, а также вычисляться следующее значение параметра цикла по формулам:
Условие продолжения цикла: цикл должен повторяться до тех пор, пока не будет добавлен последний член последовательности натуральных чисел, т.е. пока параметр цикла будет меньше или равен конечному значению параметра цикла.
Этап 3. Разработка алгоритма решения задачи.
Введем обозначения: S – сумма последовательности, i – значение натурального числа.
Начальное значение цикла i=1, конечное значение цикла i =100, шаг цикла 1.
В схеме алгоритма решения задачи цифрами указаны номера элементов алгоритма. Номера элементов соответствуют номерам шагов словесного описания алгоритма.
1.1.4 Разработка алгоритма
Этот этап заключается в разложении вычислительного процесса на возможные составные части, установлении порядка их следования, описании содержания каждой такой части в той или иной форме. Далее осуществляется проверка, которая показывает, обеспечивается ли реализация данного метода.
В большинстве случаев не удается сразу получить нужный результат, поэтому составляющие части алгоритма анализируются на предмет того, как они (каждая в отдельности и все вместе) выполняют возложенную на них роль. Как правило, в процессе разработки алгоритм проходит несколько этапов детализации.
Наиболее правильное решение – метод «сверху вниз», когда за основу берется вся задача, разбиваемая на подзадачи более низкого уровня. На этой стадии получается более уточненный алгоритм. Процесс детализации можно продолжать далее. На каждой стадии детализации происходит многократная проверка алгоритма и исправление его.
Опираясь на крупноблочную структуру алгоритма, можно быстрее и проще разработать программы, произвести их анализ, оценку и выбрать наилучший вариант. Эффект поэтапной детализации зависит от того, как осуществляется его структуризация, т.е. расчленение на составные части. Она должна осуществляться не по произволу программиста, а должна определяться логикой рассматриваемой задачи. Каждый элемент такой схемы должен быть максимально самостоятельным и логически завершенным, чтобы дальнейшую его детализацию можно было выполнять отдельно от детализации остальных элементов.
Существуют различные способы описания алгоритма. Эти способы отличаются друг от друга компактностью записи, степенью формализации, на какого исполнителя они рассчитаны, каким образом они высвечивают логику алгоритма.
Прежде всего, известен словесный способ описания алгоритма, который мы можем встретить в любой предметной области. Можно записывать алгоритм в виде схем. Существуют и формальные алгоритмические языки для записи алгоритмов псевдокоды и так называемые структурограммы (диаграммы Насси-Шнайдермана).
1.1.5 Программирование
На этом этапе алгоритм представляется в форме, понятной ЭВМ, и работа программиста определяется тем, что ему доступно на данной ЭВМ. Выбирается подходящая система программирования, и алгоритм преобразовывается в программу на соответствующем алгоритмическом языке. Данное учебное пособие ориентировано на систему Visual Studio 2010.
1.1.6 Отладка
При выполнении программы могут быть следующие исходы: либо программа выдает неверные результаты, либо выдаются не все результаты, предусмотренные к выдаче; программа повторяет одну и ту же последовательность операторов (зацикливание программы); выполнение программы прекращается из-за аварийного останова (переполнение разрядной сетки, деление на ноль); программа не выдает результатов.
При указанных исходах необходима отладка программы. Это наиболее трудоемкая часть всего процесса программирования, где выявляются все ошибки, допущенные на более ранних этапах. Выполняя ее, необходимо тщательно проверить, протестировать каждый участок программы. Процесс отладки состоит в многократной последовательности действий пользователя, включающей в себя обнаружение, локализацию и исправление ошибок.
Ошибки, которые могут быть допущены в программе, можно подразделить на два вида:
- синтаксические, появление которых связано с нарушением правил записи языковых конструкций;
- семантические (смысловые), вызывающие ошибки при выполнении.