Основная часть Алгоритмические основы информатики
жүктеу/скачать 169.43 Kb.
|
- Бұл бет үшін навигация:
- Циклическая конструкция
| Запись конструкций
Для разных исполнителей основные алгоритмические конструкции могут реализовываться различным образом. Следование не имеет специальной формы записи, а выражается в том, что входящие в него шаги записываются последовательно, а управление после выполнения очередного шага этой конструкции переходит к следующему. В текстовой форме записи — это просто последовательная запись пунктов, соответствующих шагам алгоритма. В блок-схемах — это последовательная запись блоков действия, соединенных стрелкой, направленной от предыдущего блока к следующему. На процедурном языке программирования данная конструкция выражается просто последовательной записью инструкций (операторов языка программирования). Ветвление в текстовой форме записи обычно выглядит так: если выполнено такое-то условие, то сделать то-то (или перейти на такой-то пункт алгоритма), в противном случае сделать то-то (или перейти на такой-то пункт алгоритма). В блок-схемах для реализации конструкции ветвление предназначен специальный блок условия, имеющий форму ромба. Данный блок имеет один вход и два выхода, соответствующих истинному или ложному значению логического выражения, записанного в этом блоке. В языках программирования данная конструкция реализуется через условный оператор (см. “Операторы языка программирования”). В машине Тьюринга ветвление реализуется через анализ текущего состояния машины и текущего символа на ленте машины Тьюринга (в зависимости от символа и от состояния машины на ленту записывается определенный символ и совершается переход в определенное состояние). Циклическая конструкция в явном виде во многих формах записи алгоритмов, к сожалению, отсутствует. На практике она реализуется с помощью проверки условия и управляющей конструкции перехода. В текстовой форме записи переход осуществляется на тот же самый пункт или пункт с меньшим номером. В блок-схемах переход с помощью стрелок осуществляется на часть схемы, по которой выполнение алгоритма уже ранее проходило. В языках программирования циклическая конструкция реализуется через различные операторы цикла: “с предусловием”, “с постусловием”, “с параметром”. На самом деле для реализации любой циклической конструкции хватило бы и одного вида оператора, например, с “предусловием”, различные операторы циклов вводятся в тот или иной язык программирования только для удобства программистов. Пример 3. Рассмотрим следующую задачу. Пусть на вход алгоритму подается последовательность символов “+”. Требуется заменить каждый второй символ этой последовательности на “–”. Для машины Тьюринга эта задача может быть переформулирована так. На ленте машины Тьюринга содержится последовательность символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Автомат в состоянии q1 обозревает крайний левый символ в указанной последовательности. Решение В состоянии q1 машина пропускает знак “+”, а при достижении конца последовательности — останавливается. В состоянии q2 машина знак “+” заменяет на знак “–”, при достижении конца последовательности она останавливается. “–” является символом алфавита этой машины, но он нам встретиться не может. В данной машине неявным образом заложена последовательная смена состояний q1 и q2, до тех пор пока входная последовательность не закончится, т.е. алгоритм реализуется с использованием цикла. Решение той же задачи с помощью блок-схемы можно записать так: жүктеу/скачать 169.43 Kb. Достарыңызбен бөлісу:
|