Информатика. Курс лекций. Громов Ю.Ю - 90 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

В нашем псевдокоде общий синтаксис цикла этого типа имеет следующий вид:
repeat {действие} until (условие)
Рис. 4.8. Блок-схема цикла
while-do
Рис. 4.9. Блок-схема цикла
repeat-until
Рассмотрим конкретный пример:
repeat {взять монету из кармана} until (в кармане нет монет)
Когда выполнение алгоритма доходит до этой инструкции, подразумевается, что в кармане есть хотя бы одна монета. Это
предположение не является обязательным при использовании следующей инструкции:
while (в кармане есть монета) do {взять монету из кармана}
Придерживаясь терминологии нашего псевдокода, будем называть эти структуры оператором цикла с условием про-
должения и оператором цикла с условием завершения. Иногда оператор цикла while называют априорным циклом (pretest
loop), или циклом с предусловием, поскольку условие завершения проверяется до выполнения тела цикла, а оператор цикла
repeat называется апостериорным циклом (posttest loop), или циклом с постусловием, поскольку условие завершения про-
веряется после выполнения цикла.
Алгоритм сортировки методом вставки. В качестве дополнительного примера итеративной структуры рассмотрим
задачу сортировки списка имен в алфавитном порядке. Прежде чем приступить к обсуждению, следует установить некото-
рые ограничения, которые необходимо будет учитывать. Попросту говоря, наша задача – отсортировать список "внутри его
самого". Другими словами, мы хотим отсортировать список, просто переставляя его элементы, а не перемещая весь список в
другое место. Это аналогично сортировке списка, элементы которого записаны на отдельных карточках, разложенных на
переполненном рабочем столе. На столе достаточно места для всех карточек, однако запрещается отодвигать другие нахо-
дящиеся на столе материалы, чтобы освободить дополнительное пространство. Подобное ограничение типично для компью-
терных приложений, но не потому, что рабочее пространство в машине обязательно переполнено, как наш рабочий стол, а
потому, что мы стремимся использовать доступный объем памяти самым эффективным образом. Попробуем сделать первый
шаг в поисках решения задачи. Рассмотрим, как можно было бы отсортировать карточки с именами, расположенные на ра-
бочем столе. Пусть исходный список имен выглядит следующим образом:
Fred
Alice
David
Bill
Carol
Один из подходов к сортировке этого списка заключается в следующем. Обратите внимание, что подсписок, состоящий
из единственного верхнего имени Fred, уже отсортирован, а подсписок из двух верхних имен, Fred и Alice, – еще нет. Поэто-
му подымем карточку с именем Alice, поместим карточку с именем Fred вниз, туда, где раньше была карточка с именем
Alice, а затем положим карточку с именем Alice в самое верхнее положение, как показано в первой строке на рис. 4.10. Те-
перь список будет иметь такой вид:
Alice
Fred
David
Bill
Carol

Страницы