Основные структуры алгоритмов: сравнительный анализ и примеры их использования (СПОСОБЫ ОПИСАНИЕ АЛГОРИТМОВ)

Содержание:

ВВЕДЕНИЕ

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

Известно, что математическая теория алгоритмов сложилась вовсе не в связи с бурным развитием информатики и вычислительной техники, а возникла в недрах математической логики для решения её собственных проблем. Она, прежде всего, оказала большое влияние на мировоззрение математиков и на их науку.

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

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

ПОНЯТИЕ АЛГОРИТМА И ЕГО СВОЙСТВА

Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий.

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

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

Основными свойствами алгоритма являются:

Детерминированность (определенность).

Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;

Результативность

Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;

Массовость

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

Дискретность

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

Понятность

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

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

Алгоритм может быть записан различными способами: на естественном языке в виде описания; в виде графических блок-схем; на специальном алгоритмическом языке. В школе на уроках информатики для записи алгоритмов используется, так называемый, "школьный алгоритмический язык". Этот язык по существу является “мёртвым" языком” так как на нём не работают компьютеры, и мы не будем им пользоваться. Запись алгоритмов на родном языке доступна и удобна. Примеров таких записей множество, хотя бы книга кулинарных рецептов есть не что иное, как сборник алгоритмов, написанных на родном языке. Существенным недостатком такой записи является недостаточная наглядность, что особенно сказывается, когда алгоритм имеет много ветвлений. Поэтому, мы будем записывать наши алгоритмы в виде блок-схемы.

СПОСОБЫ ОПИСАНИЕ АЛГОРИТМОВ

Существуют различные способы описания алгоритмов. Приведем основные из них: словесный (пошаговое описание); табличный и в виде формул; графический (в виде схем); с использованием псевдокода (алгоритмического языка).

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

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

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

ЭЛЕМЕНТЫ БЛОК-СХЕМ АЛГОРИТМОВ

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

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

Таблица 1 – Основные обозначения для блок-схемы

Терминатор начала и конца работы функции	Терминатором начинается и заканчивается любая функция. Тип возвращаемого значения и аргументов функции обычно указывается в комментариях к блоку терминатора.
Операции ввода и вывода данных	Определено множество символов ввода/вывода, например вывод на магнитные ленты, дисплеи и т.п. Если источник данных не принципиален, обычно используется символ параллелограмма. Подробности ввода/вывода могут быть указаны в комментариях.
Выполнение операций над данными	В блоке операций обычно размещают одно или несколько (ГОСТ не запрещает) операций присваивания, не требующих вызова внешних функций.
Блок, иллюстрирующий ветвление алгоритма	Блок в виде ромба имеет один вход и несколько подписанных выходов. В случае, если блок имеет 2 выхода (соответствует оператору ветвления), на них подписывается результат сравнения — «да/нет». Если из блока выходит большее число линий (оператор выбора), внутри него записывается имя переменной, а на выходящих дугах — значения этой переменной.
Вызов внешней процедуры	Вызов внешних процедур и функций помещается в прямоугольник с дополнительными вертикальными линиями.
Начало и конец цикла	Символы начала и конца цикла содержат имя и условие. Условие может отсутствовать в одном из символов пары. Расположение условия, определяет тип оператора, соответствующего символам на языке высокого уровня — оператор с предусловием (while) или постусловием (do … while).
Подготовка данных	Символ «подготовка данных» в произвольной форме, задает входные значения. Используется обычно для задания циклов со счетчиком.
Соединитель	В случае, если блок-схема не умещается на лист, используется символ соединителя, отражающий переход потока управления между листами. Символ может использоваться и на одном листе, если по каким-либо причинам тянуть линию не удобно.
Комментарий	Комментарий может быть соединен как с одним блоком, так и группой. Группа блоков выделяется на схеме пунктирной линией.

ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

ЛИНЕЙНАЯ АЛГОРИТМИЧЕСКАЯ СТРУКТУРА

Линейные алгоритмы предполагают последовательное выполнение действий в порядке, заданном схемой, без их повторения или пропуска некоторых действий. Алгоритм линейной структуры изображается линейной последовательностью связанных друг с другом блоков (рис.2.1). Такой порядок выполнения действий называется естественным. Поэтому в схемах алгоритмов линейной структуры нет блока «Решение».

