Алгоритмы и исполнители (стр. 4 )

int x, y, xx, yy;

Разведка

{

ВУгол;

xx = 0;

пока ( справа_свободно )

{

ПроверитьРяд;

направо; вперед(1); налево;

xx = xx + 1;

}

ПроверитьРяд;

НаБазу;

}

Теперь надо написать окончательные варианты процедур ПроверитьРяд и ПроверитьКлетку. В процедуре ПроверитьРяд надо (с помощью переменной yy) отслеживать, сколько шагов Робот сделал на север. Поскольку Робот проверяет клетки на обратном ходу (чтобы не ходить по цветам), мы увеличиваем счетчик yy, когда Робот идет на север, а затем уменьшаем его при каждом шаге назад так, чтобы при вызове процедуры ПроверитьКлетку координаты xx и yy были правильными.

ПроверитьРяд

{

yy = 0;

пока ( впереди_свободно )

{

вперед ( 1 );

yy = yy + 1;

}

ПроверитьКлетку;

пока ( сзади_свободно )

{

назад ( 1 );

yy = yy - 1;

ПроверитьКлетку;

}

}

В процедуре ПроверитьКлетку надо запоминать положение Базы, записав координаты Робота xx и yy в глобальные переменные x и y, если она найдена.

ПроверитьКлетку

{

если ( грядка ) посади;

если ( база )

{

x = xx; y = yy; /* запомнить положение Базы */

}

}

10.  Исполнитель Черепаха

2  Как работает Черепаха?

Исполнитель Черепаха умеет делать рисунки и чертить на плоскости. Поскольку ей нужны все ее лапы, чтобы ходить, она держит перо в зубах.

Среда Черепахи – плоскость с системой координат. Система координат необходима для того, чтобы однозначно определять место Черепахи на плоскости. Черепаха редко использует прямоугольную систему координат, она поступает так же, как и человек – может развернуться в любую сторону и идти вперед или назад. Такая система координат (“вправо-влево-вперед-назад”) называется естественной системой координат.

2  Какие команды понимает Черепаха?

СКИ Черепахи:

покажись; Черепаха появляется на экране

скройся; Черепаха исчезает

опусти_перо; Черепаха оставляет за собой след

подними_перо; Черепаха перемещается без следа

в_точку ( x, y ); переместиться в точку с координатами (x, y)

вперед ( n ); переместиться вперед на n шагов

назад ( n ); переместиться вперед на n шагов

влево ( a ); развернуться влево на угол a градусов

вправо ( a ); развернуться вправо на угол a градусов

Как видно из этого списка команд, для Черепахи важно не только ее начальное положение на плоскости, но и ее направление. Мы будем считать, что в исходном положении Черепаха смотрит вверх (“на север”).

2  Как управлять Черепахой?

Сначала выполним простейшую задачу для Черепахи — нарисуем квадрат со стороной 40 шагов. Черепаху будем обозначать черным треугольником. Как вы знаете, все углы квадрата равны 90 градусов, поэтому программа выглядит так:

2  Как раскрасить рисунок?

Вы заметили, что Черепаха рисует все время черной линией. Используя специальные команды, рисунок можно раскрасить.

¨  Для изменения цвета линии используется команда

цвет ( n ); /* установить цвет линии n */

Цвет линии может иметь значения от 0 до 15, таким образом можно использовать всего 16 цветов:

Черепаха умеет также закрашивать замкнутую область заданным цветом.

¨  Для закрашивания используется команда

закрась ( n );

где n — цвет краски.

При этом необходимо выполнение следующих условий:

1.  Область должна быть замкнуты, то есть в границе не может быть разрывов, иначе краска "вытекает".

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

3.  Черепаха не должна находиться в точке, которая имеет тот же цвет, что и граница.

Ниже показана программа, которая рисует желтый квадрат (номер цвета 14) с границей синего цвета (цвет 1).

Если вы не использовали команду цвет, все линии рисуются черным цветом. Чтобы в самом начале залить экран каким-нибудь фоном, надо также использовать команду закрась.

2  Окружности

Черепаха умеет сама рисовать окружности. Для этого надо перевести ее в центр окружности и применить специальную команду.

¨  Для рисования окружности, центр которой находится в том месте, где стоит Черепаха, используют команду

окружность ( R );

где R - радиус окружности

Цвет окружности определяется установленным цветом линий (то есть последней командой цвет). Учтите, что Черепаха рисует окружность только тогда, когда ее перо опущено.

4  Задачи

2  Циклы

4  Как циклы сокращают программу

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

