«ОСНОВЫ ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ ПРОБНОЕ УЧЕБНОЕ ПОСОБИЕ для средних учебных заведений В двух частях • ЧАСТЬ ВТОРАЯ Под редакцией А. П. Ершова и В. М. Монахова Рекомендовано Управлением информатики и ...»

ОСНОВЫ ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ

ТЕХНИКИ

ПРОБНОЕ УЧЕБНОЕ ПОСОБИЕ

для средних учебных заведений

В двух частях

•

ЧАСТЬ ВТОРАЯ

Под редакцией А. П. Ершова и В. М. Монахова Рекомендовано Управлением информатики и электронно-вычислительной техники Министерства просвещения СССР

МОСКВА

«ПРОСВЕЩЕНИЕ» 1986 ББК 73я72 0-75 А. П. ЕРШОВ, В. М. МОНАХОВ, А. А. КУЗНЕЦОВ, Я. Э. ГОЛЬЦ, М. П. ЛАПЧИК, А. С. ЛЕСНЕВСКИЙ, Ю. А. ПЕРВИН, Д. О. СМЕКАЛИН Основы информатики и вычислительной техники: Проб.

0-75 учеб. пособие для сред. учеб. заведений. В 2 ч. Ч. 2/ А. П. Ершов, В. М. Монахов, А. А. Кузнецов и др.; Под ред.

А.'П. Ершова, В. М. Монахова.— М.: Просвещение, 1986.— 143 с: ил.

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

Q 4306020400-399.письмо -86, доп. № 2 ББК73я72+32.973я 103(03)— © Издательство «Просвещение», Раздел I

УСТРОЙСТВО ЭВМ

В первой части курса были изложены первоначальные сведения об электронных вычислительных машинах (ЭВМ). Коротко их повторим.

ЭВМ — это машина для автоматической обработки информации. Она состоит из процессора, памяти и внешних устройств.

В памяти хранится разнообразная информация, закодированная в виде последовательностей цифр 0 и 1, которые принято называть битами (англ. bit — сокращение от binary digit_— двоичная цифра).

Работа процессора происходит под управлением программы. Программа находится в памяти ЭВМ и состоит из отдельных команд. Команды, как и любая информация, кодируются последовательностями цифр 0 и 1. Выполнение одной.команды процессором может состоять в арифметическом действии над числами, перемещении информации в памяти, выдаче команды внешнему устройству (например, «изобразить букву А на экране») и т. д.

Внешние устройства ЭВМ обеспечивают ввод и вывод информации, взаимодействие ЭВМ с человеком и другими ЭВМ. Кроме того, внешние устройства позволяют хранить информацию на так называемых внешних носителях: гибких магнитных дисках, кассетах магнитофона и т. д. На рисунке 1 изображен гибкий магнитный диск (он лежит на учебнике) и накопитель на гибких магнитных дисках (дисковод), в который вставлен другой такой же магнитный диск.

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

Такие устройства называют микросхемами (рис. 2). Если микросхема содержит целиком весь процессор ЭВМ, то она называется микропроцессором. Микропроцессор и другие микросхемы размещаются на плате, которая видна на рисунке 3.

На рисунке 4 изображена плата, на которой: 1 — микропроцессор, 2 — микросхемы памяти.

В этом разделе разберем подробнее устройство ЭВМ и ее частей, познакомимся с кодированием информации в машине, увидим, как выглядят машинные программы, и узнаем, как работает ЭВМ при их исполнении.

Будем рассматривать устройство вычислительных машин на примере выпускаемых нашей промышленностью персональных ЭВМ ДВК-2М (рис. 5), построенных на базе микропроцессора К1801ВМ1 (рис. 6).

§1. ОБЩАЯ СХЕМА УСТРОЙСТВА ЭВМ

Рассмотрим сначала, как хранится информация и как соединяются и обмениваются между собой информацией компоненты ЭВМ.

1. Память ЭВМ. Вся память разбита на отдельные участки из восьми битов. 8 битов информации называются байтом. Более крупная единица измерения — байт — часто оказывается удобнее, чем бит. Байты имеют номера: 0, 1, 2, 3,.... Эти номера называются также адресами. Два соседних участка: нулевой и первый, второй и третий, четвертый и пятый и т. д.— образуют ячейки памяти ЭВМ. Как мы видим, одна ячейка памяти может хранить два байта, другими словами — 16 битов информации. Для содержимого одной ячейки используется название — машинное слово или просто слово. Каждое слово тоже имеет адрес — это адрес начального байта слова. Таким образом, адресами слов будут четные числа 0, 2, 4, 6,.... Адреса слов и байтов тоже необходимо хранить в памяти ЭВМ и передавать между различными устройствами машины. При этом, как и другая информация, адреса кодируются последовательностями нулей и единиц. Каждый адрес кодируется 16 битами.

Например, адреса 0, 1024 и 65535 кодируются так:

2. Связь и обмен информацией между компонентами ЭВМ осуществляется с помощью магистрали (рис. 7). Магистраль можно представить себе как пучок проводов, к которому параллельно подсоединены все компоненты ЭВМ. Посылая по магистрали электрические сигналы, любая компонента ЭВМ может передавать информацию другим компонентам.

Рассмотрим, как происходит обмен информацией через магистраль. Пусть процессору необходимо прочесть порцию информации из памяти. Прежде всего необходимо указать, в каком месте памяти расположена требуемая информация. Это место указывается с помощью адреса. Для передачи адреса (16 битов) используются 16 проводов магистрали.

По тем же 16 проводам передается и информация. Таким образом, максимальная порция информации, передаваемая за один раз, состоит из 16 битов.

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

Чтение процессором слова, записанного в памяти по некоторому адресу, происходит следующим образом:

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

2. Память считывает адрес с магистрали и передает на магистраль содержимое соответствующего слова.

3. Процессор считывает слово с магистрали.

Примерно так же взаимодействуют между собой и все остальные компоненты ЭВМ. Более подробно об этом смотрите в приложении III.

1. Что такое ЭВМ? Для чего она используется?

2. Перечислите внешние устройства ЭВМ. Расскажите об их назначении.

3. Что такое бит и байт? Сколько битов в одном байте?

1. Что такое микросхема, микропроцессор?

2. Что такое магистраль? Для чего она служит?

3. Как происходит чтение слова из памяти?

1. Память ЭВМ ДВК-2М позволяет хранить 56 кбайтов. Учитывая, что 1 кбайт = 1024 байта, определите, сколько слов может поместиться в памяти этой ЭВМ.

§2. ОСНОВНОЙ АЛГОРИТМ РАБОТЫ ПРОЦЕССОРА

ЭВМ можно запрограммировать для исполнения очень сложных алгоритмов и переработки огромных объемов информации. Однако при исполнении этих алгоритмов ЭВМ выполняет громадное число простых шагов; за один шаг ЭВМ выполняет только одну команду над элементарными порциями информации — битами, байтами, словами.

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

1. Собственная память процессора. Процессор — это важнейшее устройство ЭВМ, обеспечивающее автоматическое исполнение хранящейся в памяти программы.

Процессор имеет небольшую собственную память, из которой нас интересуют 8 слов, называемых регистрами и имеющих имена R0, R1, R2, R3, R4, R5, R6, R7.

Каждый регистр, как и слово обычной памяти, хранит 16 битов; кроме того, в собственной памяти процессора нас интересуют еще два бита с именами N и Z.

2. Основной алгоритм работы процессора. Как и всякая информация, команды программы размещаются в памяти ЭВМ, и каждая команда занимает одно слово. Адреса слов — четные числа, каждое слово занимает два байта. Поэтому, например, программа из трех команд может храниться по адресам 1500, 1502, 1504.

Процессор в каждый момент исполнения программы помнит, какую команду он должен выполнять следующей. Для этой цели используется регистр R7, называемый также Счетчиком Команд (СК). Если после выполнения очередной команды СК = 1500, то это значит, что следующей выполняемой командой будет команда, хранящаяся по адресу 1500.

Как же работает процессор? Чтобы выполнить команду, он должен прежде всего узнать, в чем она состоит, т. е. получить из памяти слово по адресу, хранящемуся в Счетчике Команд. Далее, процессор должен изменить содержимое Счетчика Команд, иначе на следующем шаге будет снова выполняться та же самая команда. Затем процессор приступает собственно к выполнению команды. Пусть, например, это команда "переслать слово R1 в R2". В этом случае процессор помещает в регистр R2 содержимое регистра R1. В нашем примере хранящийся в Счетчике Команд адрес увеличивается на 2. В результате этого процессор переходит к выполнению команды, которая хранится в памяти следом за только что выполненной.

Таким образом, действия процессора по выполнению каждой команды состоят из четырех этапов, процессор 1) читает адрес из Счетчика Команд;

2) читает слово из памяти по этому адресу;

3) увеличивает Счетчик Команд на 2;

4) выполняет команду, записанную в прочитанном слове.

Этот циклический процесс прекращается, когда выполняемой командой окажется специальная команда стоп.

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

3. Пример программы. Пусть требуется целое число, находящееся в регистре R0, сложить с целым числом в регистре R1 и поместить результат в регистр R2, не меняя R0 и R1. Это можно сделать с помощью двух команд:

переслать слово R0 в R2, добавить слово R1 к R2.

На алгоритмическом языке смысл этих команд можно выразить как R2 := R0 и К := R1 + R2.

Чтобы процессор выполнил эти две команды, их надо поместить в памяти друг за другом, например в ячейки с адресами 1500 и 1502, и записать в СК адрес первой команды, т. е. 1500. Чтобы процессор остановился после выполнения этих двух команд, в следующее слово памяти с адресом 1504 нужно поместить команду стоп. Предположим, что это сделано, и что в начальный момент содержимое регистров такое: R0 = 21, R1 = 15, R = 4 (табл. 1).

