Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Основные понятия теории алгоритмов).pdf

Стоит отметить, что на ЯП С++ используются 2 основные оператора, которые поддерживают реализацию разветвленных алгоритмов:[3]

– оператор if;

– оператор switch.

Рассмотрим синтаксис оператора if (рисунок 9):

Рис.9. Синтаксис оператора if

Оператор switch использует аналогичную структуру:

switch(x)

case 1: инструкции1;

case 2: инструкции2;

…

case n: инструкцииn;

default: инструкции.

Рассмотрим пример использования логического оператора для реализации разветвленного алгоритма.[16]

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

Опишем блок-схему алгоритма (рисунок 10):

Рис.10. Блок-схема разветвленного алгоритма

Код программы имеет вид:

int main()

{

// объявление переменных которые отвечают сторонам треугольника[12]

float a,b,c;

//объявление переменных для вычисления площади, полупериметра

float ar, p;

//ввод стороны а

cout<<"a = ";

cin>>a;

//ввод стороны b

cout<<"b = ";

cin>>b;

//ввод стороны c

cout<<"c = ";

cin>>c;

//проверка возможности построения треугольника

if ((a+b>c)||(a+c>b)||(b+c>a))

//вычисление площади

{

//вычисление полупериметра

p=(a+b+c)/2;

//вычисление площади

ar=sqrt(p*(p-a)*(p-b)*(p-c));

cout<<"Area: "<<ar;

}

else

//в противоположном случае

cout<<"It is impossible to build a triangle";

getch();

return 0;

Результат выполнения программы показан на рисунке 11:

Рис.11. Результат выполнения программы

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

Одним из самых основных методов для проверки корректности алгоритма считается его трассировка.

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

Стоит отметить, что в ходе выполнения этой проверки должны присутствовать 2 факта:

– при выборе исходных тестирующих данных с одной и той же самой области реализации ход алгоритма будет аналогичным;

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

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

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

Циклическим называется такой программный алгоритм, который имеет свой участок кода, выполняющийся многократно, а при этом его изменяются параметры и вместе с другими значениями переменных.[4]

По способу организации рассматриваемые алгоритмы делятся на такие 2 вида:

– классические циклы;

– традиционные циклы.

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

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

Для этого должны являться известными:

• начальное значение аргумента t_нач;
• конечное значение аргумента t_кон;
• шаг параметра Δt.

Стоит отметить, что зная эти величины, легко вычисляется количество повторений циклов (формула (1)):

(1)

В этой формуле квадратные скобки будут значить, что после деления указанного числа будет браться только его целая часть (дробная – отбрасывается), поскольку численность повторений цикла – это целая величина.[20]

Отметим, что цикл использует такие 4 части:

– подготовка цикла – определенному параметру цикла будет присвоено исходное значение;

– тело цикла – главные действия, что реализуются каждый раз при выполнении витка цикла;

– изменение параметров циклов на шаг;

– условие для выхода с цикла.

Рассмотрим пример для реализации циклического алгоритма.

Необходимо для целочисленного массива найти сумму максимального и минимального значения.[15]

Рассмотрим пример блок-схемы алгоритма (рисунок 12):

Рис.12. Блок-схема циклического алгоритма

Код программы имеет следующий вид:

int main()

{

//объявление переменных

int ar[10],p,min,max,x;

//ввод размерности массива ar

cout<<"Input dimention of array:";

cin>>x;

//ввод массива ar

cout<<"Input the elements of array: ";

for (p=0;p<x;p++)

cin>>ar[p];

//присваиваем начальные значения для переменных

min=ar[0];

max=ar[0];

//нахождение минимума и максимума

for(p=0;p < x; p++)

{

if(min>ar[p])

min=ar[p];

if(max<ar[p])

max=ar[p];

}

//вывод данных

cout<<"Max + min = "<<max + min;

//задержка экрана

getch();

//возврат 0

return 0;

На рисунке 13 показана результат выполнения программы:[10]

Рис.13. Результат выполнения программы

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

ЗАКЛЮЧЕНИЕ

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

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

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

Одной с самых кардинальных проблем является проблематика взаимодействия общества и информатики.

Именно информатика поставила задачу создания технологии искусственного интеллекта.

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

В работе были выполнены следующие задачи:

– рассмотрены основные понятия об алгоритмах, их свойства;

– описаны методы подачи алгоритмов;

– охарактеризованы базовые структуры алгоритмов и провести их сравнительный анализ;

– проведено рассмотрение операторов для реализации основных структур алгоритмов на языке С++;

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