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

Содержание:

ВВЕДЕНИЕ

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

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

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

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

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

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

Предмет исследования – структуры алгоритмов.

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

Задачами данного исследования являются:

-изучить понятия об алгоритмах, их свойства и классификацию;

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

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

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

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

Проблему использования базовых структур алгоритмов изучали разные ученые: Б. Страуструп, Дж.Прата, Г Шилдт. Как результат исследования ими были выпущены учебники по изучению языка программирования С++.

Глава 1. ОСНОВНЫЕ ПОНЯТИЯ ОБ АЛГОРИТМАХ

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

В жизнедеятельности постоянно нужно сталкиваться с различными правилами, что описывают последовательности действий с целью достичь какого-то определенного результата. Такие правила являются многочисленными. К примеру, мы придерживаемся каких-то правил, чтобы приготовить лекарство, позвонить, сварить суп или же решить какое-то математическое уравнение. Рассмотренные примеры можно объединять под понятием «алгоритм». [^[1]]

Понятие алгоритма – это фундаментальная концепция информатики и математики. Оно возникло задолго до создания персональных компьютеров и на данный момент стало главным понятием. [^[2]]

. Термин «алгоритм» происходит от фамилии индийского математика Мугаммада аль-Хорезми (рис.1.1). [^[3]]

Это – один из крупнейших ученых Средневековья. Его родина – Хорезм. Свои знания аль-Хорезми совершенствовал в «Доме мудрости» в Багдаде. Это учреждение было своего рода Академией наук, в которой работали многие ученые арабского Востока. «Дом мудрости» славился своей богатой библио­текой старинных рукописей и астрономической обсерваторией. [3]

Исследователи установили, что аль-Хорезми был автором 9 сочинений:

1. Книга об индийской арифметике;
2. Краткая книга об исчислении алгебры и алмукабалы;
3. Астрономические таблицы;
4. Книга картины Земли;
5. Книга о построении астролябии;
6. Книга о действиях с помощью астролябии;

Algorithmi – латинское транскрипция его фамилии, это слово применялось для обозначения правил по таким арифметическим действиям:

– сложение;

– вычитание;

– умножение;

– деление. [^[4]]

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

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

Алгоритм – точное правило, которое определяет процесс преобразования начальных данных для получения результатных при решении определенного вида задач. [^[5]]

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

Алгоритм – фундаментальное понятие программирования. Ученые выделяют 3 основных класса алгоритмов:

– информационные;

– вычислительные;

– управляющие [^[6]].

Вычислительные алгоритмы – алгоритмы, что работают со сравнительно простыми форматами данных.

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

Эффективность работы таких алгоритмов прямо зависит от организации информации в программе.

Управляющие алгоритмы характеризуются тем, что информация для них поступает от внешних источников, которыми они и управляют. Результатами выполнения этих алгоритмов является создание своевременной управляющей реакции на изменение начальных данных. [^[7]]

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

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

Любые алгоритмы обладают такими свойствами: [^[8]]

1. Массовость – возможность применить алгоритм к любым задачам четко определенного класса.

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

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

2. Детерминированность или определенность – набор указаний должен не зависеть от исполнителя алгоритма и быть точен. Такая характеристика обеспечивает однозначность и определенность результата процесса, который описан при заданных начальных данных. [^[10]]

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

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

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

4. Ясность – это понимание исполнителя алгоритма о том, что нужно сделать для выполнения поставленного алгоритма. [^[11]]

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

5. Формальность– это когда результат выполнения алгоритмов не должен зависеть от любого рода факторов, что не являются частью рассматриваемого алгоритма. [^[12]]

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

6. Результативность – завершение процесса преобразования начальной информации в конечную. Это свойство указывает применение алгоритма к всем допустимым наборам исходных данных за некоторое число шагов обеспечивает получение результата. [^[13]]

7. Корректность – означает, что если алгоритм создан для решения определенной задачи, то для всех исходных данных он должен всегда давать правильный результат и ни для каких исходных данных не будет получен неправильный результат. [^[14]]

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

1.3. Методы описания алгоритмов

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

Методы, которые используются для этого, определяют квалификацию исполнителя, в значительной степени. К базовым методам для записи алгоритма относятся: [^[15]]

– блок-схемы;

– формульно-словесный метод;

– языки программирования алгоритмов.