Напомним, что и команды в памяти ЭВМ, и числа в регистрах процессора изображены в таблице в привычном для человека виде. В машине они кодируются последовательностями из 0 и 1.

4. Пример исполнения программы процессором. Посмотрим, как работает процессор при исполнении этой программы. В соответствии с основным алгоритмом, на первом шаге процессор 1) читает содержимое СК (1500);

2) читает слово из памяти по адресу 1500, т. е. команду "переслать слово R0 в R2";

3) увеличивает СК на 2 (до 1502);

4) выполняет прочитанную команду, т. е. пересылает содержимое регистра R0 (21) в регистр R2, после чего в регистре R2 также будет содержаться число 21.

После этого процессор выполняет второй шаг:

1) читает содержимое СК (1502);

2) читает слово из памяти по адресу 1502, т. е. команду "добавить слово R1 к R2";

3) увеличивает СК на 2 (до 1504);

4) выполняет прочитанную команду, т. е. добавляет содержимое регистра R1 (15) к содержимому регистра R2 (21), после чего в R2 будет содержаться число 36.

После этого процессор выполняет третий шаг, т. е. снова 1) читает содержимое СК (1504);

2) читает слово из памяти по адресу 1504, т. е. команду стоп;

3) увеличивает СК на 2 (до 1506);

4) выполняет прочитанную команду, т. е. останавливается.

Итак, в результате исполнения этой программы в регистре R2 появится число 36 — сумма содержимого регистров R0 (21) и R1 (15).

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

Из третьей колонки таблицы видно, что Счетчик Команд после выполнения каждой команды указывает адрес следующей выполняемой команды программы. В процессе работы он «скользит» по программе, автоматически увеличиваясь при выполнении каждой команды, как бы «считая» команды программы. Этим и объясняется его название.

1. Каков общий вид алгоритма, записанного на алгоритмическом языке?

2. Какие бывают составные команды? Приведите примеры.

3. Какие типы величин используются в алгоритмическом языке? Приведите примеры.

4. Какие величины называются:

а) аргументами; б) результатами; в) промежуточными величинами? Приведите примеры.

5. Как выполняется команда присваивания?

1. Что надо сделать, чтобы процессор исполнил заданную программу? Где нужно разместить команды программы? Чему должно равняться содержимое СК?

2. Процессор выполнил команду стоп, расположенную в слове по адресу 1022. Каково после этого содержимое регистра СК?

1. Заполните таблицу значений для рассмотренной программы, предполагая, что в начальный момент:.

2. Напишите программу, которая складывает целые числа, находящиеся в регистрах R0, Rl, R2, и помещает результат в:

а) регистр R3; б) регистр R2.

3. Заполните таблицу значений для программ упражнения 2, считая, что программа размещена начиная с адреса 1500, в начальный момент СК = 1500, R0 = 5, R1 = 7, R2 = 8.

4. Напишите программу, которая складывает удвоенное содержимое регистра R0 с утроенным содержимым регистра R1 и помещает результат в:

а) регистр R2; б) регистр R1; в) каждый из регистров R3 и R4.

5. Напишите программу, которая помещает в регистр R1 учетверенное содержимое регистра R0.

§ 3. КОМАНДА ВЕТВЛЕНИЯ И КОМАНДА ПОВТОРЕНИЯ

Для написания программ, с ветвлениями и повторениями используются специальные команды, изменяющие содержимое Счетчика Команд (СК) в зависимости от значений битов N и Z процессора.

1. Назначение битов N и Z процессора. При выполнении некоторых команд процессора меняется не только содержимое регистров, но и биты N и Z в процессоре. Например, при выполнении команды "сравнить слово R1 с R2" в зависимости от знака числа (R R2) устанавливаются следующие значения битов Negative — отрицательный) и Z (zero — нуль) (табл. 3):

Содержимое регистров R1 и R2 при выполнении этой команды не изменяется.

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

Примером такой команды является команда Ее выполнение зависит от значения бита N. Если оно равно 0, то, не выполняя никаких других действий, процессор увеличивает содержимое СК на 2. Если же бит N равен 1, то содержимое СК в дополнение к обычному увеличению на 2 будет увеличено еще на 4, т. е. увеличится на 6. В результате этого две команды, идущие в памяти вслед за этой командой, пропускаются. (Это объяснение в короткой форме содержится в названии команды.) Существует и команда безусловного перехода, которая независимо ни от чего увеличивает или уменьшает СК на указанное число слов в дополнение к обычному увеличению на 2. Например, после выполнения команды содержимое СК увеличится на 4 (вместо обычного увеличения на 2) и одна команда будет пропущена.

3. Пример программы с ветвлением. Пусть требуется написать программу, которая помещает в регистр R3 большее из двух целых чисел, находящихся в регистрах R1 и R2. Запишем это на алгоритмическом языке:

алг большее число (цел Rl, R2, R3) Расположим соответствующую программу в памяти ЭВМ, начиная с адреса 1500, (табл. 4).

Приведем таблицу значений (табл. 5) для этой программы, считая, что в начальный момент СК = 1500, R1 =5 и R2 = 7. Напомним, что в таблице значений указывается содержимое СК после выполнения команды.

Заметьте, что при исполнении этой программы в результате шага 2 пропускаются две команды (с адресами 1504 и 1506). После шага 3 бит N станет нулевым, так как пересылается положительное число.

Если в начальный момент СК = 1500, R1 = 5, a R2 = 7, то таблица значений будет выглядеть так (табл. 6):

переслать слово R1 в R Заметьте, что при исполнении этой программы в результате шага 4 пропускается команда с адресом 1508.

4. Пример программы с повторением. Пусть требуется написать программу, которая должна поместить в регистр R2 значение выражения К + (К 1) + ... + 2 + 1, где число К записано в регистре R1 и не должно меняться. При исполнении этой программы в регистре R2 будут храниться последовательно:

В регистре R0 будет очередное слагаемое: вначале К, затем К 1, К 2 и т. д. Когда R0 станет равным нулю, исполнение программы закончится.

Расположим соответствующую программу в памяти ЭВМ, начиная с адреса (табл. 7).

Команда "очистить регистр R2" помещает в регистр R2 число 0 и записывается на алгоритмическом языке как R2 := 0. Следующие команды означают R0 := R1 и R2 := R2 + R0. Команда "уменьшить слово R0 на единицу", помимо этого уменьшения, устанавливает значения битов N и Z: если новое, уменьшенное, значение R0 отрицательно, то выполняются действия N := l, Z := 0. Если новое значение R0 равно 0, то N := 0, Z := 1. Наконец, если новое значение R0 положительно,, то N := 0, Z := 0.

Команда "если больше, переход на — 3 слова" проверяет значение битов N и Z. Если оба бита N и Z оказываются равными 0, то при ее выполнении СК уменьшается на (вместо обычного увеличения на 2).

Приведем таблицу значений для этой программы, считая, что в начальный момент С К = 1500 и R1 = 3 (табл. 8). Голубым цветом показаны значения битов N и Z, проверяемые при выполнении следующего шага.

если больше, переход на - 3 слова если больше, переход на - 3 слова если больше, переход на - 3 слова Из этой таблицы видно, что команды с адресами 1500, 1502, 1510 выполнились один раз, команды с адресами 1504, 1506, 1508 выполнились по три раза каждая. Это вызвано тем, что после шагов 5 и 8 происходил возврат к команде с адресом 1504. Если бы в начальный момент содержимое регистра R1 равнялось числу 100, то команды с адресами 1504, 1506, 1508 выполнились бы по 100 раз каждая.

1. Какие знаки отношений между величинами используются в алгоритмическом языке?

2. Какие величины называются табличными? Приведите примеры.

3. Для чего нужны вспомогательные алгоритмы? Как записывается команда их вызова?

1. Известно, что R1 = 5, R2 = 5, R3 = 7, R4 = 0. Выпишите значения битов N и Z после выполнения команды а) "сравнить слово R1 с R2", б) "сравнить слово R2 с R3", в) "сравнить слово,R3 с R4".

2. По адресу 1508 расположена команда "переход на +1 слово". Чему будет равно содержимое СК после выполнения этой команды?

3. В программе 5 команд. Может ли число шагов при.исполнении этой программы оказаться равным: а) 1, б) 5, в) 100?

1. Напишите программу, после исполнения которой в регистре R0 будет содержаться:

в) наибольшее из чисел, лежащих в R0, R1;

г) наибольшее из чисел, лежащих в Rl, R2, R3.

2. Напишите программу, после исполнения которой в регистре R0 будет содержаться сумма 2К + (2К 2) + … + 4 + 2, если перед началом работы число К хранится в регистре R1.

3. Напишите программу, после исполнения которой в регистре R0 будет содержаться 999 + 997 +... + 3 + 1. Перед началом работы R1 = 500.

§4. ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В ЭВМ

Мы уже говорили, что любая информация кодируется в ЭВМ с помощью последовательностей цифр 0 и 1. Рассмотрим теперь, как именно кодируются в ЭВМ адреса, числа, символы и команды.

1. Биты, байты и слова. Байт состоит из 8 битов, каждый из которых может принимать два значения: 0 или 1. Таким образом, байт может принимать 28 = 256 различных значений, а состоящее из 16 битов машинное слово может принимать 216 = 65536 различных значений. Принято нумеровать биты справа налево, начиная с нуля. Биты в слове "0001001001001111" нумеруются так (табл. 9):

Значение нулевого бита обозначается i0, значение 1-го бита обозначается i1 и т. д.

2. Кодировка адресов. В ЭВМ каждый адрес кодируется последовательностью из 16 нулей и единиц, т. е. задается словом. В наших программах мы обозначали адреса числами от 0 до 65535. Соответствие между этими числами и последовательностями из нулей и единиц задается формулой Приведем несколько примеров кодировки адресов (табл. 10).

