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

Самая существенная разница между видами циклов заключается в том факте, что тело цикла с послеусловием обязательно выполняется один раз – до самой первой проверки условия, цикл с предусловием может даже не выполнятся вообще, если при первой проверке условия получим результат «нет». [13]

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

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

3.Практическая реализация базовых структур алгоритмов

3.1.Операторы языка С++ для реализации базовых структур алгоритмов

Для выполнения линейных алгоритмов на языке С++ используется операция присваивания.[13]

Общий вид оператора присваивания следующий:[14]

имя_переменной = выражение;

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

Для реализации разветвляющих алгоритмов используются два оператора: логический оператор if и оператор выбора case.

Стандартная форма оператора if следующая:

if (выражение) оператор;

else оператор;

где оператор может быть или простым, или составным. [2]

Оператор else не обязателен. Стандартная форма оператора if с составными операторами следующая:

if (выражение) {

последовательность операторов

}

else {

последовательность операторов

}

Если выражение истинно (любое значение, кроме 0), выполняется блок операторов, следующий за if; иначе выполняется блок операторов, следующих за else. Всегда выполняется код ассоциированный или с if или с else, но никогда не выполняются оба кода одновременно.

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

switch (выражение) {

case константа1:

последовательность операторов

break;

case константа2:

последовательность операторов

break;

case константа3:

последовательность операторов break;

...

default:

последовательность операторов

}

Оператор default выполняется, если не найдено соответствий, default необязателен и, если его нет, то в случае отсутствия совпадений ничего не происходит. Когда обнаруживается совпадение, операторы, ассоциированные с соответствующим case, выполняются до тех пор, пока не встретится оператор break. В случае default (или последнего case, если отсутствует default), оператор switch заканчивает работу при обнаружении конца.[5]

Следует знать о трех важных моментах оператора switch:[11]

1.switch отличается от if тем, что он может выполнять только операции проверки строгого равенства, в то время как if может вычислять логические выражения и отношения.

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

3. если в операторе switch используются символьные константы, они автоматически преобразуются к целочисленным значениям.

Рассмотрим реализацию алгоритмов цикла на языке С++, где существуют три разновидности цикла:[19]

– цикл for;

– оператор цикла while;

– оператор цикла do ... while.

Все эти операторы цикла содержат непременно следующие составные части:

– условие продолжения цикла;

– присваивания исходных значений;

– тело цикла;

– изменение счетчика цикла.

Оператор for используется, когда есть известное заранее количество повторений.

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

Синтаксис оператора:

for (инициализация счетчика; условие выполнения; модификация)

{

тело цикла;

}

Простой пример вычисления суммы иллюстрирует использования данного оператора for:[5]

int summa = 0;

for (i = 1; i <= 15; i ++)

s = s + i;

Операторы с предусловием и постусловием используются для организации циклов и являются альтернативными к оператору for. Обычно цикл с предусловием используется, если количество повторений заранее неизвестно, а для многократного повторения тела цикла известно условие, при истинности которого цикл продолжает выполнение. Это условие следует проверять каждый раз перед очередной итерацией. Например, при считывании данных из файла условием цикла является наличие данных непосредственно в файле, то есть повторять чтение данных следует до тех пор, пока указатель не будет указывать на конец файла.[15]

Синтаксис цикла с предусловием:

while (условие выполнения)

{

тело цикла

};

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

Цикл с постусловием выполняется, если есть надобность проверять истинность условий каждый раз после итерации. Как отмечали выше, отличие циклов с предусловием и с постусловием заключается в самой первой итерации.[6]

Синтаксис цикла do … while:

{

тело цикла

}

while (условие выполнения);

Последовательность операторов (тело цикла) выполняется один или несколько раз, пока условие станет ложным. Оператор цикла do ... while используется в тех случаях, когда есть необходимость выполнить тело цикла хотя бы один раз, поскольку проверка условия осуществляется после выполнения операторов.[7]

Если тело цикла состоит из одного оператора, то операторные скобки {} не является обязательны.[4]