Формульно-словесный метод базируется на инструкциях по реализации в определенной последовательности действий с использованием символов, выражений, математическими пояснениями или выражениями на естественном языке. [^[16]]

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

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

Внутри блока описывается конкретный этап реализации алгоритма.

Рассмотрим базовые фигуры, применимые в создании блок-схем:[19]

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

2. Решение. Выбор направления алгоритма или программы в зависимости от условий (Рис.1.3) [^[17]]

3. Предопределенный процесс. Использование созданных ранее и описанных отдельно алгоритмов или же программ (функций, программных модулей, процедур). Символ служит для выполнения обращения к программным модулям (Рис.1.4). [^[18]]

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

5.Дисплей. Ввод или вывод данных, если непосредственно подключенное устройство воспроизводит их и позволяет пользователю вносить изменения (Рис.1.6). [^[19]]

6.Документ. Ввод или вывод данных на бумажный носитель (Рис.1.7).

7.Линия перехода. Указание последовательности перехода (Рис.1.8)

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

Внутри блока ставятся одинаковые номера, соответствующие для разорванной линии перехода (Рис.1.9).

9. Межстраничный соединитель. Указание связей между частями схем алгоритмов и программ, что являются расположенными на разных листах. [^[21]]

Этот блок служит для аналогичных целей, что и блок соединитель, но при расположении составных блок-схемы на других страницах (Рис.1.10) [^[22]]

10.Пуск - остановка. Начало или конец процесса обработки данных (Рис.1.11).

11.Комментарий. Связь между блоками схемы и пояснениями к ним. Позволяет включать пояснения в блок-схему, формулы и другую полезную информацию (Рис.1.12) [^[23]]

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

Языком программирования называется система условных обозначений, которая помогает более точно описать алгоритмы или инструкции программ.[^[24]]

Отметим, что языки программирования – искусственные языки. Они отличаются от человеческих языков ограниченной численностью служебных слов, строгими правилами записи команд. При их применении не допускается свободное толкование используемых выражений (что как раз характерно для естественного языка).[^[25]]

Со времени разработки первых ЭВМ человечество создало более 2,5 тысяч самых различных языков программирования. Число их пополняется каждый год все новыми и новыми, зачастую специализированными, языками.

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

Машинный вид команды для программы, состоящий из обозначений «0» и «1», указывает на то, именно какое действие должен выполнить центральный процессор в своей работе.

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

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

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

Намного проще писать программу на языке программирования, который более близок к естественному языку, а работу по «переводу» данной программы в машинный код поручить компьютеру. [^[28]]

Рассмотрим классификацию языков программирования по парадигме программирования. Вся языки делятся на следующие категории:

– императивные языки программирования, которые описывают процесс вычислений в виде команд, изменяющих состояние программы. Основными элементами императивных языков являются переменные, моделирующие ячейки памяти ЭВМ; операторы присваивания, осуществляющие пересылку данных; один или несколько итеративных циклов.

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

– декларативные языки, которые указывают, какие вычисления должны быть выполнены. Операторы в программе на языке логического программирования выполняются не в том порядке, в каком они записаны, а в порядке, определяемом системой реализации правил. [^[29]]

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

Наиболее распространенными языками высокого уровня являются C++, Java, C#, Pascal.

Вывод:

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

Глава 2. КЛАССИФИКАЦИЯ АЛГОРИТМОВ

Алгоритмы бывают линейные, разветвляющиеся и циклические. [^[31]]

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

• ввод исходных данных в память ЭВМ;

• вычисление искомых величин по формулам;

• вывод результатов из памяти ЭВМ на информационный носитель. [^[32]]

Пример 1. Составить алгоритм вычисления площади круга по формуле 2 S R = π . Решение показано на рис. 2.1.

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

Пример 2. Составить алгоритм решения для функции F(x) = 1 при x > 0 и F(x) = 0 при x < 0. Блок - схема разветвляющегося алгоритма показана на рис.2.2. Циклический алгоритм описывает вычислительный процесс, этапы которого повторяются многократно. Различают простые циклы, не содержащие внутри себя других циклов, и сложные (вложенные), содержащие несколько циклов. В зависимости от ограничения числа повторений выделяю циклы с известным числом повторений и циклы, число повторений которых заранее неизвестно. [^[33]]

2.1. Циклы с известным числом повторений