3. Кодировка целых чисел. Целые числа, так же как и адреса, кодируются последовательностями из 16 нулей и единиц, т. е. словами. Поэтому можно закодировать лишь 65536 различных целых чисел. Способ кодировки выбран так, что он охватывает целые числа от 32768 до +32767. Соответствие между целым числом и его двоичным кодом задается формулой Приведем несколько примеров кодировки чисел (табл. 11).

4. Кодировка символов. Символы (цифры, русские и латинские буквы, знаки препинания и пр.) обычно кодируются последовательностями из 8 нулей и единиц, т. е. байтами. Поскольку байт имеет 256 различных значений, можно закодировать 256 различных символов. Существует несколько различных способов кодировки символов. Конкретный способ кодировки символов задается таблицей, в которой указаны коды всех символов.

5. Кодировка команд. В наших программах мы писали команды в обозначениях, удобных для человека. Однако в ЭВМ каждая команда кодируется последовательностью из 16 нулей и единиц, т. е. словом. Конкретные примеры кодировки команд приведены в приложении III.

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

2. Величины каких типов используются в алгоритмическом языке?

Каково число различных последовательностей из трех цифр, каждая из которых либо нуль, либо единица?

1. Какой адрес кодируется последовательностью 1000000000000000?

2. Какой последовательностью кодируется адрес 1024?

3. Какое целое число кодируется последовательностью 1000000000000000?

§5. ФИЗИЧЕСКИЕ ПРИНЦИПЫ РАБОТЫ ЭВМ

Мы уже знаем, что вся информация хранится в ЭВМ в виде большого количества нулей и единиц. В каком же виде записываются в памяти и обрабатываются процессором эти нули и единицы? Один из возможных способов таков. Будем считать, что наличие электрического сигнала, более точно — электрического напряжения (разности потенциалов), на данном участке электронной схемы кодирует единицу, а его отсутствие — нуль.

(Реально — при одном из самых распространенных способов кодирования — к микросхеме присоединяется источник питания, вырабатывающий напряжение +5 В, нулю соответствует потенциал от 0 до 0,5 В, а единице — потенциал от 2,5 до 5 В по отношению к заземленным участкам схемы.) Простейшим электронным устройством обработки информации, закодированной с помощью наличия или отсутствия напряжения, является инвертор (рис. 8). Инвертор имеет два контакта —- входной и выходной. Он устроен так. Если подать на его вход напряжение, то на выходе напряжение пропадает, а если на вход не подавать напряжение, то на выходе оно будет. (Точнее нужно говорить, конечно, не о наличии или отсутствии напряжения, а о высоком или низком напряжении.) Работа инвертора описывается такой таблицей (табл. 12):

Мы знаем, что наличие напряжения кодирует единицу, а его отсутствие — нуль.

Получаем такую таблицу (табл. 13):

На тех же принципах, что и инвертор, основан и более сложный элемент, имеющий два входа и один выход (рис. 9). Его работа описывается таблицей 14.

Другими словами, на выходе такого элемента появляется нуль, если на обоих его входах — единицы. Во всех остальных случаях на его выходе появляется единица.

Это можно записать так:

поэтому этот элемент иногда называют элементом И-НЕ.

Из тысяч и миллионов такого рода элементов строятся ЭВМ.

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

Клавиатура (см. рис. 5) предназначена для ввода информации в ЭВМ с помощью нажатий на клавиши. Простейший вариант устройства клавиатуры таков: при нажатии на клавишу замыкается контакт (как в кнопке электрического звонка) и тем самым в электронную схему клавиатуры попадает сигнал о том, какая клавиша нажата.

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

Печатающее устройство (рис. 10), или принтер (от англ. print — печатать), позволяет выводить результаты работы ЭВМ на бумагу. С его помощью можно печатать и рисунки (рис. 11), и тексты.

Если посмотреть на рисунок 11 при большом увеличении, то мы увидим, что он составлен из отдельных точек (рис. 12).

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

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

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

Пучок электронов, испускаемый источником, попадает на экран, и на экране возникает светящаяся точка.

Яркость этой точки зависит от подаваемого на кинескоп управляющего потенциала и может управляться электронной схемой дисплея. (Потенциал может быть и таким, что точки вовсе не будет видно.) Отклоняющая система перемещает эту точку по экрану, создавая для этой цели магнитное поле, отклоняющее летящие электроны. При этом точка движется из А в В, затем перескакивает из В в С, движется в D, перескакивает в Е, движется в F и т. д. (рис. 14).

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

Накопитель на гибких магнитных дисках (см. рис. 1) позволяет сохранять информацию между сеансами работы с ЭВМ на гибком диске. Если бы такого устройства не было, то все результаты работы машины терялись бы при выключении и каждый сеанс работы приходилось бы начинать с того, что вводить заново все программы, исходные данные и т. п.

Гибкий диск (см. рис. 1) представляет собой пластмассовую круглую пластинку, покрытую специальным составом, обладающим магнитными свойствами. (Похожим составом покрыта магнитофонная лента.) Он напоминает гибкую грампластинку, помещенную в закрытый конверт. В центре диска и конверта имеются круглые отверстия. Кроме того, в конверте есть еще одно продолговатое отверстие, через которое магнитная головка, читающая и записывающая информацию на диск, может приближаться к поверхности диска. (На рисунке 1 сквозь отверстия в конверте видна часть диска.) Когда диск вставляется в накопитель, отверстие в нем надевается на вращающуюся ось и диск начинает крутиться, совершая несколько оборотов в секунду. После этого магнитная головка, похожая на те, которые используются в магнитофонах, приближается к вращающейся поверхности диска и начинает записывать информацию или считывать ранее записанную. Запись и воспроизведение происходят так же, как в магнитофонах, только записывается и воспроизводится не музыка, а последовательности нулей и единиц, кодирующие нужную нам информацию.

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

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

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

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

Автоматическая работа ЭВМ обеспечивается основным алгоритмом работы процессора и использованием специального регистра — Счетчика Команд. И программа, и обрабатываемая с ее помощью информация кодируются в двоичном коде.

Составление программ в двоичных кодах и размещение их в памяти ЭВМ очень трудоемкая работа. Мы видели, как непросто закодировать даже элементарную конструкцию если-то-иначе-все, а ведь мы писали не в двоичных кодах, а в привычных для человека обозначениях. Поэтому в кодах на ЭВМ, как правило, не работают — человек составляет программу на алгоритмическом языке или на каком-то языке программирования, а в коды эту программу переводит уже сама ЭВМ под управлением специальных системных программ. Как именно это делается, мы рассмотрим в § 17.

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

1. Как кодируется информация в ЭВМ? Как представляются биты при хранении информации в памяти и обработке ее процессором?

2. Что такое инвертор?

3. Что такое элемент И-НЕ?

4. Как может быть устроена клавиатура ЭВМ?

5. Как образуется изображение, печатаемое на бумаге?

6. Как образуется изображение на экране дисплея?

7. Как записывается информация на магнитном диске?

ЗНАКОМСТВО С ПРОГРАММИРОВАНИЕМ

АЛГОРИТМИЧЕСКИЙ ЯЗЫК

В первой части курса мы изучали основные конструкции алгоритмического языка.

Сейчас продолжим это изучение.

Напомним, что команда ветвления записывается так:

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

Однако часто оказывается, что возможных случаев не два, а больше. Например, вспомним алгоритм определения кислотности раствора (п. 4, ч. I).

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

1) бумажка покраснела;

2) бумажка посинела;

3) бумажка не изменила цвет.

Команда выбора позволит записать этот же алгоритм более просто и наглядно.

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

алг определение кислотности раствора нач отлить в пробирку 1 мл раствора опустить в пробирку лакмусовую бумажку кон Команда выбора может записываться в полной и сокращенной форме. В этом примере использована сокращенная форма команды:

выбор все Выполнение команды выбора происходит так. Сначала исполнитель проверяет, соблюдается ли условие 1. Если да, то он выполняет команды, входящие в серию 1, и на этом выполнение команды выбора заканчивается. Если нет, то исполнитель проверяет, соблюдается ли условие 2. Если проверяемое условие соблюдается, то он выполняет команды, входящие в серию 2, и на этом выполнение команды выбора заканчивается. Если же и условие 2 не соблюдается, то исполнитель проверяет условие 3. Если оно соблюдается, то он выполняет серию 3 и т. д. Другими словами, исполнитель последовательно проверяет все условия команды, пока не обнаружит первое из них, которое соблюдается. Найдя первое такое условие, исполнитель выполняет стоящую за ним серию команд, и на этом выполнение команды выбора заканчивается. Если, например, перед началом выполнения команды выбора соблюдается и условие 2, и условие 3, то исполнитель все равно выполнит только серию 2.

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

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

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

П р и м е р 1. Записать алгоритм, определяющий число корней уравнения х2 = а в зависимости от а.

алг число корней (вещ а, лит А) нач кон Пример 2. Записать алгоритм, позволяющий получить словесное наименование школьных оценок, т. е. позволяющий получить их значение в виде литерных величин.

алг название оценки (цел х, лит А) нач кон П р и м е р 3. Составить алгоритм вычисления значений функции, график которой изображен на рисунке 16.

Область определения этой функции разбивается на три участка. На промежутке ]—, 0] значения функции тождественно равны нулю. На промежутке ]0, 1] значения данной функции совпадают со значениями функции у = х. Наконец, на промежутке ]1, + °°[ значения функции тождественно равны 1. Таким образом различаются три случая:

1) х 0;

3) х> 1.

Выписанные условия и будут фигурировать в команде выбора; мы заменим лишь запись 0 < х 1 на принятую в алгоритмическом языке запись 0 < х и x 1. Получается такой алгоритм:

алг значение функции (вещ х, вещ у) нач кон Вспомним, что условия в команде выбора проверяются последовательно. При этом второе условие будет проверяться только в том случае, если первое условие не соблюдается и, следовательно, х > 0. Таким образом, часть второго условия (0 < х) можно не проверять: если дело дошло до проверки второго условия, то заведомо 0 < х. Рассуждая аналогично, замечаем, что проверку третьего условия (х > 1) можно исключить. Действительно, если второе условие (х 1) не соблюдается, то третье условие (х > 1) будет соблюдаться автоматически. Приходим к такому алгоритму:

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

выбор при условие: серия все Ее полная форма если условие все может быть записана в виде выбор при условие: серия все 1. Как записывается команда выбора? Как она выполняется? Приведите примеры.

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

3. Может ли команда ветвления рассматриваться как частный случай команды выбора? Приведите примеры.

1. Запишите в виде команды выбора фразу из сказки: «Направо пойдешь — коня потеряешь, налево пойдешь — смертью умрешь, прямо пойдешь — друга найдешь».

2. Напишите алгоритм вычисления значений функции, график которой изображен на рисунке 17.

3. Запишите алгоритм нахождения числа корней уравнения х2 = а + 1 в зависимости от значения параметра a.

4. Запишите алгоритм вычисления абсолютной величины (модуля) вещественного числа с помощью команды выбора.

5. Нарисуйте график функции, значения которой вычисляются таким алгоритмом:

алг значение функции (вещ х, вещ у) нач кон 6. В тексте приведены два варианта алгоритма «значение функции» с использованием команды выбора. Поменяем в каждом из них местами два первых условия команды выбора, записав:

а) выбор б) выбор Останутся ли алгоритмы правильными? Почему?

7. Запишите с помощью команды выбора:

если условие то если условие 8. Напишите алгоритм нахождения числа корней уравнения ах + b = 0 в зависимости от значений параметров а, b. Не забудьте рассмотреть случай а = 0, а также а = 0 и b = 9. Напишите алгоритм нахождения числа дней в месяце, если даны: номер месяца п — целое число от 1 до 12; целое число а, равное 1 для високосного года и равное 0 в противном случае:

10. Напишите алгоритм вычисления значений функции у =| х 1 | + | х 4|, различающий случаи x 1, 1 < х 4 и х > 4.

11. Чтобы определить, на какую цифру оканчивается квадрат целого числа, достаточно знать лишь последнюю цифру самого числа. Напишите алгоритм, который по одной из цифр 0, 1,2,..., 9 — последней цифре числа п — находит последнюю цифру числа n2.

12. Напишите алгоритм, который по номеру дня недели — целому числу от 1 до — выдает в качестве результата количество уроков в вашем классе в соответствующий день.

§7. КОМАНДА ПОВТОРЕНИЯ С ПАРАМЕТРОМ

В первой части курса (п. 4) мы изучали команду повторения пока условие серия Эта команда позволяет выполнить одну и ту же серию многократно.

П р и м е р 1. Записать алгоритм, заполняющий нулями таблицу вещ таб а [1:100].

алг заполнение нулями (вещ таб а[1:100]) нач цел i кон При исполнении этого алгоритма команда выполняется сначала для i = 1, затем для i = 2,..., 100. Более наглядно этот алгоритм может быть записан с помощью команды повторения с параметром. При этом он будет выглядеть так:

алг заполнение нулями (вещ таб а [1:100]) нач цел i кон В данном случае параметром является целочисленная переменная величина i, которая в ходе выполнения команды принимает все значения от 1 до 100. Для каждого из этих значений переменной выполняется команда а [i]: = 0. В результате таблица а заполняется 100 нулями.

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

для х от Xmin до Xmаx Здесь х: — целочисленная переменная величина, a Xmin и Хmах — выражения, принимающие целочисленные значения. Выполнение команды происходит так:

1) вычисляются значения выражений Xmin и Хmах;

2) переменной х последовательно присваиваются значения Xmin, Xmin + 1. Xmin + 2,..., Xmax, и для каждого из этих значений выполняется серия команд, заключенная между нц и кц, в частности при Xmin = Xmax эта серия выполнится только один раз. Если же с самого начала Xmin > Xmax, то серия не выполнится ни разу.

Приведем еще несколько примеров, где применение команды повторения с параметром (будем называть ее циклом «для») вместо команды повторения (цикла «пока») позволяет упростить запись алгоритмов.

П р и м е р 2. Записать алгоритм суммирования элементов линейной таблицы (п. 10) с использованием команды повторения с параметром.

В п. 10 (см. ч. I) этот алгоритм был записан в виде:

алг сумма (вещ таб а [1:1000], вещ S) нач цел i кон Теперь это можно записать проще:

алг сумма (вещ таб а [1:1000], вещ S) нач цел i кон П р и м е р 3. Заполнить таблицу произведение [1:9, 1:9], сделав произведение [i, j] равным произведению чисел i и j.

В п. 10 для этого использовался такой алгоритм:

алг таблица умножения (цел таб произведение [1:9, 1:9]) рез произведение нач цел i, j кон Мы используем обозначение ij для произведения чисел i и j, чтобы постепенно привыкать к обозначениям, принятым в языках программирования.

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

алг таблица умножения (цел таб произведение [1:9, 1:9]) рез произведение нач кон В этом примере одна команда повторения используется внутри другой команды повторения. Мы видим, что команда повторения с параметром позволяет записывать алгоритмы более коротко и наглядно.

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

алг копирование таблицы (цел таб а [1:100], цел таб b [l:100]) нач кон Если нам нужно, чтобы данные в таблице b располагались в обратном порядке (по сравнению с их порядком в таблице а), то можно составить алгоритм «обращение» следующим образом:

алг обращение (цел таб а (1:100], цел таб b[1:100]) нач цел i кон При исполнении этого алгоритма команда выполняется сначала при i = 1:

затем при t = 2:

наконец, при i = 100:

В результате этого значения b[1], b[2],..., b [100] становятся равными соответственно а[100], а [99],..., а[1], что и требовалось.

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

Этот алгоритм иллюстрирует совместное применение команд повторения с параметром и выбора.

алг подсчет (цел таб а [1:100], цел отр, пул, пол) нач цел i кон Во всех предыдущих примерах команда повторения с параметром использовалась для работы с таблицами. Но ее удобно использовать и в других случаях. Например, с ее помощью можно рисовать картинки.

П р и м е р 6. Составить алгоритм рисования спирали.

алг спираль 1 (цел п) нач цел i кон При исполнении этого алгоритма с п = 10 появится такая же картинка, как на рисунке 18.

Интересно посмотреть, как будет выполняться этот алгоритм при малых значениях п. При п = 2 будет нарисована ломаная из двух звеньев (рис. 19), при п = 1 нарисован отрезок (рис. 20).

Что же получится, если взять п = 0? При этом будет выполняться команда:

для i от 1 до вперед (i); налево (90) Оказывается, что не будет нарисовано ничего. Дело в том, что в алгоритмическом языке принято такое соглашение: в команде вида для х от Xmin до Хmах при Xmin > Хmах серия команд не выполняется ни разу. Поэтому алгоритм рисования спирали при п = 0 или при п < 0 ничего не нарисует.

П р и м е р 7. Записать алгоритм рисования правильного п-угольника со стороной 1.

алг n-угольник (цел п) нач кон При исполнении этого алгоритма исполнитель п раз повторяет такие действия:

нарисовать отрезок длины 1, повернуться налево на угол в Обратите внимание, что в этом алгоритме серия команд входящая в команду повторения с параметром i, не использует значение этого параметра.

Он используется только как счетчик числа повторений.

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

для x от Xmin до Хmах шаг хшаг Выполнение этой команды происходит так же, как и команды на с. 39; разница состоит в том, что после каждого повторения значение параметра х увеличивается не на 1, а на значение целочисленного выражения хшаг.

П р и м е р 8. Записать алгоритм вычисления суммы всех двузначных нечетных чисел.

алг сумма нечетных (цел S) нач кон Пример 9. Составить алгоритм заполнения таблицы, содержащей число дней для 1901,..., 1999 годов. Напомним, что каждый четвертый из них, начиная с 1904 года, високосный и содержит на один день больше, чем обычно, а все остальные содержат 365 дней.

алг заполнение таблицы (цел таб число дней [1901 : 1999]) рез число дней нач кон Первая команда повторения заполняет таблицу без учета високосных лет. Она выполняется для Вторая вносит поправку для високосных лет и выполняется для Значение параметра i, равное 1996 + 4 = 2000, оказывается большим указанной в команде границы 1999, и для него серия команд между нц и кц (в данном случае — единственная команда) не выполняется.

Команда повторения с параметром, не содержащая явного указания шага, эквивалентна команде повторения с шагом 1.

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

1. Какова форма записи команды повторения с параметром?

2. Приведите примеры применения команды повторения с параметром.

3. Может ли команда повторения с параметром содержать внутри себя команду выбора или другую команду повторения с параметром? Приведите примеры.

4. Приведите пример применения команды повторения с параметром и шагом, не равным 1.

1. Используя команду повторения с параметром, составьте алгоритм, который прибавляет по 1 ко всем элементам таблицы а. Его заголовок должен иметь вид:

алг прибавление 1 (цел таб а [1 : 100]) 2. Составьте алгоритм заполнения таблицы умножения чисел от 1 до 99 двумя способами: с использованием и без использования команды повторения с параметром. Заголовок должен иметь вид:

алг таблица умножения (цел таб произведение [1:99, 1:99]) рез произведение Какой из двух способов вам кажется более удобным?

3. Какие изменения нужно сделать в алгоритмах «копирование таблицы» и «обращение» (с. 36, 37), чтобы фигурирующие в них таблицы из 100 элементов заменить таблицами из 200 элементов?

4. Рассмотрим следующий алгоритм:

алг обработка 1 (цел таб а[1:10]) нач кон Каковы будут результаты исполнения этого алгоритма для величины а, значения которой приведены в таблице 15?

