программирование_занятие_2

название: Основные алгоритмические конструкции.

изучается:

Макрокоманда (несколько команд оформляется как одна).

Линейный алгоритм.

Неполное ветвление, условие.

Цикл:

циклы ДО и ПОКА,

базовый материал:

Алгоритм, основные свойства алгоритма. (из 1 урока)

Оформление программ: блок-схемы, языки программирования. (из 1 урока)

Ввод-вывод информации, присваивание. (из 1 урока)

Основные алгоритмические структуры

Макрокоманды

- Надеюсь, слушатели хорошо знакомы с понятиями:

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

Прежде всего, обратим внимание на свойство алгоритма, которое называют «дискретность». Свойство отмечает, что алгоритм всегда разбивается на части (=этапы, =шаги). В возможных взаимоположениях этих частей мы будем разбираться.

Прежде чем переходить к алгоритмическим структурам, обратим внимание на действие, противоположное разбиению алгоритма на шаги (свойство дискретности). Часто встречается необходимость объединения нескольких шагов в одну группу, которую затем считают отдельным одним шагом.

При оформлении блок-схем, можно несколько разных действий написать внутри одного блока – прямоугольника – блока действий.

Задача: одной рукой поменять местами два яблока, лежащих в разных карманах (в один карман два яблока не помещаются).

Решение представлено в виде блок-схемы. Отдельные три шага заключены в один блок. В дальнейшем этот блок можем считать одной командой – командой обмена.

В языках программирования высокого уровня так же предусматривается возможность объявления нескольких команд одной составной. В языке pascal одной командой считаются все команды, заключенные между служебными словами begin и end, в языке с – заключенные в фигурные скобки. В языках, не обладающих возможностью использовать составные команды, (, dBASE), приходится использовать специальные служебные слова, замыкающие группы команд.

basic		pascal		c
if <условие> then … endif		begin ... end;		{ ... }

Линейный алгоритм

Изучение алгоритмических конструкций начнем с линейного алгоритма. В учебниках иногда используется термин «следование».

Алгоритм назовем линейным, если 1) выполняется каждый его шаг, и 2) только один раз.

Такого определения вполне достаточно. В некоторых учебниках используются слова «шаги выполняются последовательно, друг за другом», но эти слова означают наличие некоторого порядка. А порядков имеется два!

Одним из свойств алгоритма является, что его можно использовать двояко: либо исполнить, либо записать по определенным правилам. Таким образом первый порядок – порядок исполнения команд, второй – порядок написания. Эти порядки могут не совпадать.

На рисунке слева – случай, когда порядок написания и порядок исполнения совпадают, справа – эти порядки различны. Может показаться, что на рисунке справа алгоритм не линеен, так как команды выполняются не «друг за другом», а сначала вторая, потом первая. Но если определить линейный алгоритм как указано выше - Алгоритм линейный, если выполняется каждый его шаг, и только один раз – то эта проблема снимается.

Встречается ли практически случай, представленный на втором рисунке?

Да, встречается.

Первые программы школьники нашей страны писали на языке basic, многие версии которого носили однокомандный характер (в одной строке программы можно было написать только одну команду). Сами строки при этом нумеровались.

10 команда 1

20 команда 2

30 команда 3

40 команда 4

50 команда 5

60 команда 6

70 END

Нумеровать строки рекомендовалось через десяток, для того, чтобы при необходимости, можно было вставить пропущенную команду. Между строками с номерами 30 и 40, таким образом, можно вставить до 9 строчек-команд. Как быть, если требуется вставить большее количество команд?

Начинающие программисты, а иногда и профессионалы, вписывали команду перехода (GOTO) на строку с номером, находящуюся после конца программы (END), затем, начиная с этой строки, писали требуемые команды, в конце которых, снова командой перехода, выполняли возврат в основную программу. Подобное программирование даже получило название – «компьютерные спагетти».

(Представьте, что получиться, если применить этот прием несколько раз!)

10 команда 1

20 команда 2

30 команда 3

35 GOTO 100

40 команда 4

50 команда 5

60 команда 6

70 END

100 команда 1 из пропущенных между 3 и 4