вперед ( 40 );

вправо ( 90 );

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

В данном случае эти команды надо повторить только 4 раза и можно легко 4 раза написать одинаковые команды. Но представьте, что надо сделать одинаковые операции 100 или 200 раз! В программировании в таких случаях используется специальная команда (оператор), которая говорит исполнителю, что какую-то часть программы надо сделать несколько раз.

¨  Цикл — это многократное исполнение последовательности команд

Следующая программа рисует квадрат с использованием оператора цикла:

Квадрат

{

покажись;

опусти_перо;

}

4  Задачи

2  Вложенные циклы

Рассмотрим более сложную задачу, когда требуется нарисовать цепочку из пяти одинаковых квадратов, разделенных интервалом в 10 шагов:

Здесь явно напрашивается использование циклов, поскольку мы видим одинаковые элементы в рисунке, и хочется сказать исполнителю что-то вроде "Сделай 5 раз две операции:

нарисуй квадрат и затем … переместись к левому нижнему углу следующего".

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

¨  Вложенный цикл — это цикл, расположенный внутри другого цикла

Решение задачи выглядит так:

ПятьКвадратов

{

покажись;

/* рисуем квадрат */

/* переходим к следующему */

}

4  Задачи

2  Процедуры

4  Зачем нужны процедуры?

Иногда в задании явно есть одинаковые операции, но применить цикл не удается. Рассмотрим рисунок из трех равносторонних треугольников, сторона которых равна 40 пикселей. С одной стороны, все треугольники одинаковые, с другой — они расположены так, что нельзя использовать один цикл для всех трех фигур.

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

Программа

{

влево ( 30 );

опусти_перо;

повтори ( 3 )

{

вперед ( 40 );

вправо ( 120 );

}

вправо ( 30 );

подними_перо;

вперед ( 10 );

опусти_перо;

закрась ( 14 );

подними_перо;

назад ( 10 );

}

Следующий важный шаг: мы вводим в СКИ новую команду Треуг, которая включает все эти команды. Основная программа принимает такой вид:

Программа

{

Тр;

}

Однако если мы оставим ее в таком виде, то при запуске получим сообщение «Не понимаю, что такое 'Треуг'». И это правильно, потому что команды Треуг нет в СКИ исполнителя. Значит, надо «объяснить» Черепахе, что такое Треуг. Для этого после основной программы включаем такой текст (расшифровку команды Треуг)

Треуг

{

влево ( 30 );

опусти_перо;

повтори ( 3 )

{

вперед ( 40 );

вправо ( 120 );

}

вправо ( 30 );

подними_перо;

вперед ( 10 );

опусти_перо;

закрась ( 14 );

подними_перо;

назад ( 10 );

}

Запустим программу и убедимся, что она работает по-прежнему: рисует один треугольник с заливкой. Однако теперь в СКИ Черепахи добавлена новая команда, и мы можем ее использовать несколько раз. Такая команда называется процедурой.

Сначала рисуем первый треугольник, затем переводим исполнителя в вершину второго, и снова применяем команду Треуг, и т. д. Вот что получается окончательно для фигуры из трех треугольников:

Программа

{

покажись;

опусти_перо;

Треуг;

вправо ( 90 );

вперед ( 40 );

влево ( 90 );

Треуг;

влево ( 120 );

Треуг;

}

Треуг

{

влево ( 30 );

опусти_перо;

повтори ( 3 )

{

вперед ( 40 );

вправо ( 120 );

}

вправо ( 30 );

подними_перо;

вперед ( 10 );

опусти_перо;

закрась ( 14 );

подними_перо;

назад ( 10 );

}

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

¨  Процедуры (вспомогательные алгоритмы, подпрограммы) – это новые команды, которые мы добавляем к СКИ исполнителя. Чтобы исполнитель знал, что делать по этой команде, после основной программы надо дать расшифровку процедуры через уже известные исполнителю команды.

4  Как правильно применять процедуры?

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

2.  Основная программа всегда записывается первой. Она использует новые команды, расшифрованные после нее, при этом говорят, что процедура вызывается.

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

4.  В программе может быть несколько процедур. Одна процедура может вызывать другую процедуру.

4  Задачи

2  Процедуры с параметрами

Построим теперь с помощью Черепахи такую пирамидку, как на рисунке справа. Числа обозначают длины сторон соответствующих квадратов.

Сначала выделим общее всех трех фигур: все они — квадраты.

Затем выделим отличия: длина стороны и цвет заливки. Эти свойства называются параметрами.

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

влево ( 90 );

