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

[ n 1 / 2 ] = 86 {\displaystyle [n^{1/2}]=86}

Так как остаток деления 7399 на 7 равен 0, то 7399 не является простым. Графически алгоритм перебора делителей представлен на рис. 3.2.

Рис. 3.2 Алгоритм «перебора делителей» [14]

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

3.3 Алгоритм решето Эратосфена

Решето Эратосфена – это алгоритм нахождения простых чисел до заданного числа n. В процессе выполнения данного алгоритма постепенно отсеиваются составные числа, кратные простым, начиная с 2.

Название «решето» метод получил потому, что, согласно легенде, Эратосфен писал числа на дощечке, покрытой воском, и прокалывал дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые. Эратосфен дал таблицу простых чисел до 1000 (см. Приложение 3).

Схематично алгоритм «Решето Эратосфена» представлен на рис. 3.3.

Рис. 3.3 Алгоритм «Решето Эратосфена» [14]

Приведем пример алгоритма «Решето Эратосфена».

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
2. Пусть переменная p изначально равна двум – первому простому числу.
3. Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
4. Найти первое не зачеркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
5. Повторять шаги 3 и 4, пока возможно.

Теперь все не зачеркнутые числа в списке – это все простые числа от 2 до n.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать начиная сразу с числа p², потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p² станет больше, чем n. Также, все простые числа (кроме 2) – нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p².

Приведем пример алгоритма «Решето Эратосфена» для n = 30.

Запишем натуральные числа, начиная от 2, до 30 в ряд:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Первое число в списке, 2 – простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 2 (то есть, каждое второе, начиная с 2² = 4):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее не зачеркнутое число, 3 – простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 3 (то есть, каждое третье, начиная с 3² = 9):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее не зачёркнутое число, 5 – простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 5 (то есть, каждое пятое, начиная с 5² = 25):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее не зачеркнутое число –7. Его квадрат, 49– больше 30, поэтому на этом работа завершена. Все составные числа уже зачеркнуты:

2 3 5 7 11 13 17 19 23 29

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

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

Заключение

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

На проведенной проделанной работы можно сделать следующие выводы.

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

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

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

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

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

Запись алгоритма на формальном языке называется программой. Иногда само понятие алгоритма отождествляется с его записью, так что слова «алгоритм» и «программа» — почти синонимы. Небольшое различие заключается в том, что под алгоритмом, как правило, понимают основную идею его построения. Программа же всегда связана с записью алгоритма на конкретном формальном языке.

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

Список использованной литературы

1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: Пер. с англ.: – М.: Издательский дом «Вильямс», 2001 г. –384 с., ил.
2. Библиотека программиста // http://www.programmer-lib.ru/assemw_page.php?id=1 (дата обращения 27.07.2018)
3. Брой, М. Информатика. Основополагающее введение: В 4-х ч. Ч.1. / М. Брой. – М.: Диалог-МИФИ, 1996. – 299 с.
4. Википедия // https://ru.wikipedia.org/wiki (дата обращения 11.08.2018)
5. Вирт, Н. Алгоритмы и структуры даны учебник / Н. Вирт. – М.: Мир, 1989. – 360 с.
6. Информатика: базовый курс: учебник для студентов вузов, бакалавров, магистров, обучающихся по направлению «Информатика» / О.А. Акулов, Н.В. Медведев. 6-е изд., испр. и доп. – М.: Издательство «Омега-Л», 2009. – 574 с.
7. Кадырова, Г.Р. Основы алгоритмизации и программирования: учебное пособие / Г.Р. Кадырова. – Ульяновск, УлГТУ, 2014 – 95 с.
8. Каймин, В.А. Информатика: учебник / В.А. Каймин. – М.: Проспект, 2011. – 272 с.
9. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001 г. – 960 с., 263 ил.
10. Макконнел Дж. Анализ алгоритмов. Вводный курс. – М.: Техносфера, 2002 г. –304 с.
11. Самуйлов С.В. Методика сравнительного анализа алгоритмов на примере алгоритмов последовательного поиска // Концепт, 2014. – №9. // https://e-koncept.ru/2014/14236.htm (Дата обращения 15.08.2018)
12. Семакин, И.Г. Основы алгоритмизации и программирования: учебник для студ. учреждений сред. проф. Образования / И.Г. Семакин, А.П. Шестаков. – 3-е изд. стер. – М.: Издательский центр «Академия», 2012. – 400 с.
13. Соболь, Б.В. Информатика и программирование: учебное пособие / Б.В. Соболь. – Ростов н/Д: Феникс, 2006 – 354 с.
14. Теория алгоритмов // https://inf1.info (дата обращения 01.08.2018)
15. Тихомиров, В. М. Великие математики прошлого и их великие теоремы. – 2-е изд., испр. – МЦНМО, 2003. – 16 с.

Приложение 1. Основные элементы блок--схемы

Приложение 2. Структура разветвляющегося алгоритма

Начало

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

Ввод данных

Действия

Условие

Действия 1

Действия 2

Окончание

Вывод данных

Окончание

Приложение 3. Таблица алгоритма «Решето Эратосфена»