На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз, пока соблюдается некоторое заранее установленное условие.
Например, если вам необходимо перебрать ящик с яблоками, чтобы отделить гнилые от спелых, то нам необходимо повторять следующие действия:
1. Взять яблоко.
2. Посмотреть, не гнилое ли оно.
3. Если гнилое – выбросить, если нет – переложить в другой ящик.
Выполнять этот набор действий необходимо до тех пор, пока не закончатся яблоки в ящике.
Форма организации действий, при которой выполнение одной и той же последовательности действий повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением).
Алгоритм, содержащий циклы, называется циклическим алгоритмом, или алгоритмом с повторениями.
Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием.
Следует разрабатывать алгоритмы, не допускающие таких ситуаций.
Рассмотрим алгоритм работы будильника на телефоне, который должен зазвонить в 8:00 утра, а затем звонить через каждые 10 минут, до тех пор пока его не выключат.
В этом случае его блок-схема выглядит так: (блок-схему (рис. 9.) см. в конце конспекта)
На этом уроке мы обсудили три типа алгоритмов – линейные алгоритмы, алгоритмы с ветвлениями и алгоритмы с повторениями.
На следующем уроке мы на практике обсудим составление алгоритмов.
Решето Эратосфена
Вспомним определение простого натурального числа.
Натуральное число называют простым, если оно имеет только два делителя: единицу и само это число. Остальные числа называются составными. При этом число 1 не является ни простым, ни составным.
Примеры простых чисел: 2, 3, 5, 7.
Примеры составных чисел: 4, 6, 8.
В III веке до нашей эры греческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых чисел, меньших заданного числа п:
1. выписать все натуральные числа от 1 до n;
2. вычеркнуть 1;
3. подчеркнуть наименьшее из неотмеченных чисел;
4. вычеркнуть все числа, кратные подчеркнутому на предыдущем шаге числу;
5. если в списке имеются неотмеченные числа, то перейти к шагу 3, в противном случае все подчеркнутые числа – простые.
Это циклический алгоритм. При его выполнении повторение шагов 3–5 происходит, пока в исходном списке остаются неотмеченные числа.
Рассмотрим результат этого алгоритма. Выпишем все простые числа от 1 до 25.
Выпишем числа от 1 до 25.
Вычеркнем 1. Теперь подчеркнем двойку. Вычеркнем все четные числа.
Так как не все числа отмечены, то подчеркиваем 3. Теперь вычеркиваем все числа, которые делятся на 3.
Так как не все числа отмечены, то подчеркиваем 5. Теперь вычеркиваем число 25.
Так как не все числа отмечены, то подчеркиваем 7.
Вычеркнуть ничего нельзя, но не все числа отмечены, поэтому подчеркиваем 11.
Вычеркнуть ничего нельзя, но не все числа отмечены, поэтому подчеркиваем 13. Снова нельзя ничего вычеркнуть – подчеркиваем 17, затем 19 и 23.
Теперь все числа отмечены.
Получаем простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23.
Рис. 7. Блок-схема для смены лампочки
Рис. 8. Блок-схема действий шестиклассника
Рис. 9. Блок-схема работы будильника