в_точку ( 30, 20 );

Теперь нам надо научиться вводить такие же команды – процедуры с параметрами.

Сначала составим программу, которая рисует один квадрат со стороной 40 и синей заливкой:

Программа

{

опусти_перо;

повтори ( 4 )

{

вперед ( 40 );

вправо ( 90 );

}

вправо ( 45 ); подними_перо;

вперед ( 10 ); опусти_перо;

закрась ( 1 ); подними_перо;

назад ( 10 );

влево ( 45 );

}

Теперь, так же, как и раньше, сделаем из этой программы новую команду (процедуру) Квадрат:

Программа

{

Квадрат;

}

Квадрат

{

опусти_перо;

повтори ( 4 )

{

вперед ( 40 );

вправо ( 90 );

}

вправо ( 45 ); подними_перо;

вперед ( 10 ); опусти_перо;

закрась ( 1 ); подними_перо;

назад ( 10 );

влево ( 45 );

}

Проблема состоит в том, что эта Черепаха рисует только квадраты со стороной 40 и синей заливкой. Теперь заменяем в процедуре все изменяемые величины (параметры) на буквенные обозначения: обозначим длину стороны через n и цвет через c.

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

Программа

{

Квадрат ( 40, 1 );

}

Квадрат ( int n, int c )

{

опусти_перо;

повтори ( 4 )

{

вперед ( n );

вправо ( 90 );

}

вправо ( 45 ); подними_перо;

вперед ( 10 ); опусти_перо;

закрась ( c ); подними_перо;

назад ( 10 );

влево ( 45 );

}

В заголовке процедуры перед каждым именем параметра стоит слово int (от английского integer) – это означает, что данный параметр – целое число. У нас длина стороны и цвет – целые числа, поэтому перед каждым стоит слово int.

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

Программа

{

покажись;

Квадрат ( 40, 1 );

вперед ( 40 );

Квадрат ( 30, 10 );

вперед ( 30 );

Квадрат ( 20, 12 );

}

Не забудьте после основной программы написать расшифровку команды Квадрат.

4  Как применять процедуры с параметрами?

1.  Процедуры с параметрами используются для выполнения похожих, но не одинаковых действий.

2.  Все изменяющиеся величины обозначаются символьными именами и называются параметрами процедуры.

3.  Имена параметров могут состоять из нескольких символов (букв или цифр), но начинаются обязательно с буквы.

4.  В заголовке процедуры в скобках через запятую перечисляются все параметры, для каждого из которых указывается его имя и тип данных:

int целое число

float число, которое может быть дробным

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

6.  При вызове процедуры в скобках указываются фактические параметры – конкретные значения параметров, которые надо использовать в данный момент. При вызове надо указать ровно столько фактических параметров, сколько формальных параметров указано в расшифровке.

7.  Во время выполнения процедуры фактические значения параметров подставляются вместо имен формальных параметров.

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

4  Задачи

2  Переменные

4  Зачем нужны переменные?

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

Начнем с более простой задачи, в которой все столбики имеют одинаковую высоту:

Несложно написать такую программу с использование цикла:

Программа

{

повтори ( 5 ) {

опусти_перо;

вперед ( 20 );

назад ( 20 );

подними_перо;

вправо ( 90 );

вперед ( 20 );

влево ( 90 );

}

}

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

Выберем имя ячейки n. Тогда вместо

вперед ( 20 );

назад ( 20 );

мы напишем

вперед ( n );

назад ( n );

Откуда компьютер возьмет значение n? Во-первых, сначала оно равно 20, поэтому перед циклом нужно написать

n = 20;

Кроме того, после каждого шага цикла (когда мы переходим к следующей линии), нужно увеличивать значение n на 10. На языке программирования это запишется в виде

n = n + 10;

Такая запись – это не уравнение (в отличие от математики), а команда исполнителю: «возьми значение n, добавь к нему 10 и запиши результат в ячейку n».

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

int n;

Слово int (от английского integer – целый) означает, что эта переменная предназначена только для хранения целых чисел. В нее можно записать числа 4 и 5, а вот 4,4 или 4,7 – нельзя. Вот полная программа:

Программа

{

int n;

n = 20;

повтори ( 5 ) {

опусти_перо;

вперед ( n );

назад ( n );

подними_перо;

вправо ( 90 );

вперед ( 20 );

влево ( 90 );

n = n + 10;

}

}

4  Задания

4  Что такое переменная?

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

¨  Переменная – это величина, которая имеет имя, тип и значение. Значение переменной может меняться во время выполнения программы. В компьютерах каждая переменная записана в свою ячейку памяти.

