Урок 9 (общий-С/С++, VB). Понятие об алгоритмах. Псевдокод. Блок-схемы.

Эпиграф.

Ученые проводят опыт. Под потолком подвешен вне досягаемости банан и бутылка водки. Испытуемые - шимпанзе и алкоголик. В углу лежит ящик. Обезьяна пару раз подпрыгивает, останавливается, потом идет к ящику, ставит его под банан, достает и ест. Пьяница прыгает дальше. Ученые сжалились и стали подсказывать: "Да ты погоди, постой, подумай!.." На что получили ответ: "Что тут думать! Прыгать надо!!!"

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

Для программиста алгоритм всегда был важнее языка, т.к. он показывает как сделать, а язык - как это написать. Непонятно в чем разница? Разберемся.

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

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

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

Очень часто начинающие программисты ахают и открывают рты, когда маститые мэтры бросают через плечо: "Да какая разница на чем писать!" Понятно, эту фразу очень трудно понять, когда ты еще путаешься в элементарных синтаксических правилах одного языка, а остальные ощущаются как какие-то неподъемные громады в тумане: нечто неясное и аморфное... И очень неясно зачем писать какие-то алгоритмы непонятные... Код надо писать, код! А если неправильно написали, мы чего-нибудь исправим, и опять запустим, и так пока не заработает.

О! В таком виде работа очень напоминает приведенный эпиграф. Прямо один в один!

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

Итак, алгоритм - это последовательность операций (в обычной жизни - действий). Что за чем мы должны сделать, чтобы получить какой-то результат. На самом деле мы уже знакомились с составлением алгоритмов, во всяком случае те, кто читал Вводную лекцию по курсу программирования для начинающих. Напомню - посмотрите задание 1. То, что в нем предлагалось вам сделать, и было написанием алгоритма.

Мне тут подсказывает Сашок, что можно привести хороший пример для сравнения языка с алгоритмом: сделать то же описание похода на кухню по-русски, по-английски и, скажем, по-японски. Алгоритм один и тот же, языки - разные. Выучил новый язык - можешь описать и на нем. Но если не в силах просто членораздельно описать, как пройти на кухню, тогда за программирование лучше и не браться. Даже на самом простом языке.

Каким должен быть алгоритм?

* Правильным или результативным. То есть, он должен обеспечивать такую последовательность действий, которая позволит вам достичь результата. Если вы, описывая алгоритм утреннего вставания-одевания, опустите операцию "взять одежду в руки", удастся вам одеться? Сомневаюсь, если только вы не фея. Следовательно, такой алгоритм будет неверным без одной-единственной операции.
* Однозначным. Он должен быть написан так, чтобы не было возможности не единственным образом толковать правила и порядок выполнения действий.
* Эффективным. То есть, он должен достигать результата максимально удобным и коротким способом. Например, если взять тот же алгоритм "как дойти до кухни из комнаты", то можно сделать это не одним способом. Можно (коротко говоря) выйти из комнаты в коридор, а из него попасть в кухню. А можно вылезти в окно (если вы живете на первом этаже, а если не на первом, то возможностей масса: вылезти по веревке, спуститься, как Тарзан, по балконам соседей, по пожарной лестнице, или придумать что-нибудь покруче в стиле американских экшенов), пробежать/пройти по земле до подъезда, подняться по лестнице или лифтом, открыть свою дверь ключом или позвонить, чтобы кто-то ее открыл и войти на кухню. Итак, цель достигнута в обоих случаях. А про эффективность, думаю, все ясно А про то, что программа, сделанная по неэффективному алгоритму работает во много раз дольше?


Как записать алгоритм.

записывать алгоритмы можно любым удобным способом, лишь бы понятно было.

* Алгоритмический язык. Хорошо, мы уже выяснили, что алгоритм от языка не зависит. А как же его можно записать? А как мы описывали алгоритм, когда делали задание 1? Правильно, на своем собственном языке. Мы просто описывали - что за чем нужно делать. Обычными словами разговорной речи. Но, наверно, вы заметили, что описания, которые у нас получились - это весьма сдержанный, усеченный вариант речи в котором отсутствуют ненужные красивости и, главное, неоднозначности. Получаем так называемый псевдокод. Это язык описания алгоритмов, искусственный, неформальный (то есть, пишешь так, как тебе удобно, только чтобы другие понимали, если ты работаешь не один).
* Блок-схема. Алгоритм может быть записан графически. Для этого и служит блок-схема. Для изображения операций в ней используются специальные символы. Познакомимся с основными из них.

Начало или конец. Внутри фигуры пишут начало (или begin - кому как нравится) или конец (end) соответственно. Если вы рисуете не всю схему, а только кусок ее, который нужно расписать подробнее, можете ограничиться маленьким кружочком.
В прямоугольнике находится операция. Можно написать ее словами (например: умножить х на у), а можно кусочком кода с оператором (х*у)
Если вы хотите указать, что одно из действий сложное, и его хорошо бы разбить на ряд более простых, и вы выносите его как подзадачу в отдельное место - обозначьте такое действие так.
Внутри ромба пишутся проверяемые условия (урок С6, урок VB 8). Обычно после проверки условий последовательность операторов перестает быть конструкцией следования и становится конструкцией выбора либо повторения. (следующие уроки будут посвящены именно этим конструкциям)
Так обозначается введение входных параметров, а также выходных. Допустим, вы вынесли отдельно блок операторов и теперь хотите его расшифровать. Но для его работы нужно ввести определенные данные. Их вы напишете справа от этой скобки. То же относится к данным, которые вам нужно получить по окончании работы программы или части кода.

Вообще-то, есть еще специальные символы блок-схем, но, во-первых, их можно найти в литературе, а во-вторых, для наших учебных целей приведенных выше вполне достаточно.

Последовательность операторов изображается стрелочками, соединяющими блоки. Например вот так:



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

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

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

название процедуры описание этой процедуры
CmdSound_Click При щелчке мышью на кнопке cmdSound вызывается звуковой сигнал
CmdEnd_Click При щелчке мышью на кнопке cmdEnd приложение заканчивает работу.

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

Приложение от Dusk-а.

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

* Поставь машину на ручной тормоз
* Достань домкрат
* Сними колпак
* Ослабь болты на колесе
* Подними машину на домкрате
* Выверни болты
* Сними колесо
* Достань запасное колесо
* Одень запасное колесо на место
* Вверни болты
* Опусти домкрат
* Затяни болты
* Одень колпак
* Положи домкрат и спустившееся колесо в багажник


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

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



Задание.

* Написать алгоритмы и блок-схемы программ, которые вы делали в курсе раньше. Для VB - сделать таблицу процедур.
* Попробуйте составить блок-схему программы "Как перейти дорогу".