a[i] 5. Выполните предыдущее упражнение для алгоритмов а) алг обработка 2 (цел таб а [1 : 10]) б) алг обработка 3 (цел таб а[1:10]) нач кон 6. Что нарисует исполнитель алгоритма «n-угольник» (пример 7), если 7. Что нарисует исполнитель алгоритма «спираль» при n = 10, если заменить в нем команду "налево (90)" командой "направо (90)"?

8. Исходными данными являются целочисленная таблица температура [1 : 31], в которой записана температура за каждый день января, и величина S, равная средней январской температуре за последнее столетие. Составьте алгоритм, подсчитывающий, сколько в январе было дней с температурой, большей, меньшей и равной средней. Его заголовок должен иметь вид:

алг подсчет (цел таб температура [1 :31], цел S, цел бол, мен,рав) арг температура, S 9. Составьте алгоритм заполнения таблицы числа дней от 1801 до 1899 года. (Високосные годы — каждый четвертый, начиная с 1804 года.) 10. Составьте алгоритм заполнения таблицы числа дней от 1801 до 2000 года. Учтите, что 1900 год не високосный, а 2000 год високосный.

11. Составьте алгоритм вычисления числа воскресений в.1991 году. (Первое воскресенье 1991 года — 6 января.) 12. Составьте алгоритм заполнения таблицы числа дней для всех лет с 1-го до 2000го года. Указание: високосными являются годы, номера которых делятся на 4, за исключением тех, номера которых делятся на 100, но не делятся на 400.

13. Составьте алгоритм нахождения: а) минимального; б) максимального элемента таблицы а[1 : 100].

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

15. Составьте алгоритм вычисления суммы квадратов всех натуральных чисел от до 50: S = 12 + 22 + 32 + … + 502.

16. Составьте алгоритм вычисления первых 30 чисел Фибоначчи. (Эти числа определяются так: a1 = 1, а2 = 1, а каждое следующее число равно сумме двух предыдущих:

ап+1 = ап + 13, 21,… Вот первые несколько чисел Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21,... (§ 6, ч. I). Ответ получите в виде таблицы а [1:30].

17. Что нарисует исполнитель алгоритма «n-угольник» (пример 7), если в нем угол 360/n градусов заменить вдвое большим углом? Рассмотрите случаи п = 3, 4, 5, 6, 7, 8.

18. Составьте алгоритм циклической перестановки элементов таблицы а[1 : 1000], при которой a[i] перемещается в a [i + 1], а а [1000] перемещается в а[1].

19. Составьте алгоритм циклической перестановки элементов таблицы а[1 : 1000] на заданное число k шагов, так что элемент a [i] перемещается в a [i + k], а последние k элементов таблицы, которым «не хватило места», перемещаются в «освободившиеся»

первые k элементов таблицы.

20. Дана таблица а[1 : 500]. Напишите алгоритм, записывающий в качестве i-го элемента этой таблицы сумму чисел от а[1] до а[i] включительно.

§8. ВСПОМОГАТЕЛЬНЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ

ЗНАЧЕНИЙ ФУНКЦИИ

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

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

П р и м е р 1. В библиотеке алгоритмов приведен алгоритм вычисления модуля вещественного числа (ч. I, с. 90).

алг МОД (вещ х, вещ у) нач кон Этот алгоритм можно использовать, например, при вычислении значений функции у = |2x + 1| |3х + 7|.

алг вычисление 1 (вещ х, вещ у) нач кон При исполнении этого алгоритма мы дважды обращаемся к вспомогательному алгоритму МОД. После его первого применения а становится равным |2х + 1|, после второго b становится равным |3х + 7|. После этого команда дает нужное значение переменной у.

Этот же алгоритм можно записать иначе:

алг вычисление 2 (вещ х, вещ у) нач кон Чтобы исполнитель мог исполнить этот алгоритм, ему нужно сообщить алгоритм вычисления модуля, т. е. абсолютной величины abs (m) заданного числа т. Это делается в такой форме:

алг вещ abs (вещ х) нач кон Первая строка этой записи является заголовком. Записывая заголовок вспомогательного алгоритма вычисления функции, мы указываем тип значений функции (в данном случае вещ), название функции (в данном случае abs), затем в скобках список её аргументов с указанием типа (в данном случае функция имеет единственный вещественный аргумент х). Больше ничего указывать в заголовке не требуется — и так ясно, что все перечисленные в скобках величины являются аргументами, а результатом является значение функции, обозначаемое сокращенно служебным словом знач. Эта величина используется как переменная, тип которой совпадает с типом значений функции. Указывать тип этой величины не следует.

За заголовком следует алгоритм вычисления значения abs(x) при заданном х. Он гласит, что при неотрицательном х значение вычисляемой функции равно х, а в противном случае (при отрицательном х) значение равно х.

П р и м е р 2. Рассмотрим алгоритм нахождения большего из двух чисел (ч. I, с. 90).

алг БИД (вещ а, b, вещ у) нач кон Используя этот алгоритм как вспомогательный, мы записывали алгоритм нахождения большего из трех чисел так:

алг БИТ (вещ а, b, с, вещ у) нач вещ z кон В этом алгоритме используется промежуточная величина z, значение которой равно большему из чисел а и b, Алгоритм БИТ основан на таком свойстве: если через max 2 (а, b) обозначить большее из чисел a, b, a через max 3(а, b, с) — большее из трех чисел а, b, и с, то При новом способе записи вспомогательных алгоритмов алгоритм БИД приобретает такой вид:

алг вещ max 2(вещ a, b) нач кон а использующий его алгоритм нахождения БИТ — такой:

алг вещ max 3(вещ a, b, с) нач знач := max2(max2(a, b), с) кон Приведем еще несколько примеров вспомогательных алгоритмов вычисления функций.

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

Пример 3. Записать алгоритм вычисления значений функции у = sign(x), определенной следующим образом:

График этой функции изображен на рисунке 21.

Заголовок алгоритма вычисления значений функции у = sign(x) запишется так:

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

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

Для единообразия будем записывать значения всех функций с использованием скобок и писать, например, sin(x) вместо обычного sin x.

При таком способе записи со скобками известная формула для синуса суммы запишется следующим образом:

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

Здесь операция возведения в степень обозначена, как это принято во многих языках программирования, двумя звездочками, т. е. вместо а2 пишем а 2, вместо 10x пишем Аргументом функции может быть не только число (или несколько чисел), но и таблица. В следующем примере аргументом является линейная таблица а[1 : 100] из 100 элементов.

П р и м е р 4. Записать алгоритм вычисления среднего арифметического всех элементов таблицы а[1 : 100].

алг вещ среднее (вещ таб а[1 : 100]) нач кон П р и м е р 5. Записать алгоритм вычисления значений функции факториал (n) натурального аргумента п, определяемой как произведение всех натуральных чисел от 1 до п:

В математике эта функция обозначается п! Алгоритм вычисления значений функции факториал (п) таков:

алг цел факториал (нат п) нач кон Найдем теперь сумму факториалов всех целых чисел от 1 до 10, используя алгоритм вычисления факториала как вспомогательный.

алг сумма факториалов (цел S) нач цел i кон Существуют так называемые рекурсивные алгоритмы вычисления значений функций. Приведем два примера таких алгоритмов.

Иногда значение функции для некоторого аргумента можно выразить через значение этой же функции от другого аргумента, например sin(x + ) = sin(x) для всех вещественных х.

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

Пример 6. Определение функции факториал можно записать в виде следующего соотношения:

Покажем, как, используя это соотношение, можно вычислить, например, факториал (4).

Подставляя п = 4, находим, что Теперь используем наше соотношение при п = 3 и подставим полученное выражение для факториал (3). Получается факториал (4) = факториал (2) 3 4.

Наконец, применим соотношение при п = 2 и получаем факториал(4) = факториал (1) 2 3 4.

Сделав еще одну подстановку, получаем, наконец, что П р и м е р 7. Вычислим значение функции квадрат (т) = m 2 для натурального т, используя лишь операции сложения и вычитания. Вспомним формулу квадрата суммы и запишем ее для (т + 1)2:

т. е.

Перепишем теперь эту формулу, взяв вместо т выражение т — 1:

(записываем 2m как m + m, избегая умножений).

Добавив к этому равенству правило для вычисления значения квадрат (1), получим следующее соотношение:

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

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

алг нат факториал (нат п) нач кон алг нат квадрат (нат т) нач кон В этих алгоритмах значения функций выражаются через значения тех же функций от других аргументов. Такие алгоритмы называют рекурсивными.

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

1. Как используются вспомогательные алгоритмы вычисления значений функций?

Приведите примеру.

2. Как составляется заголовок алгоритма вычисления значений функции?

3. Для чего используется величина знач в алгоритме вычисления значений функции? Каков тип этой величины?

1. Напишите алгоритм вычисления значения выражения используя в качестве вспомогательного алгоритм вычисления значений функции abs(x).

2. Напишите алгоритм вычисления значений функции у = max4(a, b, с, d), значение которой равно большему из четырех ее аргументов.

3. Напишите алгоритм алг вещ больший (вещ таб а[1 : 100]), вычисляющий значения функции больший (а), значением которой является наибольший из элементов таблицы а.

4. Напишите алгоритм алг вещ сумма (вещ таб а[1 : 100]), вычисляющий сумму всех элементов таблицы a.

5. Используя алгоритм вычисления функции факториал (л) в качестве вспомогательного, напишите алгоритм вычисления суммы факториалов всех четных чисел от 2 до 100.

6. Напишите алгоритм нахождения приближенного значения функции у = sinx при малых значениях х по формуле 7. Напишите алгоритм, находящий: а) последнюю цифру десятичной записи натурального числа х; б) предпоследнюю цифру десятичной записи натурального числа х. При этом можно использовать алгоритм «остаток», имеющийся в библиотеке алгоритмов.

8. Напишите алгоритм, находящий сумму цифр десятичной записи трехзначного натурального числа х.