4  Объявление переменных

1.  В начале процедуры все используемые переменные необходимо объявлять, при этом компьютер выделяет под них место в памяти и запоминает имена переменных. Если переменная не объявлена, то возникает ошибка “НЕ ПОНИМАЮ”;

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

int целые числа (сокращение от англ. integer - целый)

float вещественные числа, которые могут иметь дробную часть

3.  Справа от типа указывают имена переменных этого типа, списком через запятую, например:

int a, b, n1, mmm;

float c2d, fg, qwerty;

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

5.  При объявлении мы может присвоить начальные значения некоторым переменным – после выделения памяти компьютер поместит эти числа в соответствующие ячейки, например:

int d, b = 4, cbn, a = 6;

float c, gh = 4.5, mmm = 7.89;

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

4  Правила работы с переменными

Для того, чтобы использовать переменные, надо уметь выполнять две основные операции

1.  Считывать из памяти и использовать значение переменной.

2.  Изменять значение переменной.

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

¨  Чтобы изменить значение переменной, надо использовать оператор присваивания: знак = показывает, что мы хотим изменить значение переменной, слева стоит имя переменной, которая изменяется, а справа - то, что мы хотим записать в эту ячейку, ее новое значение (при этом старое значение стирается!!!).

Например:

n = 5;

При этом в переменную n будет записано значение 5. Справа от знака = в операторе присваивания может стоять какое-то арифметическое выражение, в котором участвуют другие переменные и числа, например:

a = b + 5;

Этот оператор присваивания приказывает компьютеру выполнить такие действия:

1.  прочитать значение переменной b из памяти;

2.  вычислить значение выражения b+5;

3.  результат записать в ячейку a; при этом содержимое ячейки b не меняется, а старое содержимое ячейки a теряется безвозвратно.

В выражении справа можно использовать и имя той переменной, которой присваивается новое значение, в этом случае для вычислений используется старое значение этой переменной. Например:

n = n + 1;

Такой оператор присваивания приказывает компьютеру выполнить такие действия:

1.  прочитать старое значение переменной n из памяти;

2.  вычислить значение выражения n+1;

3.  результат записать в ту же ячейку n; при этом фактически содержимое ячейки n увеличивается на единицу.

Понятно, что такой оператор нельзя рассматривать с точки зрения математики как уравнение относительно n, в информатике он имеет совсем другой смысл.

4  Переменные и процедуры

Построим ряд из четырех квадратов со сторонами 10, 20, 20 и 40, расположенные так, как на рисунке.

Конечно, можно написать процедуру с параметром и вызвать ее 4 раза:

Программа

{

Квадрат ( 10 );

вправо ( 90 ); вперед ( 20 );

влево ( 90 );

Квадрат ( 20 );

вправо ( 90 ); вперед ( 30 );

влево ( 90 );

Квадрат ( 30 );

вправо ( 90 ); вперед ( 40 );

влево ( 90 );

Квадрат ( 40 );

}

Квадрат ( int a )

{

опусти_перо;

повтори ( 4 )

{

вперед ( a );

вправо ( 90 );

}

подними_перо;

}

Процедура Квадрат рисует квадрат, сторона которого задана в скобках, и возвращает Черепаху в исходное положение.

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

Здесь также можно применить цикл, но с некоторыми хитростями:

1)  длина стороны квадрата хранится в переменной, назовем ее n;

2)  в самом начале в переменную n записывается длина стороны первого квадрата (10);

3)  при вызове процедуры в качестве фактического параметра подставляется значение, взятое из переменой n;

4)  когда нарисован очередной квадрат, для перехода к следующему нужно сдвинуть Черепаху на расстояние n+10;

5)  при переходе к следующему квадрату значение переменной n увеличивается на 10.

Основная программа принимает такой вид:

Программа

{

int n = 10;

повтори ( 4 )

{

Квадрат ( n );

вправо ( 90 );

вперед ( n+10 );

влево ( 90 );

n = n + 10;

}

}

Не забудьте, что после основной программы надо привести также расшифровку процедуры Квадрат, такую же, как и раньше. Обратите внимание, что длина стороны по разному обозначается в основной программе (переменная n) и в процедуре (параметр a).

4  Цикл с параметром

Предыдущую задачу с четырьмя квадратами можно решить и иначе, с помощью цикла пока:

Программа

{

int n;

n = 10;

пока ( n<=40 )

{

Квадрат ( n );

вправо ( 90 );

вперед ( n+10 );

влево ( 90 );

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4 5