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

Рисунок 27Источник 8

Пример в виде блок-схемы: Требуется, не пользуясь операцией деления, получить частное q и остаток r от деления натурального числа x на натуральное число y.

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

Рисунок 28Источник 8

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

Рисунок 29Источник 8

На алгоритмическом языке эта конструкция записывается так:

Рисунок 30Источник 8

Выполняется цикл-ДО следующим образом:

• выполняется тело цикла;
• проверяется условие (вычисляется значение логического выражения); если условие не удовлетворяется («Нет»), то снова выполняется тело цикла и осуществляется переход к проверке условия;
• если же условие удовлетворяется, то выполнение цикла заканчивается.

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

Пример: Алгоритм по выучиванию наизусть четверостишия.

Рисунок 31Источник 8

Пример: вычислим значение переменной b согласно следующему алгоритму:

Рисунок 32Источник 8

Так же этот алгоритм в виде табличной записи:

Рисунок 33Источник 8

Пример: Спортсмен приступает к тренировкам по следующему графику: в первый день он должен пробежать 10 км; каждый следующий день следует увеличивать дистанцию на 10 от нормы предыдущего дня. Как только дневная норма достигнет или превысит 25 км, необходимо прекратить её увеличение и далее пробегать ежедневно ровно 25 км. Начиная с какого дня спортсмен будет пробегать 25 км?

Пусть x — количество километров, которое спортсмен пробежит в некоторый i-й день. Тогда в следующий (i+1)-й день он пробежит x+0,1x километров (0,1x — это 10 от x).

Рисунок 34Источник 8

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

Рисунок 35Источник 8

На алгоритмическом языке эта конструкция записывается так:

Рисунок 36Источник 8

Важно понимать! В цикле-ДЛЯ всегда есть параметр цикла — величина целого типа, изменяющаяся в ходе выполнения цикла от своего начального значения i1 до конечного значения i2 с шагом R.

Выполняется цикл-ДЛЯ следующим образом:

• параметру цикла присваивается начальное значение;
• параметр цикла сравнивается с конечным значением; если параметр цикла не превышает конечное значение, то выполняется тело цикла, увеличивается значение параметра цикла на шаг и снова осуществляется проверка параметра цикла; если же параметр цикла превышает конечное значение, то выполнение цикла заканчивается.

Если величина шага в цикле с параметром равна единице, то шаг не указывают. Мы ограничимся рассмотрением именно таких циклов. В отличие от двух предыдущих конструкций (цикл-ПОКА, цикл-ДО) цикл-ДЛЯ имеет строго фиксированное число повторений, что позволяет избежать зацикливания, т.е. ситуации, когда тело цикла выполняется бесконечно.

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

Рисунок 37Источник 8

Для исполнителя Робот цикл с известным числом повторений реализуется с помощью следующей конструкции:

Рисунок 38Источник 8

Пример: Так, если правее Робота не встретится препятствий, то, выполнив приведённый ниже алгоритм, он переместится на  пять клеток вправо и закрасит эти клетки:

Рисунок 39Источник 8

3.Зачем же нужны алгоритмы?

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

За всю историю компьютерных наук сложилось понимание, какие алгоритмы и структуры данных (способы их хранения) нужны для решения практических задач — так называемый джентльменский набор, который должен знать каждый разработчик. Например, сортировка: товары в магазине сортируют по стоимости или сроку годности, а рестораны — по удалённости или рейтингу. Хэш-таблицы помогают проверить корректность пароля и не хранить его на сайте в открытом виде, графы — находить кратчайший путь и хранить связи между пользователями в соцсетях.

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

Знание алгоритмов помогает найти эффективное решение задачи

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

Аналогично и в программировании. Задача разработчика — использовать наиболее эффективное решение. Для этого нужно учитывать скорость работы программы, объём потребляемой памяти, экономическую эффективность (насколько стоимость решения оправдана конечным результатом), простоту реализации, масштабируемость. [Источник: София Техажева, руководитель программ «Python-разработчик» и «Алгоритмы для разработчиков» в Яндекс.Практикуме].

Заключение

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

Источники

Источники 1- Программирование и основы алгоритмизации: Для инженерных

специальностей технических университетов и вузов. /А.Г. Аузяк, Ю.А.

Богомолов, А.И. Маликов, Б.А. Старостин. Казань: Изд-во Казанского

национального исследовательского технического ун-та - КАИ, 2013, 153 с.

2- Видеоурок по информатике «Алгоритмы, величины, структура алгоритмов» https://www.youtube.com/watch?v=ct8agmyOW_U

3- http://csaa.ru/sposoby-predstavlenija-algoritmov-2/

4- http://inform-school.narod.ru/bl2_t1.htm

5- http://bourabai.ru/alg/a12.html

6-https://urok.1sept.ru/%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8/211674/#:~:text=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%20%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9%20%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B%20%E2%80%93%20%D1%8D%D1%82%D0%BE%20%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC,%D0%B1%D1%8B%D0%B2%D0%B0%D0%B5%D1%82%20%D0%BD%D0%B5%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B8%D0%BC%D0%BE%20%D0%BF%D0%BE%D0%B2%D1%82%D0%BE%D1%80%D0%B8%D1%82%D1%8C%20%D0%BD%D0%B5%D1%81%D0%BA%D0%BE%D0%BB%D1%8C%D0%BA%D0%BE%20%D1%80%D0%B0%D0%B7.

7-https://sites.google.com/site/elektronnyjucebnikmitrofanova/tema-1-algoritm/tema-1-3-vidy-algoritmov/cikl-s-postusloviem

8-https://www.yaklass.ru/p/informatika/8-klass/osnovy-algoritmizatcii-14923/osnovnye-algoritmicheskie-konstruktcii-13987/re-f874a988-2062-48c6-800e-64baab38bfb8 (Босова Л. Л., Босова А. Ю., Информатика: учебник для 8 класса. М. : БИНОМ. Лаборатория знаний, 73 с.)