Циклический алгоритм (цикл)- это алгоритм, в котором группа операторов выполняется несколько раз подряд. [^[34]]

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

•подготовка первого выполнения цикла (присвоение счетчику цикла начального значения);

•тела цикла, которое образуют блоки, выполняемые многократно;

•изменение значения счетчика циклов и сравнение его с конечным значением. [^[35]]

Блок-схемы циклических алгоритмов существенно отличаются структурами повторения "повторять ДО "(повторять до выполнения условия окончания цикла) или "повторять ПОКА " (повторять пока выполняются условия продолжения циклического процесса). В первом варианте проверка условий окончания циклических вычислений осуществляется в конце цикла (рис. 2.3, а), а во втором - в начале цикла (рис. 2.3, б). Как видно из рисунка, цикл "повторять ДО "выполняется, по крайней мере, один раз, а цикл "повторять ПОКА" может сразу привести к выходу из цикла. Подготовка выполнения первого цикла. [^[36]]

Пример 3. Составить алгоритм решения задачи вычисления N первых членов геометрической прогрессии, используя формулу n+1 n b =b *q для любых b и q, где n - текущий член геометрической прогрессии.

Блок-схема алгоритма решения данного примера показана в двух вариантах: с использованием цикла "ДО" (рис. 2.4, а) и цикла "ПОКА"(рис. 2.4, б).

2.2. Циклы с неизвестным числом повторений

Примером циклов, число повторений которых не задано, являются итерационные вычислительные процессы. В них решение задачи реализуется путем последовательного приближения к искомому результату. Процесс является циклическим, поскольку заключается в многократных вычислениях. Начальное приближение Y0 выбирается заранее или задается по определенным правилам. Заканчивается итерационное вычисление при выполнении условия, где d- допустимая ошибка вычисления. [^[37]]

На каком-то шаге условие не выполнится (ложь) и тогда происходит выход из цикла и продолжается выполнение программы. [^[38]]

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

Пример 4. Составить алгоритм вычисления функции с точностью d, используя рекуррентную формулу

Если начальное приближение y1 = x, тогда на первом цикле вычисления будем иметь

Блок - схема алгоритма решения примера 4 приведена на рис. 2.6. [^[39]]

Вывод:

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

Глава 3. ПРИМЕРЫ АЛГОРИТМОВ

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

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

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

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

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

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

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

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

else оператор;

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

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

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

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

}

else {

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

}

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

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

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, может содержать аналогичные константы.[^[44]]

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

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

– цикл for;

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

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

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

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

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

– тело цикла;

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

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

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

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

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

{

тело цикла;

}

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

int summa = 0;

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

s = s + i;

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

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

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

{

тело цикла

};

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

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

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

do

{

тело цикла

}

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

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

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

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

3.2. Алгоритм сортировки пузырьком

Еще одно применение метода грубой силы к задаче сортировки состоит в сравнении соседних элементов и их обмене, если они находятся не в надлежащем порядке.[^[52]] Обход массива повторяется до тех пор, пока массив не будет упорядочен.

Реализация алгоритма:

using System;

class Program

{

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

static void Swap(ref int e1, ref int e2)

{

var temp = e1;

e1 = e2;

e2 = temp;

}

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

static int[] BubbleSort(int[] array)

{

var len = array.Length;

for (var i = 1; i < len; i++)

{

for (var j = 0; j < len - i; j++)

{

if (array[j] > array[j + 1])

{

Swap(ref array[j], ref array[j + 1]);

}

}

}

return array;

}

static void Main(string[] args)

{

Console.WriteLine("Сортировка пузырьком");

Console.Write("Введите элементы массива: ");

var parts = Console.ReadLine().Split(new[] { " ", ",", ";" }, StringSplitOptions.RemoveEmptyEntries);

var array = new int[parts.Length];

for (int i = 0; i < parts.Length; i++)

{

array[i] = Convert.ToInt32(parts[i]);

}

Console.WriteLine("Отсортированный массив: {0}", string.Join(", ", BubbleSort(array)));

Console.ReadLine();

}

}

Результат работы программы (рис.3.1):

3.3. Алгоритм шифрования XOR

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

Формула для получения закодированного текста: Cn = Mn xor Kn.

Ключ шифрования можно получить двумя способами :

Повторять ключевое слово пока длина гаммы не будет равна длине сообщения;

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