Рисунок 2.1 – Алгоритм линейной структуры

РАЗВЕТВЛЯЮЩАЯСЯ АЛГОРЕТМИЧЕСКАЯ СТРУКТУРА

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

Таким образом, алгоритм ветвящейся структуры содержит только структуры «Следование» и «Ветвление».

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

Для реализации процесса выбора одного из двух вариантов решения используется логический блок (блок проверки условия), приведенный на рисунке 3.1. При входе в этот блок выполняется проверка логического условия (обычно математического неравенства). Если результат проверки условия «Истина», т.е. условие выполняется, то происходит переход к выполнению блоков, стоящих по ветви «+». В противном случае, т.е. когда проверяемое условие не выполняется, происходит переход к выполнению блоков, стоящих по ветви «–».

Рисунок 3.1 – Логический блок

Визуальное представление алгоритма в виде блок-схемы представлено на рисунке 2.2.

Рисунок 2.2 – Алгоритм разветвляющейся структуры

АЛГОРЕТМИЧЕСКАЯ СТРУКТУРА «ЦИКЛ»

В алгоритмах циклической структуры выполнение одних и тех же действий может повторяться несколько раз. Организация циклического вычислительного процесса выполняется в несколько этапов:

1-й этап – подготовка к выполнению цикла. На этом этапе задаются начальные значения для параметра цикла и переменных, использующихся для хранения накапливающихся величин (сумма, количество или произведение вычисляемых величин). Параметр цикла – это переменная, на основе которой строится цикл. Она должна удовлетворять трем условиям: являться исходной величиной для выполнения вычислений; изменяться по определенному закону (чаще всего это закон арифметической прогрессии); оказывать влияние на условие завершения повторяющихся вычислений.

2-й этап – тело цикла. Оно содержит арифметические и логические действия, которые могут повторяться определенное количество раз. В конце тела цикла обязательно должен быть блок, в котором изменяется значение параметра цикла.

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

Пример.

Вычислить значение функции y(x) = x²+ 1,5 при изменении аргумента x в диапазоне x_n ≤ x ≤ x_k с шагом Dx. Вывести таблицу значений x и y.

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

Рисунок 4.1 – Алгоритм цикла с постусловием

Представим данную схему циклического алгоритма с помощью цикла типа «ДЛЯ», или цикла с параметром, который является модификацией цикла «ПОКА» для ситуации, когда заранее известно количество повторений некоторых действий. В этом случае все три необходимых блока – блок 4, блок 5 и блок 8 – собираются в один блок – блок 4, в котором указываются начальное и конечное значения параметра и шаг изменения.

Рисунок 4.2 – Алгоритм для цикла с параметром

На рисунке ниже представлена блок-схема цикла с предусловием. Другие названия цикла: цикл-пока, цикл с заданным условием продолжения работы.

Особенность данного вида цикла: операторы цикла будут повторяться до тех пор, пока условие истинно. Его проверка делается каждый раз перед выполнением операторов цикла. Цикл может ни разу не выполниться, если его условие ложно.

Рисунок 4.3 – Алгоритм цикла с предусловием

ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ АЛГОРИТМОВ НА ЯЗЫКЕ C И JAVA

Чтобы составить программу линейной структуры требуется:

1. Определить, что является исходными данными, какие будут у них типы.
2. Выбрать имена переменных.
3. Определить, что является искомыми результатами, какие будут у них типы. Выбрать имена переменных.
4. Определить, какие формулы связывают исходные данные с результатами.
5. Если нужны промежуточные данные, определить их типы и выбрать имена вспомогательных переменных.
6. Описать все используемые переменные.
7. Ввод всех исходных данных.
8. Вычисления.
9. Вывод результатов.
10. Будьте внимательны: вспомогательная переменная должна получить значение до того, как она будет использована в вычислениях.
11. Подобрать данные для тестирования программы (проверки правильности ее работы).

Задача:

Напишите программу, решающую следующее выражение:

Используйте аргументы командной строки для инициализации значений a b.

Код программы на языке C:

#include <stdio.h>

#include <stdlib.h>

int main(int ac, char **av)

{

int a = atoi(av[1]);

int b = atoi(av[2]);

int result;

result = (a + b*b)/(1-a);

printf("%d", result);

return 0;

}

Код программы на языке JAVA

import java.lang.Math.*;
import java.io.*;