9. Напишите алгоритм, находящий сумму трехзначного числа N с трехзначным числом N, полученным из первого перестановкой его цифр в обратном порядке. (Например, если N = 123, то N = 321, а искомая сумма равна 444.) 10. Напишите алгоритм подсчета количества «счастливых» автобусных билетов.

(Билет называется счастливым, если сумма первых трех цифр номера билета равна сумме последних трех цифр.)

§9. АЛГОРИТМЫ РАБОТЫ С ЛИТЕРНЫМИ ВЕЛИЧИНАМИ

Мы уже рассматривали величины, значениями которых являются тексты: "нет решения", "ракета станет спутником Солнца", "удовлетворительно". Такие величины назывались литерными. Говоря о текстах, мы имеем в виду произвольные последовательности символов (необязательно имеющие смысл). Например, значением литерной величины может быть текст или текст До сих пор у нас не было никаких операций, которые выполнялись бы над литерными величинами. Сейчас мы введем несколько таких операций.

Операция соединения, или склеивания, обозначается знаком + и соединяет два текста в один. Например, Обратите внимание, что результат соединения текстов зависит от их порядка:

"345" + "12" = "34512".

Длиной текста называется количество букв в нем. Длина текста А обозначается длин (А).

Например, Существует текст длины 0, не содержащий ни одной буквы. Он обозначается двумя стоящими рядом кавычками "" и называется пустым текстом.

Будем считать, что буквы в тексте пронумерованы слева направо, начиная с единицы (табл. 16).

Еще одна операция над текстами, которую мы будем рассматривать, называется вырезкой. С ее помощью можно «вырезать» из текста фрагмент, указав номера первой и последней буквы. Например, если А = "информатика", то Фрагмент может содержать всего одну букву:

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

Приведем примеры таких алгоритмов.

П р и м е р 1. Написать алгоритм подсчета числа букв "а" в тексте.

алг цел число букв а (лит х) нач кон П р и м е р 2. Написать алгоритм обращения слова.

Поясним смысл этого алгоритма. Если, например, его аргументом является слово "кот", то результат — слово "ток", если аргумент — "акитамрофни", то результат — "информатика" и т. д.

Этот алгоритм может быть записан таким образом:

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

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

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

Например, при А = "квант" команда заменит часть слова "квант" с 4-й по 5-ю букву на "рк". После выполнения этой команды значением литерной величины А станет слово "кварк". При этом важно, чтобы новая часть слова имела ту же длину, что и старая. Например, команда не имеет смысла, так как часть слова с 7-й по 9-ю букву содержит ровно 3 буквы.

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

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

Мы познакомились с основными конструкциями алгоритмического языка в русском варианте (Русского Алгоритмического Языка — РАЯ). В разных республиках нашей страны и в других странах используемые в нем слова могут изменяться, но содержание основных конструкций будет одним и тем же. Конструкции алгоритмического языка служат основой языков программирования, применяемых при решении различных возникающих из практики задач на больших и малых ЭВМ. И хотя различные языки программирования имеют индивидуальные особенности, связанные с областью их применения, историей развития и т. д., основные конструкции этих языков являются «переводом»

конструкций нашего алгоритмического языка.

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

1. Как применяется операция соединения к литерным величинам? Приведите примеры.

2. Как применяется операция вырезки к литерным величинам? Приведите примеры.

3. Как применяется команда частичного изменения значения литерной величины?

Приведите примеры.

1. Пусть А = "компьютеризация". Найдите значения:

2. Составьте алгоритм подсчета суммарного числа букв "а" и букв "б" в данной литерной величине.

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

4. Составьте алгоритм, удваивающий каждую букву в заданном тексте (при этом, например, из слова "бейсик" должно получиться слово "ббееййссиикк").

5. Составьте алгоритм, выясняющий, является ли данное слово «перевертышем»

(так называются слова, читающиеся одинаково слева направо и справа налево, например:

ПОТОП, КАЗАК).

6. Составьте алгоритм, вычеркивающий из данного слова все буквы "а" (так, чтобы, например, из слова "заноза" получалось слово "зноз").

7. Составьте алгоритм, который каждую встреченную в слове букву "б" заменял бы сочетанием букв "ку" (так, чтобы, например, из слова "абракадабра" получалось слово "акуракадакура").

8. С помощью операций вырезки и склеивания составьте из частей слова "интеграл" слова "гантели", "рентген", "тигр", "агент".

9. Напишите алгоритм, проверяющий, является ли частью данного слова слово "сок". Ответ должен быть "да" или "нет". Например, для слов "сокол" и "кусок" ответ "да", а для слова "кокос" — "нет".

10. Напишите алгоритм, посчитывающий, сколько раз в данном слове встречается сочетание "со" (например, в слове "согласование" оно встречается 2 раза).

11. Напишите алгоритм, подсчитывающий, сколько раз в данном слове х встречается (в качестве его части) данное слово у. Если слово у длиннее, чем х, то результат должен быть равен нулю. Примеры: если х = "аттестат", у = "т", результатом должно быть число 4;

если х = "абракадабра", у = "бра" — результат равен 2; если х = "забой", у = "еж" — результат равен 0; если х = "ааааа", у = "ааа", то результат равен 3.

12. В примере 2 поменяйте местами «слагаемые» в команде присваивания, т. е. команду замените командой а) Пусть аргументом этого алгоритма является слово "школа". Что будет результатом?

б) Что будет результатом применения этого алгоритма к произвольному слову?

ЯЗЫК ПРОГРАММИРОВАНИЯ РАПИРА

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

Язык программирования Рапира разработан в начале 80-х годов в СССР для использования в школьном курсе информатики. Школьные компьютеры снабжены программами, позволяющими им исполнять алгоритмы, записанные на этом языке. Вместе с тем этот язык имеет широкие возможности, позволяющие составлять сложные производственные программы. Здесь описаны только некоторые простейшие элементы языка Рапира. Его конструкции близки к соответствующим конструкциям алгоритмического языка. Поэтому в большинстве случаев мы будем вводить их по аналогии с известными элементами алгоритмического языка.

§ 10. ЗАПИСЬ АЛГОРИТМОВ В ВИДЕ ПРОЦЕДУР

НА РАПИРЕ

Чтобы познакомиться с языком Рапира, рассмотрим какой-нибудь известный нам из первой части учебника алгоритм (например, алгоритм решения квадратного уравнения) и сравним его записи на алгоритмическом языке и на Рапире. На алгоритмическом языке он запишется так:

алг решение квадратного уравнения (вещ а, b, с, х1, х2, лит у) нач вещ D кон Теперь запишем этот алгоритм на языке Рапира:

ПРОЦ РЕШЕНИЕ КВАДРАТНОГО УРАВНЕНИЯ

ИМЕНА: D НАЧ КОН Мы видим, что записи этих алгоритмов похожи, но есть и некоторые отличия. Перечислим основные из них.

1. В программах на алгоритмическом языке употреблялись любые буквы (латинские и греческие), математические знаки и т. п. Поскольку на клавиатуре компьютеров есть не все из этих букв, то алфавит языка Рапира ограничен: можно использовать только русские и латинские буквы. Кроме того, переменные с индексами записываются в одну строку: х1 пишется как XI и т. п.

2. По тем же причинам возведение в степень обозначается двумя звездочками, умножение — одной, а квадратный корень из числа х записывается как SQRT(X) (сокращение английских слов square root — квадратный корень), деление обозначается /.

3. Вместо служебного слова алг используется слово ПРОЦ (сокращение от «процедура»). Процедурой называется и сама запись алгоритма на Рапире.

4. В названии алгоритма отдельные слова соединены черточками (символами подчеркивания). Имена в Рапире (названия алгоритмов, переменных и т. п.) должны представлять собой последовательность букв, цифр и символов подчеркивания ( ) и не должны содержать пробелов. Такое соглашение помогает компьютеру не спутать имя "РЕШЕНИЕ _ КВАДРАТНОГО _ УРАВНЕНИЯ" с написанными подряд тремя именами "РЕШЕНИЕ", "КВАДРАТНОГО" и "УРАВНЕНИЯ".

5. Нет отдельных списков аргументов и результатов (арг а, b, с или рез х1, х2, у).

Вместо этого в перечислении величин в заголовке процедуры (их называют параметрами процедуры) ставится стрелка => (состоящая из двух символов = и > ) перед аргументами и после результатов. (Если какая-то величина Z является и аргументом, и результатом алгоритма, то мы стрелку ставим и до, и после: = > Z = >.) Указание аргументов и результатов алгоритма с помощью стрелок удобно, так как избавляет от необходимости повторно писать имена параметров. Тем самым уменьшается вероятность ошибки.

6. В заголовке процедуры на Рапире не указаны типы параметров А, В, С, XI, Х2 и Y. Это одна из особенностей Рапиры. Дело в том, что в Рапире одна и та же величина может в разные моменты времени принимать значения различных типов. Другими словами, типы имеют не сами величины, а их значения.

Хотя в заголовке процедуры и не указано, что А, В, С должны принимать числовые значения, попытка применить процедуру, например, к литерным значениям величин А, В, С приведет к ошибке: при вычислении значения выражения В2 4АС выяснится, что операции возведения в квадрат и умножения неприменимы к литерным значениям.

7. По той же причине запись вещ D заменена записью ИМЕНА: D, не конкретизирующей тип промежуточной величины D.

8. Команды повторения и выбора пишутся на Рапире так же, как и на алгоритмическом языке, только с использованием заглавных букв при записи служебных слов.

1. Приведите примеры различий между алгоритмическим языком и языком Рапира.

Чем объясняются эти различия?

2. Как указываются аргументы и результаты алгоритма в записи на алгоритмическом языке и на Рапире?

1. Запишите выражение на языке Рапира.

2. Заголовок алгоритма, записанного на Рапире:

Укажите аргументы и результаты этого алгоритма.