Реализация алгоритма:

using System;

public class XORCipher

{

//генератор повторений пароля

private string GetRepeatKey(string s, int n)

{

var r = s;

while (r.Length < n)

{

r += r;

}

return r.Substring(0, n);

}

//метод шифрования/дешифровки

private string Cipher(string text, string secretKey)

{

var currentKey = GetRepeatKey(secretKey, text.Length);

var res = string.Empty;

for (var i = 0; i < text.Length; i++)

{

res += ((char)(text[i] ^ currentKey[i])).ToString();

}

return res;

}

//шифрование текста

public string Encrypt(string plainText, string password)

=> Cipher(plainText, password);

//расшифровка текста

public string Decrypt(string encryptedText, string password)

=> Cipher(encryptedText, password);

}

class Program

{

static void Main(string[] args)

{

var x = new XORCipher();

Console.Write("Введите текст сообщения: ");

var message = Console.ReadLine();

Console.Write("Введите пароль: ");

var pass = Console.ReadLine();

var encryptedMessageByPass = x.Encrypt(message, pass);

Console.WriteLine("Зашифрованное сообщение {0}", encryptedMessageByPass);

Console.WriteLine("Расшифрованное сообщение {0}", x.Decrypt(encryptedMessageByPass, pass));

Console.ReadLine();

}

}

Результат работы программы (рис.3.2):

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

private string GetRandomKey(int k, int len)

{

var gamma = string.Empty;

var rnd = new Random(k);

for (var i = 0; i < len; i++)

{

gamma += ((char)rnd.Next(35, 126)).ToString();

}

return gamma;

}

3.4. Алгоритм рекурсивного бинарного поиска

Бинарный поиск представляет собой в высшей степени эффективный алгоритм для поиска в отсортированном массиве.[ ^[53]]

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

Если они равны, возвращаем индекс середины;

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

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

Реализация алгоритма:

using System;

class Program

{

//метод для рекурсивного бинарного поиска

static int BinarySearch(int[] array, int searchedValue, int first, int last)

{

//границы сошлись

if (first > last)

{

//элемент не найден

return -1;

}

//средний индекс подмассива

var middle = (first + last) / 2;

//значение в средине подмассива

var middleValue = array[middle];

if (middleValue == searchedValue)

{

return middle;

}

else

{

if (middleValue > searchedValue)

{

//рекурсивный вызов поиска для левого подмассива

return BinarySearch(array, searchedValue, first, middle - 1);

}

else

{

//рекурсивный вызов поиска для правого подмассива

return BinarySearch(array, searchedValue, middle + 1, last);

}

}

}

//программа для бинарного поиска элемента в упорядоченном массиве

static void Main(string[] args)

{

Console.WriteLine("Бинарный поиск(рекурсивная реализация)");

Console.Write("Введите элементы массива: ");

var s = Console.ReadLine().Split(new[] { " ", ",", ";" }, StringSplitOptions.RemoveEmptyEntries);

var array = new int[s.Length];

for (int i = 0; i < s.Length; i++)

{

array[i] = Convert.ToInt32(s[i]);

}

//сортируем массив

Array.Sort(array);

Console.WriteLine("Упорядоченный массив: {0}", string.Join(", ", array));

while (true)

{

Console.Write("Введите искомое значение или -777 для выхода: ");

var k = Convert.ToInt32(Console.ReadLine());

if (k == -777)

{

break;

}

var searchResult = BinarySearch(array, k, 0, array.Length - 1);

if (searchResult < 0)

{

Console.WriteLine("Элемент со значением {0} не найден", k);

}

else

{

Console.WriteLine("Элемент найден. Индекс элемента со значением {0} равен {1}", k, searchResult);

}

}

Console.ReadLine();

}

}

Вывод:

В данной главе рассмотрены примеры кода алгоритмов на языке C++.

Разобрали как работают популярные их реализации на примере алгоритма сортировки пузырьком, шифрования XOR и алгоритма рекурсивного бинарного поиска.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

- рассмотрены методы реализации и примеры составления алгоритмов различной структуры;

- приведены примеры применения алгоритмов при написании программ на языке c++.

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

