Псевдокод и блок-схемы

Дата создания: 2010-08-31 18:18:03
Последний раз редактировалось: 2012-02-08 04:53:26

Предварительные уроки:
1. Базовые концепции программирования. Перейти.

Дальнейшие уроки:
1. Установка Visual C++ 2008. Перейти.

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

Любой язык очень богат. С помощью языка, в нашем случае - русского, мы можем выразить любую мысль. Компьютеры гораздо глупее нас - людей. Они не терпят неоднозначностей, которыми так богаты человеческие языки. Кроме того, стоит отметить, что наш (и любой другой национальный) язык слишком избыточен с точки зрения компьютера. Мы можем донести информацию без искажения смысла, используя гораздо более скудные средства, например, отказавшись от междометий, вводных слов...

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

Главная задача программиста: переводить мысли с повседневного языка общения на язык компьютеров.

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

Псевдокод (pseudocode)

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

Что такое псевдокод? Это запись команд компьютеру обычным человеческим языком. В итоге программист получает промежуточную форму между повседневным языком и языком программирования.

Давайте разберём пример. Обычно, в качестве примеров выбирают ситуации, с практикой не имеющие ничего общего. Мы же рассмотрим совсем другой пример, который постоянно встречается на практике. Допустим у нас в стратегической игре есть карта размером 64 на 64 клетки. Для каждого персонажа игры нужно проверить, чтобы он не выходил за пределы карты. Координаты обозначим как x (по горизонтали), y (по вертикали). Очевидно, что координаты любого персонажа должны находиться в диапазоне [1 ... 64]. Предыдущее предложение - это мысль, которую нужно выразить на языке программирования.

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

Если координата x юнита меньше единицы, то сделать x равным единице.
Если координата y юнита меньше единицы, то сделать y равным единице.
Если координата x юнита больше 64, то сделать x равным 64.
Если координата y юнита больше 64, то сделать y равным 64.

Данные четыре предложения ограничивают движение персонажа. Это и есть псевдокод. Всю задачу мы смогли реализовать с помощью четырёх ветвлений с одной ветвью, в каждой из которых по одному оператору. Теперь этот псевдокод можно легко перевести на любой язык программирования. Давайте сделаем это для C++. Для этого в псевдокоде нужно заменить некоторые слова на английские эквиваленты, а математические действия нужно записать на математическом языке. Слово если на английском будет if (читается как иф):

if x < 1, x = 1.
if y < 1, y = 1.
if x > 64, x = 64.
if y > 64, y = 64.

Это тоже псевдокод, правда, уже более близкий к языкам программирования. В данном варианте псевдокода мы кое-что потеряли. Чьи координаты здесь проверяются? Чтобы обозначить, что x,y - координаты персонажей игры, мы запишем их через точку: unit.x, unit.y. Здесь видно, что x и y принадлежат юниту, а не зданию или дереву. Посмотрим на новый вариант:

if unit.x < 1, unit.x = 1.
if unit.y < 1, unit.y = 1.
if unit.x > 64, unit.x = 64.
if unit.y > 64, unit.y = 64.

Это всё ещё псевдокод, но здесь уже не содержится никакой избыточности - мы избавились от всех лишних слов. Данный вариант очень близок к языкам программирования. На C++ финальный код будет выглядеть вот так:

if (unit.x < 1) unit.x = 1;
if (unit.y < 1) unit.y = 1;
if (unit.x > 64) unit.x = 64;
if (unit.y > 64) unit.y = 64;

Этот код на С++ полностью рабочий! Кстати, очень похожий код мы будем использовать в арканоиде для контроля шара.

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

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

Что должен уметь делать программист?

Основная задача программиста состоит в следующем: перевод мыслей на язык, понятный компьютерам. Давайте ещё раз проследим, как это происходит.

Сначала мы захотели создать стратегию, далее мы начинаем обдумывать отдельные части будущей программы. Так, мы хотим, чтобы действие игры происходило на ограниченном поле размером 64*64 клетки. Отсюда вытекает следующее правило: любой персонаж игры должен находиться в пределах этого поля. У каждого персонажа есть координаты, которые задают его местоположение на карте. Чтобы точно удостовериться, что персонаж находится внутри поля, нужно проверить, не пересёк ли персонаж какую-либо из четырёх сторон поля. Теперь мы можем написать псевдокод (или сразу код, если достаточно хорошо знаем какой-нибудь язык программирования):

Если координата x юнита меньше единицы, то сделать x равным единице.
Если координата y юнита меньше единицы, то сделать y равным единице.
Если координата x юнита больше 64, то сделать x равным 64.
Если координата y юнита больше 64, то сделать y равным 64.

В итоге из одного предложения: "Любой персонаж игры должен находиться в пределах поля 64*64" - получилось четыре ветвления, каждое из которых будет состоять из одного оператора.

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

Блок-схемы (blockschemes)

Блок-схема - это графическое представление программы.

Блок-схемы строятся из отдельных блоков. При этом разные средства языков программирования на блок-схемах изображаются разными блоками. Например, для условия, на основе которого строится ветвление, изображается ромбом. Оператор, в котором происходит обработка информации, изображается прямоугольником. Давайте более подробно обсудим разные блоки.

Любая программа имеет начало и конец. На блок-схемах начало и конец программ обозначаются прямоугольниками со скруглёнными углами. Внутри этих прямоугольников пишутся слова: "Начало", "Конец".

В блок-схемах выделяют два вида операторов: операторы обработки данных и операторы ввода/вывода.

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

Как видим, блоки соединяются линиями со стрелочками. Стрелочками указывается последовательность выполнения блоков.

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

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

Если условие, записанное в ромбе, выполняется, то выполняется код по линии "да", а если не выполняется, то выполняется ветка "нет".

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

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

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

На этой же картинке я показал ещё пару новых вещей: троеточия и окружности.

Троеточие используется, чтобы показать, что в этом месте пропущено несколько операторов.

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

Если нужно разорвать код с несколькими ветвями, то окружности нумеруются.

Для обозначения циклов в блок-схемах используется следующий блок:

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

А теперь давайте посмотрим, как будет выглядеть блок-схема программы, псевдокод которой мы рассмотрели выше:

Я немного усовершенствовал программу. Здесь не просто проверяются координаты одного юнита, но координаты всех юнитов игры. Сами юниты хранятся в массиве units. Всего в игре двадцать юнитов. Чтобы проверить координаты всех юнитов, используется переменная current (current - текущий, читается как каррент). На картинке не показаны две вещи: как увеличивается переменная current и то, что проверяются x и y для текущего юнита.

Увеличение current должно происходить после всех ветвлений, но перед тем, как процессор вернётся к началу цикла. Я упустил этот момент, когда рисовал картинку (а сейчас исправлять неохота).

Заключение

Вот, в общем-то, и всё по псевдокоду и блок-схемам. Некоторые моменты я упустил, надеюсь, дополню позже.

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