3. Арифметическое выражение имеет вид:

Запишите на Рапире команду, которая вычисляет значение этого выражения и присваивает его переменной с именем ВЕЛИЧИНА.

4. Запишите на Рапире команду, которая вычисляет величину h по формуле:

5. Составьте описание процедуры РАССТОЯНИЕ, которая имеет в качестве аргументов координаты двух точек: (XI, Yl), (X2, Y2) и вычисляет расстояние между этими точками.

6. Напишите процедуру с заголовком ПРОЦ ПРОВЕРКА (= > Р, = > Q, = > R, Z = > ), где Р, Q, R — коэффициенты квадратного уравнения, a Z — литерная переменная, принимающая одно из трех значений:

"КОРНИ ОДНОГО ЗНАКА",

"КОРНИ ПРОТИВОПОЛОЖНЫХ ЗНАКОВ",

"ВЕЩЕСТВЕННЫХ КОРНЕЙ НЕТ".

Предусмотрите вызов процедуры РЕШЕНИЕ_КВАДРАТНОГО_УРАВНЕНИЯ внутри описания процедуры ПРОВЕРКА.

Процедура ПРОВЕРКА должна вычислять корни и, если они существуют, выяснять совпадение и несовпадение их знаков.

§11. ЗАПИСЬ АЛГОРИТМОВ ВЫЧИСЛЕНИЯ

ЗНАЧЕНИЙ ФУНКЦИЙ НА РАПИРЕ

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

алг нат НОД (нат т, нат п) нач нат х, у знач := х кон Напомним, что этот алгоритм называется алгоритмом Евклида и основан на том, что На Рапире этот алгоритм будет выглядеть так:

ФУНК НОД (М, N) ИМЕНА: X, Y НАЧ КОН Отметим некоторые особенности записи.

1. В этом примере вместо служебного слова алг используется не слово ПРОЦ (процедура), а слово ФУНК (функция). Это объясняется следующим. В алгоритмическом языке алгоритмы вычисления значений функций отличаются тем, что после слова алг в них указывается тип значений функции (в данном случае нат). В Рапире тип значений функции заранее не указывается. Вместо этого алгоритмы вычисления функций начинаются со слова ФУНК, что выделяет их среди остальных.

2. Как и в алгоритмическом языке, аргументы М и N функции НОД не нуждаются в специальном указании, что они являются аргументами, и стрелки перед ними не ставятся.

3. Вместо знака используется комбинация знаков / =. Аналогично вместо знаков ; и используются комбинации знаков < = и > =.

Приведем еще один пример записи алгоритма вычисления функции.

ФУНК ПЛОЩАДЬ (А, В, С)

ИМЕНА: ПОЛУПЕРИМЕТР

НАЧ

(ВЫЧИСЛЯЕТ ПЛОЩАДЬ ТРЕУГОЛЬНИКА СО СТОРОНАМИ А, В, С

ПО ФОРМУЛЕ ГЕРОНА)

ПОЛУПЕРИМЕТР: = (А + В + С)/ ЗНАЧ : = SQRT (ПОЛУПЕРИМЕТР(ПОЛУПЕРИМЕТР — А) КОН В этой записи текст, заключенный в скобках между звездочками, предназначен для человека, читающего программу. Исполнитель же программы (компьютер) пропускает части текста программы, заключенные между «(» и «)».

1. Как записываются алгоритмы вычисления значений функций на языке Рапира?

Приведите пример.

2. Почему возникает необходимость использовать в языке Рапира два слова — ФУНК и ПРОЦ — вместо одного слова алг в алгоритмическом языке?

1. Запишите на языке Рапира алгоритм вычисления функции МАХ2(М, N), значение которой равно большему из чисел М и N. Заголовок должен быть таким:

2. Используя алгоритм предыдущего упражнения как вспомогательный, запишите алгоритм вычисления значений функции МАХ3(М, N, S), значение которой равно большему из трех чисел М, N и S.

3. Опишите алгоритм вычисления функции, значение которой равно числу букв "A" в заданном тексте СЛОВО.

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

а) число вхождений любой буквы, заданной в качестве аргумента алгоритма, в тексте СЛОВО;

б) процентный состав задаваемой буквы в тексте СЛОВО.

5. Опишите функцию ДЕНЬНЕДЕЛИ, которая по аргументу ДЕНЬ — литерной величине, принимающей значение "ПОНЕДЕЛЬНИК", "ВТОРНИК",..., "ВОСКРЕСЕНЬЕ", вычисляет номер дня недели — целое число 1, 2,..., 7 соответственно.

Воспользуйтесь командой ВЫБОР.

Табличные величины называются в Рапире кортежами. Элементы кортежа нумеруются всегда с единицы. Правила Рапиры позволяют записывать кортежи в виде списка элементов, разделенных запятыми и заключенных в угловые скобки < и >. Например, после выполнения команды значением переменной величины А станет такой кортеж (таблица) из пяти элементов:

Как и в алгоритмическом языке, через A[N] в Рапире обозначается N-й элемент кортежа (таблицы) А.

Длина кортежа X обозначается ДЛИН(Х) (так же как и длина текста). Используя введенные обозначения, составим алгоритм суммирования всех элементов кортежа:

ФУНК СУММА(X) (СУММА ВСЕХ ЭЛЕМЕНТОВ КОРТЕЖА)

ИМЕНА: К НАЧ КОН Элементами кортежа могут быть не только числа. Например, выполнив команду ИМЯ_МЕСЯЦА := ("ЯНВАРЬ", "ФЕВРАЛЬ", "МАРТ", "АПРЕЛЬ", "МАЙ", "ИЮНЬ", "ИЮЛЬ", "АВГУСТ", "СЕНТЯБРЬ", "ОКТЯБРЬ", "НОЯБРЬ", "ДЕКАБРЬ"), мы получим кортеж ИМЯ_МЕСЯЦА, для которого ДЛИН(ИМЯ_МЕСЯЦА) = 12, причем ИМЯ_МЕСЯЦА[ К ] будет названием К-го месяца года, например:

ИМЯ_МЕСЯЦА [ 9] = "СЕНТЯБРЬ" Элементами кортежа могут быть и другие кортежи. Например, после выполнения команды значением А[ 1 ] является кортеж, а значением А[ 2 ] — кортеж. Тем самым А[ 1 ] [ 1 ] означает первый элемент кортежа А[ 1 ] (т. е. кортежа ) и, следовательно, А[ 1 ] [ 1 ] = 1. Аналогичным образом Такие «кортежи кортежей» заменяют в Рапире прямоугольные таблицы, имеющиеся в алгоритмическом языке. Приведенный пример кортежа <, > соответствует таблице Таблица а [ 1 : m, 1 : п] изображается в Рапире в виде кортежа из т элементов, каждый из которых является кортежем из п элементов. Подчеркивая сходство «кортежа кортежей» с прямоугольными таблицами, в Рапире разрешают наряду с A[I].[J] писать А [ I, J].

Применение кортежей проиллюстрируем на примере. Пусть у нас имеется список класса с указанием оценок по истории, по математике и по информатике за IX класс. Запишем сведения о каждом ученике в виде кортежа:

Например, кортеж содержит информацию о том, что ученик по фамилии Сорокин имеет четверку по истории, пятерку по математике и четверку по информатике. А весь список запишется в виде кортежа, элементы которого — кортежи, содержащие сведения о каждом из учеников.

Например, список (табл. 17) будет представлен в виде кортежа:

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

ПРОЦ КРУГЛЫЕ_ОТЛИЧНИКИ( => СПИСОК, ЧИСЛО => ) ИМЕНА : НОМЕР НАЧ

ДЛЯ НОМЕР ОТ 1 ДО ДЛИН (СПИСОК)

КОН Применяя эту процедуру к нашему списку, получим в ответе 2 (в этом списке двое круглых отличников — Макаров и Полякова).

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

ПРОЦ ОТЛИЧНИКИ( => СПИСОК, ЧИСЛО => ) ИМЕНА:НОМЕР НАЧ

ДЛЯ НОМЕР ОТ 1 ДО ДЛИН (СПИСОК)

ЕСЛИ СПИСОК [НОМЕР] [2] = 5 ИЛИ КОН Выполнив эту процедуру в применении к нашему списку, получим в ответе 5 (все ученики, кроме Вербицкого и Кириллова, имеют хотя бы одну пятерку).

Среднюю оценку по информатике можно подсчитать так:

ПРОЦ СРЕДНЯЯ ( = > СПИСОК, ОЦЕНКА = > ) ИМЕНА : НОМЕР, СУММА НАЧ СУММА:=

ДЛЯ НОМЕР ОТ 1 ДО ДЛИН (СПИСОК)

СУММА : = СУММА + СПИСОК [НОМЕР] [4] ОЦЕНКА := СУММА/ДЛИН (СПИСОК) КОН Результатом исполнения этого алгоритма будет средняя оценка «4».

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

а соединяя два кортежа и, получаем кортеж :

1. Что соответствует в Рапире имеющимся в алгоритмическом языке табличным величинам?

2. Могут ли быть элементами кортежа: а) литерные величины; б) кортежи?

3. Какие операции над кортежами вам известны?

1. Составьте процедуру вычисления произведения всех элементов кортежа. Его заголовок должен иметь вид:

ФУНК ПРОИЗВЕДЕНИЕ (X)

(*ПРОИЗВЕДЕНИЕ ВСЕХ ЭЛЕМЕНТОВ КОРТЕЖА X*)

2. Чему равно А [3], если 3. Составьте процедуру, определяющую по списку класса (в форме кортежа) число учеников, у которых отметка по математике ниже отметки по информатике.

4. Элементами кортежа ЧИСЛА являются числовые величины. Найдите наименьший из элементов кортежа.

5. В условии предыдущей задачи найдите номер наименьшего элемента.