1. Айвор Хортон. Visual C++ 2010. Полный курс. Издательский дом «Вильямс». – 2014. – 300 с.
2. Борис Пахомов. С/С++ и MS Visual C++ 2010 для начинающих. БХВ-Петербург. – 2014. – 436 с.
3. Брайан Керниган Алгоритмизация и программирование. Издательство «Невский диалект». – 2014. – 320 с.
4. Бьерн Страуструп. Программирование. Принципы и практика использования. Издательский дом «Вильямс». – 2015. – 258 с.
5. Джесс Либерти. Освой самостоятельно С++ за 21 день. Издательский дом «Вильямс». – 2012. – 230 с.
6. Динман М.И. Алгоритмизация и программирование. Освой на примерах. – СПб.: БХВ-Петербург, 2012.– 260 с.
7. Дэвид Гриффитс, Дон Гриффитс. Изучаем программирование на С. Издательство «Эксмо». – 2013. – 400 с.
8. Кнут, Дональд, Эрвин. Искусство программирования. Том 1. Основные алгоритмы. 3-е изд. Пер. с англ. – : Уч. пос. М.: Издательский дом. «Вильямс», 2014.– 720с.
9. Кубенский А.А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++. – СПб.: БХВ-Петербург, 2013. – 464с.
10. Майерс С. Эффективное использование алгоритмизации. 50 рекомендаций по улучшению ваших программ и проектов. Пер. с англ. – М.: ДМК Пресс; – СПб.: Питер. 2013.–240с.
11. Прата С. Язык программирования С++. Издание 6. Издательский дом «Вильямс» – 2016. – 304 с.
12. Р. Лафоре. Объектно-ориентированное программирование в С++. Издательство «Питер». Издание 4. – 2014. – 628 с.
13. С++ Стандартная библиотека. Для профессионалов./Н. Джосьютис. – СП Питер, 2012. – 350 с.
14. Седжвик Роберт. Фундаментальные алгоритмы. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./ Седжвик Роберт. К.: Издательство «ДиаСофт», – 2014. – 500 с.
15. Скляров В.А. Язык С++ и объектно-ориентированное программирование. Справочное пособие. – Минск. «Вышейшая школа». – 2012. – 478с.
16. Харви Дейтел, Пол Дейтел. Как программировать на С++. Пер. с англ. – М.: ЗАО «Издательство БИНОМ», 2012. – 430 с.
17. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учеб. пособие. – Финансы и статистика, 2014. – 464с.
18. Штерн Виктор. Основы С++: Методы программной инженерии.– Издательство «Лори», 2013. – 860с.
19. Язык С++: Учеб. Пособие /И.Ф. Астахова, С.В. Власов, В.В. Фертиков, А.В. Ларин.–Мн.: Новое знание, 2013. – 203 с.
20. Программирование и основы алгоритмизации: Для инженерных специальностей технических университетов и вузов. /А.Г.Аузяк, Ю.А.Богомолов, А.И. Маликов, Б.А. Старостин. Казань: Изд-во Казанского национального исследовательского технического ун-та - КАИ, 2013, 153 с.
21. Основы алгоритмизации и программирования: учеб. пособие / Т.А. Жданова, Ю.С. Бузыкова. – Хабаровск : Изд-во Тихоокеан. гос.ун-та, 2011.56с.
22. Макаров В.Л. Программирование и основы алгоритмизации.: учебн. пособие.-Спб., СЗТУ, 2003, - 110с.
23. Левитин А. В. Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 144–146. — 576 с.
24. Левитин А. В. Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 180–183. — 576 с.

ПРИЛОЖЕНИЕ

Рис 1.1 «Мугаммад аль-Хорезми»

Рис. 1.2 «Блок - Процесс»

Рис.1.3 «Блок - Решение»

Рис.1.4 «Блок – Предопределенный процесс»

Рис.1.5 «Блок – Ручной ввод»

Рис.1.6 «Блок – Дисплей»

Рис.1.7 «Блок – Документ»

Рис.1.8 «Блок - Линии перехода»

Рис.1.9 «Блок – Соединитель»

Рис.1.10 «Блок – Междустрочный соединитель»

Рис.1.11 «Блок – Пуск остановка»

Рис.1.12 «Блок – Комментарий»

Рис.2.1 «Блок - схема алгоритма вычисления площади круга» 

Рис.2.2 «Блок - схема разветвляющегося алгоритма»

Рис.2.3 «Блок-схемы циклических алгоритмов»

Рис.2.4 «Блок-схема алгоритма решения задачи»

