|
|
|
§ 3.4. Типы алгоритмов Алгоритмы с повторениямиНа практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз, пока соблюдается некоторое заранее установленное условие. Форма организации действий, при которой выполнение одной и той же последовательности действий повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением). Алгоритм, содержащий циклы, называется циклическим алгоритмом или алгоритмом с повторениями. Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием. Следует разрабатывать алгоритмы, не допускающие таких ситуаций. Рассмотрим пример из математики. Натуральное число называют простым, если оно имеет только два делителя: единицу и само это число1. 1 Напомним, что число 1 не относят ни к составным (имеющим более двух делителей), ни к простым числам. 2, 3, 5, 7 — простые числа; 4, 6, 8 — нет. В III веке до нашей эры греческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых чисел, меньших заданного числа n: 1) выписать все натуральные числа от 1 до n; 2) вычеркнуть 1; 3) подчеркнуть наименьшее из неотмеченных чисел; 4) вычеркнуть все числа, кратные подчеркнутому на предыдущем шаге; 5) если в списке имеются неотмеченные числа, то перейти к шагу 3, в противном случае все подчеркнутые числа — простые. Это циклический алгоритм. При его выполнении повторение шагов 3-5 происходит, пока в исходном списке остаются неотмеченные числа. Вот так выглядит блок-схема действий школьника, которому перед вечерней прогулкой следует выполнить домашнее задание по математике:
В зависимости от порядка выполнения команд можно выделить три типа алгоритмов:
Алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным. Форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий, называется ветвлением. Форма организации действий, при которой выполнение одной и той же последовательности действий повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением).
|
|
|