110 команда 2 -+-

…

170 команда последняя из пропущенных между 3 и 4

180 GOTO 40

Обычно же, в современных языках программирования реализуется ЛЕКСИКОГРАФИЧЕСКИЙ порядок, то есть порядок написания и исполнения команд совпадают.

Строки с командами исполняются «сверху вниз», в каждой строке может находиться несколько команд, в этом случае они исполняются слева направо.

Конструкция следования (линейный алгоритм) является наиболее простой, и некоторые алгоритмы имеют именно такую структуру.

Линеен алгоритм обмена, алгоритмы деления угла или отрезка пополам и многие другие.

Ветвление неполное

Вернемся к нашему определению линейного алгоритма и попытаемся определить остальные алгоритмические структуры.

Алгоритм назовем линейным, если

1) выполняется каждый его шаг, и

2) только один раз.

Для начала, откажемся от требования 1), обязательности выполнения каждого шага алгоритма.

Имеем алгоритм, в котором некоторые шаги могут не выполняться.

Получившаяся структура алгоритма называется. НЕПОЛНОЕ ВЕТВЛЕНИЕ

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

Если условие истинно – шаг алгоритма выполняется, иначе – нет.

Всевозможные условия являются объектом работы, то есть ДАННЫМИ, которые могут иметь либо значение истина, либо значение ложь. Образуются эти значения при сравнении двух переменных или выражений одного типа.

A=B

A<>B

X<>5

A>5

B<3

C<=A+B

Значения этих выражений «истинно» (true) или «ложно» (false) зависит от значений используемых переменных.

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

На языке блок-схем блок ветвления обозначается ромбом, имеет один вход и два выхода. Однако любой алгоритм должен обладать свойством результативности, то есть у него должен быть конец и только один. Обе ветви, для достижения конца соединяются, место соединения называется УЗЕЛ и на блок-схеме отмечается кружком.

Наличие двух выходов так же представляет собой проблему. Выходы должны быть разными. Поэтому они маркируются словами «да» и «нет» или знаками «+» и «-». Согласно первому выходу алгоритм продолжаем при истинности условия, которое вписывается в ромб, иначе – продолжаем согласно второму выходу. Лентяи просто ставят около выхода «да» точку. Этого достаточно для однозначного определения дальнейших шагов алгоритма.

НЕПОЛНОЕ ВЕТВЛЕНИЕ

Ветвления очень часто встречаются в различных алгоритмах:

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

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

Цикл

Ветвление - один из случаев нарушения линейности алгоритма.

Как уже отмечалось, на блок-схеме ветвление обозначается ромбом, внутри которого указывается условие. Блок ветвления имеет один вход и два выхода. Обе ветви, для достижения конца соединяются в узле.

Однако ветви могут соединиться и перед блоком условия!

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

(Линейным называется алгоритм, каждый шаг которого обязательно выполняется и ТОЛЬКО ОДИН РАЗ. Нарушено второе условие.)

Такая организация алгоритма называется ЦИКЛ.

(н)

│

(*)-<──────────┐

│ │

/ \ │

/ \ │

нет / \ да │

┌──-<условие>───┐ │

│ \ / │ │

│ \ / │ │

│ \ / ┌───┴───┐ │

│ │ ШАГ │ │

│ │ ТЕЛО │ │

│ └───┬───┘ │

└───────┐ └─────┘

(к)

Шаги, которые могут выполняться несколько раз подряд образуют ТЕЛО цикла. Выполнять или нет тело еще раз решает УСЛОВИЕ цикла.

Итак, любой цикл имеет ТЕЛО и УСЛОВИЕ ВЫХОДА.

Снова вспоминаем свойство алгоритма, что его можно исполнить и его можно записать.

Две составных части цикла – тело и условие – можно записать по разному: либо сначала условие, потом тело, либо сначала тело, потом условие.

В первом случае цикл называется циклом типа «пока», во втором – циклом типа «до».

Так выглядит оформление цикла с предусловием (цикла «пока») в разных языках программирования.