public class Quiz {
public static void main(String[] args) {
int a = Integer.parseInt(args[0]);
int b = Integer.parseInt(args[1]);

int res = (int)(a + Math.pow(b , 2))/(1 - a);

System.out.println(res);
}
}

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

Задача:

Найти наибольшее из трех чисел a, b, c. Входные аргументы брать из командной строки.

Код программы на С

#include <stdio.h>

#include <stdlib.h>

int main(int ac, char **av)

{

int a = atoi(av[1]);

int b = atoi(av[2]);

int c = atoi(av[3])

if (a > b && a > c)

printf("%d", a);

else if (b > a && b > c)

printf("%d", b);

else if (c > a && c > b)

printf("%d", c);

return 0;

}

Код программы на JAVA

import java.lang.Math.*;
import java.io.*;

public class Quiz {
public static void main(String[] args) {
int a = Integer.parseInt(args[0]);
int b = Integer.parseInt(args[1]);
int c = Integer.parseInt(args[2]);

if (a > b && a > c)
System.out.println(a);
else if (b > a && b > c)
System.out.println(b);
else if (c > a && c > b)
System.out.println(c);
}
}

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

Задача:

Вывести на экран таблицу ASCII.

ASCII – код для обмена информацией. В настоящее время чаще используется 8-битный вариант (под каждый символ выделяется 1 байт памяти). Проще говоря, получается таблица из 256 символов, соответствующих числам от 0 до 255.

Код на языке С

int main()

{

char c = 0;

while (c <= 255)

{

printf("%c", c);

c++;

}

return 0;

}

Код на языке Java

import java.io.*;

public class Quiz {
public static void main(String[] args) {
char c = 0;
while (c < 256)
{
System.out.print(c++);
}
}
}

Эта же задача, но решенная с помощью цикла с постусловием:

Код на языке С:

int main()

{

char c = 0;

do

{

printf("%c", c);

}

while (c++ < 256);

}

Код на языке JAVA

import java.io.*;

public class Quiz {
public static void main(String[] args) {
char c = 0;
do {
System.out.print(c);
}
while (c++ < 256);
}
}

Эта же задача, но решенная с помощью цикла с параметром:

Код на языке С:

#include <stdio.h>

int main()

{

char c = -1;

for(;c < 256; c++)

{

printf("%c", c);

}

}

Код на языке JAVA

import java.io.*;

public class Quiz {
public static void main(String[] args) {
char c = 0;
for(; c < 256; c++)
{
System.out.print(c);
}
}
}

СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ

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

Линейной называют алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i-го действия (шага) выполняется (i+1)-е действие (шаг), если i-е действие — не конец алгоритма.

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

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

ЗАКЛЮЧЕНИЕ

Создание алгоритма для решения задач какого-либо типа, его представление исполнителю в удобной для него форме – это творческий акт. Алгоритм может быть представлен различными способами: на разговорном естественном язык; на языке блок-схем; на языке программирования. Выбор и разработка алгоритма и численного метода решения задачи имеют важнейшее значение для успешной работы над программой. Тщательно проработанный алгоритм решения задачи – необходимое условие эффективной работы по составлению алгоритму.

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

БИБЛИОГРАФИЯ

1. Б.В. Соболь [и др.] «Информатика и программирование»– Ростов н/Д: Феникс, 2006 – 354 с.

2. Информатика. Базовый курс./С.В. Симонович и др. - СПб.: Питер, 2001

3. Информатика: базовый курс: учебник для студентов вузов, бакалавров, магистров, обучающихся по направлению «Информатика»/О.А. Акулов, Н.В. Медведев. 6-е изд., испр. и доп.-М.: Издательство «Омега-Л», 2009.-574 с. – (Высшее техническое образование).

4. Каймин В.А. Информатика: Учебник для вузов. - М.: Высшее образование, 1998.

5. Каймин В.А., Касаев Б.С. Информатика.: Практикум на ЭВМ. Учебное пособие.

6. Культин Н.Б. Программирование в TurboPascal 7.0 и Delphi.- 2-е издание, перераб. и доп.- Спб.: БХВ-Петербург,2002.-416 с.;ил.

7. Турбо Паскаль 7.0. Самоучитель. – СПб.: Питер; К.: Издательская группа BHV, 2002.-576 с.