Операторы цикла while и do ... while преждевременного могут завершиться при выполнении операторов break или же return внутри тела циклов.

3.2.Примеры использования основных структур алгоритмов на языке программирования С++

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

Для демонстрации линейного алгоритма рассмотрим следующий пример.[7]

С начала сутки прошло n секунд. Определите сколько часов, минут и секунд прошло с начала сутки.

Код программы на языке С++ следующий:

//подключаем заголовочные файлы

#include <iostream>

#include <conio.h>

#include <clocale>

#include <math.h>

using namespace std; // объявляем пространство имен

int main()

{

float n,h,m,s; // объявляем переменные

setlocale (LC_CTYPE,"rus"); //подключаем кириллицу

cout << "Введите количество секунд n: ";

cin >> n;

//находим целые значения часов, минут, секунд

h=floor(n/3600);

m=floor((n-h*3600)/60);

s=n-h*3600-m*60;

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

cout <<"С начала сутки прошло "<<h<<" часов "<<m<<" минут "<<s<< " секунд";

getch();

return 0;

}

В результате получим:[1]

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

Для рассмотрения разветвляющего алгоритма решим следующее задание.[8]

Ввести з клавиатуры 3 целые числа и проверить создают ли они убывающую последовательность. Если да – то вывести числа, обратного знака к исходным, в противоположном случае вывести сумму квадратов чисел.[11]

#include <iostream>

#include <conio.h>

#include <clocale>

#include <math.h>

using namespace std;

int main()

{

float d1,d2,d3; // объявление переменных

setlocale (LC_CTYPE,"rus");

cout << "введите числа: ";

cin >> d1>>d2>>d3; //инициализация переменных d1, d2, d3

if ((d1>d2)&&(d2>d3)) //проверка условия убывающей последовательности[11]

{ //переопределение переменных

d1=(-1)*d1;

d2=(-1)*d2;

d3=(-1)*d3;

cout<<"Последовательность убывающая! "<<endl;

}

else

{ // переопределение переменных

d1=pow(d1,2);

d2=pow(d2,2);

d3=pow(d3,2);

cout<<"Последовательность не убывающаяя! "<<endl;

}

cout<<d1<<" , "<<d2<<" , "<<d3;

getch();

return 0;

}

В результате получим:[4]

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

Для рассмотрения циклического алгоритма напишем программу для сортировки элементов массива с помощью метода пузырька.[1]

#include <iostream>

#include <conio.h>

#include <clocale>

#include <math.h>

using namespace std;

int main()

{

//подключение кириллицы

setlocale( LC_ALL,1201 );

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

int r, m, q;

//объявление массива

int М[40];

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

cout<<»Введите размерность массива:»;

//считывание размерности вектора

cin>>m;

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

cout<<"Введите элементы массива: ";

//считывание элементов

for (r=0;r<m;r++)

cin>>M[r];

//алгоритм сортировки пузырьком

for( r=0;r < m; r++)

for( q=r+1; q < m; q++)

//проверка условия для сортировки

if (M[r] > M[q])

//переназначение элементов

swap(M[r],M[q]);

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

cout<<"Вывод элементов массива: ";

for (r=0;r<m;r++)

//вывод элемента

cout<<М[r]<<" ";

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

getch();

//возврат 0

return 0;

}

В результате получим:[17]

Рис.21. Результат сортировки

ЗАКЛЮЧЕНИЕ

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

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

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

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

Язык программирования служит двум связанным между собой целям: он дает программисту аппарат для задания действий, которые должны быть выполнены, и формирует концепции, которыми пользуется программист, размышляя о том, что делать. Первой цели идеально отвечает язык, который настолько "близок к машине", что всеми основными машинными аспектами можно легко и просто оперировать достаточно очевидным для программиста образом. Второй цели идеально отвечает язык, который настолько «близок к решаемой задаче», чтобы концепции ее решения можно было выражать прямо и коротко.

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

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

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

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

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