6. Кортеж КЛАСС состоит из кортежей пар. Первый элемент пары — литерная величина, значением которой является фамилия школьника, а второй — литерная величина, принимающая значение "А" для мальчиков и значение "Б" для девочек.

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

7. Шахматную доску можно представить в виде кортежа кортежей. Кортеж ДОСКА состоит из 8 кортежей — горизонталей. Каждый кортеж — горизонталь — в свою очередь состоит из 8 элементов — полей.

Напишите процедуру ЛАДЬЯ, аргументами которой являются два целых числа М и N, между 1 и 8 — номер горизонтали и номер вертикали поля. Эта процедура должна «пометить» все поля, побиваемые ладьей, стоящей на поле (М, N). «Пометить» поле — это значит присвоить единицу соответствующему элементу — полю. В исходном состоянии все элементы — поля содержат нулевые значения.

§ 13 КОМАНДЫ ВВОДА И ВЫВОДА НА РАПИРЕ

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

Для ввода исходных данных в компьютер пользуются клавиатурой, а для вывода результатов работы программы — экраном дисплея. В языке Рапира имеются следующие команды ввода данных с клавиатуры. По команде работа программы приостанавливается, и мы имеем возможность ввести в компьютер желаемое значение. Пусть, например, мы нажали клавиши А, Б, В,а затем специальную клавишу, сигнализирующую о завершении ввода. После этого исполнение программы продолжается, причем переменная величина X принимает литерное значение "АБВ". Если вместо клавиш А, Б, В мы нажмем клавиши 5 и 7 (и после этого нажмем специальную клавишу, сообщающую компьютеру об окончании ввода), то величина X примет литерное значение "57". Если же мы хотим, чтобы вводимые данные рассматривались как числа, то применяем команду

ВВОД ДАННЫХ : X

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

ВВОД ДАННЫХ : ПИ

нужно нажать последовательно клавиши и клавишу, сообщающую об окончании ввода, после чего ПИ примет значение 3,1416.

(Обратите внимание, что в языке Рапира, как и в других языках программирования, для отделения целой части числа от дробной применяется не запятая, а точка!) Приведем пример использования команд ввода на примере программы отыскания наибольшего общего делителя:

ПРОЦ НАИБОЛЬШИЙ_ОБЩИЙДЕЛИТЕЛЬ

ИМЕНА: А, В НАЧ

ВЫВОД: "ВВЕДИТЕ ПЕРВОЕ ЧИСЛО"

ВВОД ДАННЫХ: А

ВЫВОД: "ВВЕДИТЕ ВТОРОЕ ЧИСЛО"

ВВОД ДАННЫХ: В

ВЫВОД: "НОД РАВЕН" ВЫВОД: НОД (А, В) КОН Наряду с командами ввода, эта программа использует команды вывода. Команда выводит на экран значение X. (При этом нет необходимости в двух отдельных командах вывода для чисел и текста, так как тип значений величины X машине известен.) Теперь проследим за работой программы.

Исполнение программы начинается с выполнения первой команды. Это команда вывода. На экране появляется текст

ВВЕДИТЕ ПЕРВОЕ ЧИСЛО

Затем выполняется команда ВВОД ДАННЫХ: А и работа программы приостанавливается до тех пор, пока мы не введем число с клавиатуры. Нажмем клавиши 1, 2, 3., соответствующие цифры появятся на экране:

ВВЕДИТЕ ПЕРВОЕ ЧИСЛО

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

ВВЕДИТЕ ПЕРВОЕ ЧИСЛО

ВВЕДИТЕ ВТОРОЕ ЧИСЛО

Нажимаем клавиши 3, 2, 1. На экране появляется текст:

ВВЕДИТЕ ПЕРВОЕ ЧИСЛО

ВВЕДИТЕ ВТОРОЕ ЧИСЛО

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

ВВЕДИТЕ ПЕРВОЕ ЧИСЛО

ВВЕДИТЕ ВТОРОЕ ЧИСЛО

На этом исполнение программы заканчивается.

Обратите внимание, что приведенная программа использует вспомогательный алгоритм вычисления функции НОД(А.В). Этот алгоритм должен быть заранее сообщен компьютеру.

1. Для чего применяются команды ввода и вывода?

2. Как выполняются команды ввода и вывода?

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

2. Составьте программу, которая вводила бы две литерные величины и выводила бы их соединение.

3. Программа должна ввести два числа — координаты левого нижнего угла прямоугольника, а затем еще два числа — координаты правого верхнего угла этого прямоугольника. После этого программа запрашивает у ученика значение периметра этого прямоугольника и в зависимости от введенного значения либо хвалит ученика, выводя текст "МОЛОДЕЦ", либо сообщает о неверном результате, выводя текст "НЕВЕРНО". Составьте такую программу.

4. На соревнованиях по прыжкам в высоту установлена квалификационная норма — 180 см. По программе надо ввести фамилию спортсмена и взятую им высоту.

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

5. Перепишите процедуру

РЕШЕНИЕКВАДРАТНОГО_УРАВНЕНИЯ

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

ЯЗЫК ПРОГРАММИРОВАНИЯ БЕЙСИК

В этом разделе мы познакомимся с языком программирования Бейсик.

Язык программирования Бейсик был создан в США более двадцати лет назад. В настоящее время Бейсик — один из самых распространенных в мире языков программирования на персональных компьютерах.

1. Общий вид программы на Бейсике. Программа на языке Бейсик состоит из последовательности строк. Каждая строка начинается целым числом — номером строки; за номером строки следует команда языка Бейсик. (Правила Бейсика допускают несколько команд в одной строке. В этом случае команды отделяются друг от друга двоеточием.) Приведем пример Бейсик-программы:

5 CLS 10 t = 36. 20 text $ = "ТЕМПЕРАТУРА " 30 PRINT text $ 40 PRINT t Из этого примера видно, что в языке Бейсик в основном используются буквы латинского алфавита и английские названия команд. Приведенная программа содержит пять строк по одной команде в каждой. Строка с номером 5" содержит команду очистки экрана дисплея CLS (clear screen — очистить экран). В строке 10 содержится уже знакомая нам команда присваивания. В отличие от алгоритмического языка в Бейсике вместо знака «:

=» в команде присваивания применяется знак равенства « = ». Строка 20 содержит команду присваивания для литерной переменной. Строки 30 и 40 содержат две команды печати PRINT. Первая выводит на экран значение указанной в ней литерной переменной text$, а вторая — значение вещественной переменной t. В результате этой программы на экране будут напечатаны две строки:

ТЕМПЕРАТУРА

Замечание. Строки в Бейсике необязательно нумеровать подряд. Важно лишь, чтобы номера шли в возрастающем порядке. Однако обычно строки нумеруются с интервалом в 10:

2. Константы и переменные в языке Бейсик. Как и в алгоритмическом языке, в Бейсике величины делятся на переменные и постоянные (константы); каждая величина может быть целого, вещественного или литерного типа. Постоянные величины в Бейсике записываются так же, как и в алгоритмическом языке. Единственное отличие — в способе записи десятичных чисел. В Бейсике для отделения целой части от дробной пользуются не запятой, а точкой (например, 12.5, 0.5, 3.1415926 и т. д.). Это правило принято практически во всех языках программирования. Тип константы ясен из ее записи. Например, 2, 3, — 1 — целые числовые константы, 2.0, 36.6, 3.14 — вещественные, а "сколько ему лет?", "введите число", "есть решения", "абвгдежзикля" — литерные. В отличие от алгоритмического языка в Бейсике тип переменной определяется по ее имени. Если имя оканчивается знаком % — переменная целого типа; если знаком $ — литерного типа, во всех остальных случаях — вещественного. Например, среди величин три первые — вещественные, две следующие — литерные, две последние — целые.

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

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

Номер элемента табличной величины, в отличие от алгоритмического языка, в Бейсике записывается в круглых скобках. Например, строка содержит команду присваивания 4-му элементу таблицы А значения 36.6.

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

Для литерных переменных в Бейсике разрешено использовать только одну операцию — соединение текстов. Эта операция обозначается знаком +. Например, В выражениях языка Бейсик, как и в алгоритмическом языке, можно использовать названия функций, например:

Бейсик — язык программирования, и алгоритмы, записанные с его помощью, предназначены для ввода в ЭВМ. Поэтому для записи алгоритмов на языке Бейсик можно использовать только те символы, которые есть на клавиатуре ЭВМ. Это почти все символы, которыми мы привыкли пользоваться в математике (кроме греческих букв); операция извлечения квадратного корня (а) обозначается SQR(a); знака «не равно» () на клавиатуре тоже нет, и выражение а b записывается: а < > b, т. е. с помощью двух знаков:

«меньше» ( ).

Еще некоторые отличия в записи вы заметите сами; все они связаны с заменой отсутствующих на клавиатуре символов имеющимися, требованием записи символов в одну строку и английским «происхождением» этого языка.

1. Команда ветвления. Так же как и в алгоритмическом языке, в Бейсике есть команда ветвления. Ее общий вид следующий:

В этой команде участвуют английские слова IF, THEN, ELSE, которым соответствуют русские слова если, то, иначе. Выполняется эта команда аналогично команде ветвления в алгоритмическом языке.

Приведем пример:

После исполнения этой программы вещественная переменная а будет равна 5, если условие соблюдается (т. е. а > Ь), во всех иных случаях переменной а будет присвоено значение 10.

Условия в Бейсике записываются так же, как в алгоритмическом языке; отличия видны из таблицы 19.

Алгоритмический означает, что 5 < х 7.

2. Команда повторения в Бейсике бывает двух типов. Первый из них аналогичен команде повторения пока — нц — кц в алгоритмическом языке. Вот пример использования этой команды:

10 DIM A(I0) 15 1% = 20 WHILE I% < 30 А(1%) = 35 1% = 1% + 40 WEND Приведенная программа заполняет нулями линейную таблицу из десяти элементов.