basic		pascal		C
10 if < усл.> then 40 20 <тело цикла "ПОКА"> 30 goto 10 40 while <усл.> <тело цикла "ПОКА"> wend		while <усл.> do begin <тело цикла "ПОКА"> end;		while <усл.> { <тело цикла "ПОКА"> }

А так выглядит оформление цикла с постусловием (цикла «до») в языках программирования.

basic		pascal		C
10 rem начало цикла 20 <тело цикла «ДО»> 50 if <условие> then 10		repeat <тело цикла "ДО"> until <усл.>;		do {<тело цикла "ДО">} while <усл.>

КЛАССИФИКАЦИЯ ЦИКЛОВ ПО ВЗАИМНОМУ ПОЛОЖЕНИЮ ЧАСТЕЙ

(н) Цикл "ПОКА" (н)

┌───┤ ( сначала ├───┐

│ / \ - "условие" ┌──┴─┐ │

│ <усл>─┐ потом │тело│ │

│ +\ / │ "тело" ) └──┬─┘ │

│┌──┴─┐ │ / \ │

││тело│ │ Цикл "ДО" <усл>─┘

│└──┬─┘ │ ( сначала \ /-

└───┘ │ "тело" │+

┌───┘ потом (к)

(к) "условие")

Основным различием циклов ДО и ПОКА является то, что в цикле ДО тело цикла один раз выполняется обязательно, а в цикле ПОКА возможна ситуация, когда тело цикла не выполнится ни разу.

Изменив условие, для цикла ПОКА можно добиться выполнения цикла один (первый) раз, цикл будет работать как и цикл ДО.

Запретить выполнение первого раза тела цикла типа ДО невозможно.

Так как из цикла ПОКА можно получить цикл ДО, цикл ПОКА является более универсальным.

Попытки определить тип цикла по семантическому значению слов «до» и «пока» в русском языке обречены на неудачу.

Фразы:

Тело цикла выполняется до тех пор ПОКА позволяет условие

и

Тело цикла выполняется ДО тех пор пока позволяет условие

Различаются только акцентом.

Пример организации ввода чисел: ЭВМ будет запрашивать числа, пока не получит число 0.

a:=1;

while a<>0 do

begin

write('введи число '); readln(a)

end;

repeat

write('введи число '); readln(a)

until a=0;

Как видим, задача может быть решена как использованием цикла «пока», так и использованием цикла «до».

Довольно часто выбор типа цикла несущественен.

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

Например, если вы собираетесь удалить пробелы, стоящие в начале строки, то, скорее всего, выберете цикл с предусловием, потому что надо сначала убедиться, что пробел имеется, и только затем его удалять (глупо поступать наоборот - сначала удалять, а потом проверять, стоило ли это делать). Зато ввод текста до точки трудно построить иначе как с постусловием, поскольку сначала требуется ввести очередной символ и только потом сравнивать его с точкой.

Для цикла ПОКА принято организовывать выход при значении условия "ложно", а для цикла ДО принято организовывать выход при значении условия "истина". Это следует знать, если вы работаете, скажем, на паскале.

Однако, Вы можете разработать свой язык программирования, где все будет наоборот. Требование придерживаться этих условий при работе с блок-схемами мне кажется неправильным.

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

Заключение

Что мы узнали на этом уроке? В определении линейного алгоритма имеются всего два требования.

Алгоритм назовем линейным, если

1) выполняется каждый его шаг, и

2) только один раз.

Нарушение первого из них приводит к ветвлениям, второго – к циклам.

Других случаев расположения шагов алгоритмов нет.

Вывод: Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Логическая структура любого алгоритма может быть представлена комбинацией (суперпозицией) трех базовых структур: следования, ветвления, цикла.

Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.

В качестве самостоятельной работы составьте свои алгоритмы, в которых имеются линейность, ветвления, циклы.

По окончании нашего урока, вы должны знать ответы на вопросы:

* Какой алгоритм называется линейным?

* Какой алгоритм называется алгоритмом с ветвлением?

* Зачем в блок-схемах нужен блок - узел?

* Какой алгоритм называется алгоритмом с циклом?

* Какие два типа циклов различают?

* Какой тип циклов более универсальный и почему?

* Как оформляются циклы ДО и ПОКА на языке Паскаль?