Алгоритмы с повторениями

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

Форма организации действий, при которой выполнение одной и той же последовательности действий повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением).

Алгоритм, содержащий циклы, называется циклическим алгоритмом или алгоритмом с повторениями.

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

Рассмотрим пример из математики.

Натуральное число называют простым, если оно имеет только два делителя: единицу и само это число¹.

¹ Напомним, что число 1 не относят ни к составным (имеющим более двух делителей), ни к простым числам.

2, 3, 5, 7 — простые числа; 4, 6, 8 — нет. В III веке до нашей эры греческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых чисел, меньших заданного числа n:

1) выписать все натуральные числа от 1 до n;

2) вычеркнуть 1;

3) подчеркнуть наименьшее из неотмеченных чисел;

4) вычеркнуть все числа, кратные подчеркнутому на предыдущем шаге;

5) если в списке имеются неотмеченные числа, то перейти к шагу 3, в противном случае все подчеркнутые числа — простые.

Это циклический алгоритм. При его выполнении повторение шагов 3-5 происходит, пока в исходном списке остаются неотмеченные числа.

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

Самое главное

В зависимости от порядка выполнения команд можно выделить три типа алгоритмов:

линейные алгоритмы;
алгоритмы с ветвлениями;
алгоритмы с повторениями.

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

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

Окончание >>>