Рис.2.5 «Блок - схема типовой структуры алгоритма итерационных вычислений»

Рис.2.6 «Блок - схема алгоритма решения примера 4»

Рис.3.1. «Алгоритм сортировки пузырьком»

Рис.3.2. «Алгоритм шифрования XOR»

1. Айвор Хортон. Visual C++ 2010. Полный курс. Издательский дом «Вильямс». – 2014. 300с. ↑

2. Борис Пахомов. С/С++ и MS Visual C++ 2010 для начинающих. БХВ-Петербург. – 2014. – 436 с. ↑

3. Бьерн Страуструп. Программирование. Принципы и практика использования. Издательский дом «Вильямс». 2015. – 258 с. ↑

4. Айвор Хортон. Visual C++ 2010. Полный курс. Издательский дом «Вильямс». – 2014. – 300 с. ↑

5. Майерс С. Эффективное использование алгоритмизации. 50 рекомендаций по улучшению ваших программ и проектов. Пер. с англ. – М.: ДМК Пресс; – СПб.: Питер. 2013.–240с. ↑

6. Брайан Керниган Алгоритмизация и программирование. Издательство «Невский диалект». – 2014. – 320 с.

   ↑

7. Борис Пахомов. С/С++ и MS Visual C++ 2010 для начинающих. БХВ-Петербург. – 2014. – 436 с. ↑

8. Динман М.И. Алгоритмизация и программирование. Освой на примерах. – СПб.:БХВ-Петербург,2012.–260с. ↑

9. Кубенский А.А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++. – СПб.: БХВ-Петербург, 2013. – 464с. ↑

10. С++ Стандартная библиотека. Для профессионалов./Н. Джосьютис. – СП Питер, 2012. – 350 с. ↑

11. Седжвик Роберт. Фундаментальные алгоритмы. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./ Седжвик Роберт. К.: Издательство «ДиаСофт», – 2014. – 500 с. ↑

12. Борис Пахомов. С/С++ и MS Visual C++ 2010 для начинающих. БХВ-Петербург. – 2014. – 436 с. ↑

13. Айвор Хортон. Visual C++ 2010. Полный курс. Издательский дом «Вильямс». – 2014. – 300 с. ↑

14. Майерс С. Эффективное использование алгоритмизации. 50 рекомендаций по улучшению ваших программ и проектов. Пер. с англ. – М.: ДМК Пресс; – СПб.: Питер. 2013.–240с. ↑

15. Дэвид Гриффитс, Дон Гриффитс. Изучаем программирование на С. Издательство «Эксмо». – 2013. – 400с. ↑

16. Кнут, Дональд, Эрвин. Искусство программирования. Том 1. Основные алгоритмы. 3-е изд. Пер. с англ. – : Уч. пос. М.: Издательский дом. «Вильямс», 2014.– 720с. ↑

17. Динман М.И. Алгоритмизация и программирование. Освой на примерах. – СПб.: БХВ-Петербург, 2012.– 260 с. ↑

18. Джесс Либерти. Освой самостоятельно С++ за 21 день. Издательский дом «Вильямс». – 2012. – 230 с. ↑

19. Кубенский А.А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++. – СПб.: БХВ-Петербург, 2013. – 464с. ↑

20. Штерн Виктор. Основы С++: Методы программной инженерии.– Издательство «Лори», 2013. – 860с. ↑

21. Скляров В.А. Язык С++ и объектно-ориентированное программирование. Справочное пособие. – Минск. «Вышейшая школа». – 2012. – 478с. ↑

22. С++ Стандартная библиотека. Для профессионалов./Н. Джосьютис. – СП Питер, 2012. – 350 с. ↑

23. Прата С. Язык программирования С++. Издание 6. Издательский дом «Вильямс» – 2016. – 304 с. ↑

24. Р. Лафоре. Объектно-ориентированное программирование в С++. Издательство «Питер». Издание 4. – 2014. – 628 с. ↑

25. Майерс С. Эффективное использование алгоритмизации. 50 рекомендаций по улучшению ваших программ и проектов. Пер. с англ. – М.: ДМК Пресс; – СПб.: Питер. 2013.–240с. ↑

26. С++ Стандартная библиотека. Для профессионалов./Н. Джосьютис. – СП Питер, 2012. – 350 с. ↑

