Командой повторения, или циклом, называется такая форма организации действий в алгоритме, при которой выполнение одной и той же последовательности команд повторяется до тех пор, пока истинно некоторое логическое выражение.
Для организации цикла необходимо выполнить следующие действия:
· перед началом цикла задать начальное значение параметров (переменных, используемых в логическом выражении, отвечающем за продолжение или завершение цикла);
· внутри цикла изменять переменную (или переменные), которая сменит значение логического выражения, за счет которого продолжается цикл, на противоположное (для того чтобы цикл в определенный момент завершился);
· вычислять логическое выражение – проверять условие продолжения или окончания цикла;
· выполнять операторы внутри цикла;
управлять циклом, т.е. переходить к его началу, если он не закончен, или выходить из цикла в противоположном случае.
Различают циклы с известным числом повторений (цикл с параметром) и итерационные (с пред- и пост- условием).
Опишем схематично, как выполняется каждый из циклов.
Цикл с предусловием:
а) вычисляет значение логического выражения;
б) если значение логического выражения «истина», переход к следующему пункту, иначе к п. д)
в) выполняется тело цикла;
г) переход к п.а);
д) конец цикла.
Цикл с постусловием:
а) выполняется тело цикла;
б) вычисляется значение логического выражения;
в) если значение логического выражения «лож», переход к п. а), иначе к следующему пункту;
г) конец цикла.
Замечание. Таким образом, цикл с послесловием организован, в организован, в частности, в алгоритмических языках Pascal и QBasic. В языке С переход к повторению вычислений, как и в цикле с предусловием, осуществляется в случае истинности логического выражения.
Цикл с параметром:
а) вычисляются значения выражений, определяющие начальное значение параметра цикла;
б) параметру цикла присваивается начальное значение;
в) параметр цикла сравнивается с конечным значением;
г) если параметр цикла превосходит (при положительном шаге) конечное значение параметра цикла (или, наоборот, меньше конечного значение параметра цикла при отрицательном шаге), переход к п. з), иначе к следующему пункту;
д) выполняется тело цикла;
е) параметр цикла автоматически увеличивается на значение шага;
ж) переход к п. в.
з) конец цикла
Запись цикла на языках программирования
| QBasic | Pascal | C | |
| С предусловием | WHILE ЛВ операторы WEND | WHILE ЛВ DO оператор | while (ЛВ) оператор; |
| С постусловием | LООР операторы UNTIL ЛВ | REPEAT операторы UNTIL ЛВ; | do оператор while (ЛВ); |
| С параметром | FOR ПЦ= НЗ ТО КЗ STEР Ш операторы NEXT ПЦ | FOR ПЦ := НЗ TO (DOWNTO) КЗ DO оператор; | For (ПЦ = НЗ; НЗ<=КЗ; ПЦ = ПЦ+Ш) оператор; |
Циклы с предусловием и постусловием в большинстве случаев (за исключением отдельных реализаций алгоритмических языков) являются более универсальными по сравнению с циклом с параметром, поскольку в последнем требуется заранее указать число повторений, в то время как в первых двух это не требуется. Цикл с параметром в любом случае может быть преобразован к циклу с пред- или постусловием. Обратное верно не всегда.
Замечание. В языке С цикл for на самом деле является универсальным циклом с предусловием. В частности, из него можно сделать и описанную форму цикла с параметром.
Примеры использования основных алгоритмических структур и их суперпозиций для составления алгоритмов, а по ним – программ приводятся в многочисленной литературе по программированию, по этому не будим здесь останавливаться.
Наконец, рассмотрим вопрос анализа алгоритмов.
Одну и ту же задачу могут решать много алгоритмов. Эффективность работы каждого из них описывается разнообразными характеристиками. Прежде чем анализировать эффективность алгоритма, нужно доказать, что данный алгоритм правильно решает задачу, то можно посмотреть, насколько это решение эффективно.
При анализе алгоритма определяется количество «времени», необходимое для его выполнения. Это не реальное число секунд или других промежутков времени, а приблизительное число операций, выполняемых алгоритмом. Число операций и измеряет относительное время выполнения алгоритма. Таким образом, иногда «временем» называют вычислительную сложность алгоритма. Фактическое количество секунд, требуемое для выполнения алгоритма на компьютере, непригодно для анализа, т.к. обычно интересует только относительная эффективность алгоритма, решающего конкретную задачу. Действительно, время, требуемое на решение задачи,- не очень хороший способ измерять эффективность алгоритма , потому что алгоритм не становится лучше, если его исполнять на более медленном.
На самом деле фактическое количество операций алгоритма на тех или иных входных данных не представляет большого интереса и не очень много сообщает об алгоритме. Реально определяется зависимость числа операций конкретного алгоритма на тех или иных входных данных. Можно сравнить два алгоритма по скорости роста числа операций. Именно скорость роста играет ключевую роль, поскольку при небольшом размере входных данных алгоритм А может требовать меньшего количества операций, чем алгоритм В, но при росте объема входных данных ситуация может поменяться на противоположную.
Два самых больших класса алгоритмов – это алгоритмы с повторением и рекурсивные алгоритмы. В основе алгоритмов с повторением лежат циклы и условные выражения; для анализа алгоритмов требуется оценить число операций, выполняемых внутри цикла, и число итераций цикла. Рекурсивные алгоритмы разбивают большую задачу на фрагменты и применяются к каждому фрагменту по отдельности. Такие алгоритмы называются иногда «разделяй и властвуй», и их использование может оказаться очень эффективным. В процесс решения большой задачи путем деления ее на меньшие создаются небольшие, простые т понятные алгоритмы. Анализ рекурсивного алгоритма требует подсчета количества операций, необходимых для разбиения задачи на части, выполнения алгоритма на каждой из частей и объединения отдельных результатов для решения задачи в целом. Объединяя эту информацию и информацию о числе частей и их размере, можно вывести рекуррентное соотношение для сложности алгоритма. Полученному рекуррентному соотношению можно придать замкнутый вид, затем сравнивать результат с другими выражениями.
Список литературы
1. Ахо, Альфред Структура данных и алгоритмы [Текст]. - М.: Издательский дом «Вильямс», 2000. - 384 с.
2. Кнут, Д. Искусство программирования на ЭВМ [Текст]: Том 3. - М:. Мир, 1978. - 356 с.
3. Вирт, Н. Алгоритмы и структуры данных [Текст].- М:. Мир, 1989. - 360 с.
4. Успенский В. Теория алгоритмов: основные открытия и приложения [Текст]. - М.: Наука, 1987. - 288 с.
5. Кормен, Т. Алгоритмы: построение и анализ [Текст]/ Т. Кормен, Ч. Лейзерсон, Р. Ривест - М.: МЦНМО, 2002. М.: МЦНМО, 2002.