5.2. Разработка алгоритма

Как составить простые алгоритмы задач с использованием циклических алгоритмов в Python?

Подумай

  • Какие имеются сложности в создании алгоритмов для задач по теме циклы?
  • Какие распространенные алгоритмы известны, которые созданы с использованием циклических алгоритмов?

Новые знания

Алгоритм задачи

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

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

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

   Одним из важных аспектов алгоритма является скорость алгоритма. В процессе программирования перед программистом постоянно стоит проблема экономии рабочего времени программы. Например, на тему «встроенные циклы» выполнили задачу по выводу на экран простых чисел из заданной последовательности чисел. Для определения простых чисел мы использовали цикл for с параметром до квадратного корня проверяемого числа. Почему? Остановимся на причинах. Возьмем, например, 50, как тестируемое число. Если необходимо определить является ли это число простым или составным, то необходимо разделить это число на все числа между 1 и 50. Для того, чтобы проверить число 50 нужно выполнить цикл 50 раз. Для того, чтобы проверить число большее, чем 1 000 000, необходимо выполнить тело цикла миллионах раз. Это, конечно, очень много, учитывая, что для того, чтобы цикл выполнился 1 раз он работает около 1 секунды, соответственно, миллион раз – миллион секунд, разумеется это очень много.

for j in range(1, n)

  • Время работы
  • Длина
  • Скорость
  • Программист

   Следовательно, разработанный алгоритм неэффективен. Должен быть другой эффективный алгоритм. Если учесть, что в этом примере обязательно разделение заданного числа 50 на числа от 1 до 50, и учитывая, что делители любого числа могут быть равны до половины того же числа, за исключением самого числа (например, делители 50 могут быть числа до 25, не считая 50). В нем не остается необходимости разделить число до 50. В этом случае работа цикла сокращается в 2 раза и работает 25 раз, чтобы проверить является ли число 50 простым.

for j in range(1, n //2+1)

   Если использовать теорию чисел, то работа цикла может быть еще больше сокращена.

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

Pa

   Например, число 59 просто число. Так как корень квадратный из него √59 ≈7,6 не делится ни на одно из простых чисел 2, 3, 5, 7. Таким образом, для проверки числа 50 также 2 ...7 .достаточно 6-кратной работы цикла (√50≈ 7). Это в 8 раз меньше исходного решения. А если проверочное число 1000000, то цикл работает 1000 раз.

for j in range (2,round(math.sqrt(x)))

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

Практическая работа

   «Покраска забора».

    Для покраски забора вокруг дома у Болата имеются краски 5 разных цветов. Для того, чтобы определить, каким цветом покрасить Болат нанес краски разных цветов на забор (рисунок 1). В результате забор стал разноцветным. Болат хочет покрасить забор в один цвет, прилагая при этом как можно меньше усилий. Помогите Болату. Количество досок в заборе Болата N (n < 100). И заданы количество досок, покрашенных одним из пяти цветов. В качестве ответа на задачу должно вывестись наименьшее количество досок, подлежащих повторной покраске.

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

«Найдите максимально повторяющееся число в последовательности и количество его повторений.»

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

Рисунок 3. Код программы

  • a, то
  • условие
  • число p
  • является
  • р≤√а.
  • Если
  • Теорема.
  • простое
  • наименьшим
  • делителем
  • числа
  • выполняется

Анализ

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

Прикрепите свой файл к этому заданию, нажав «Добавить свой материал».

Синтез

Задача: Дана последовательность, состоящая из N чисел. Для этой последовательности составь программу, которая находит сумму членов последовательности до Р-го места (1≤Р, N<100).

Прикрепите свой файл к этому заданию, нажав «Добавить свой материал».

Домашнее задание

Прикрепите свой файл к этому заданию, нажав «Добавить свой материал».

Өтінемін күте тұрыңыз