27. Р. Лафоре. Объектно-ориентированное программирование в С++. Издательство «Питер». Издание 4. – 2014. – 628 с. ↑

28. Седжвик Роберт. Фундаментальные алгоритмы. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./ Седжвик Роберт. К.: Издательство «ДиаСофт», – 2014. – 500 с. ↑

29. Майерс С. Эффективное использование алгоритмизации. 50 рекомендаций по улучшению ваших программ и проектов. Пер. с англ. – М.: ДМК Пресс; – СПб.: Питер. 2013.–240с. ↑

30. Прата С. Язык программирования С++. Издание 6. Издательский дом «Вильямс» – 2016. – 304 с. ↑

31. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учеб. пособие. – Финансы и статистика, 2014. – 464с. ↑

32. Харви Дейтел, Пол Дейтел. Как программировать на С++. Пер. с англ. – М.: ЗАО «Издательство БИНОМ», 2012. – 430 с.19. ↑

33. Макаров В.Л. Программирование и основы алгоритмизации.: учебн.пособие.-Спб., СЗТУ, 2003, - 110с. ↑

34. Основы алгоритмизации и программирования: учеб. пособие / Т.А. Жданова, Ю.С. Бузыкова. – Хабаровск: Изд-во Тихоокеан. гос.ун-та, 2011. –56 с. ↑

35. Программирование и основы алгоритмизации для инженерных

    специальностей технических университетов и вузов. /А.Г. Аузяк, Ю.А.Богомолов, А.И. Маликов, Б.А. Старостин. Казань: Изд-во Казанского ун-та - КАИ, 2013, 153 с. ↑

36. Макаров В.Л. Программирование и основы алгоритмизации.: учебн.пособие.-Спб., СЗТУ, 2003, - 110с. ↑

37. Программирование и основы алгоритмизации для инженерных специальностей технических университетов и вузов. /А.Г. Аузяк, Ю.А.Богомолов, А.И. Маликов, Б.А. Старостин. Казань: Изд-во Казанского национального исследовательского технического ун-та - КАИ, 2013, 153 с. ↑

38. Основы алгоритмизации и программирования: учеб. пособие / Т.А. Жданова, Ю.С. Бузыкова. – Хабаровск: Изд-во Тихоокеан. гос.ун-та, 2011. –56 с. ↑

39. Макаров В.Л. Программирование и основы алгоритмизации.: учебн.пособие.-Спб., СЗТУ, 2003, - 110с. ↑

40. Лафоре. Объектно-ориентированное программирование в С++. Издательство «Питер». Издание 4. – 2014. – 628 с. ↑

41. С++ Стандартная библиотека. Для профессионалов./Н. Джосьютис. – СП Питер, 2012. – 350 с. ↑

42. Борис Пахомов. С/С++ и MS Visual C++ 2010 для начинающих. БХВ-Петербург. – 2014. – 436 с. ↑

43. Бьерн Страуструп. Программирование. Принципы и практика использования. Издательский дом «Вильямс». – 2015. – 258 с. ↑

44. Седжвик Роберт. Фундаментальные алгоритмы. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./ Седжвик Роберт. К.: Издательство «ДиаСофт», – 2014. – 500 с. ↑

45. Штерн Виктор. Основы С++: Методы программной инженерии.– Издательство «Лори», 2013. – 860с. ↑

46. Джесс Либерти. Освой самостоятельно С++ за 21 день. Издательский дом «Вильямс». – 2012. – 230с. ↑

47. Седжвик Роберт. Фундаментальные алгоритмы. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./ Седжвик Роберт. К.: Издательство «ДиаСофт», – 2014. – 500 с. ↑

48. Айвор Хортон. Visual C++ 2010. Полный курс. Издательский дом «Вильямс». – 2014. – 300 с. ↑

49. Динман М.И. Алгоритмизация и программирование. Освой на примерах. – СПб.: БХВ-Петербург, 2012.– 260 с. ↑

50. Дэвид Гриффитс, Дон Гриффитс. Изучаем программирование на С. Издательство «Эксмо». – 2013. – 400 с. ↑

51. Бьерн Страуструп. Программирование. Принципы и практика использования. Издательский дом «Вильямс». – 2015. – 258 с. ↑

52. Левитин А. В. Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 144–146. — 576 с. ↑

53. Левитин А. В. Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 180–183. — 576 с. ↑