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

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

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 с. ↑