Давыдов В.Г. - Программирование и основы алгоритмизации - 2003

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

А,В,С,

напечатать для контроля введенные данные, вычислить и напечатать

Система команд	Е=АВ	+ С/\,5
	машины	П М содержит несколько десятков
различных одноадресных	команду	из которых в табл. 2 приводятся

лишь те, которые будут необходимы для решения указанной задачи.

	Табл. 2. Таблица кодов операций (КОП)
КОП	Выполняемое действие (обозначение команды)

01Передача слова из ОЗУ в регистр А арифметико-логического устройства АЛУ (ЧТЕНИЕ)

02 Передача слова из регистра А АЛУ в ОЗУ (ЗАПИСЬ)

03Слолсение содержимого регистра А АЛУ с операндом, заданным в команде. Результат помещается в регистр А АЛУ (+)

04 Вычитание ( - ). Операция выполняется аналогично сложению 05 Умножение ( * ).Операция выполняется аналогично сложению 06 Деление ( / ).Операция выполняется аналогично сложению 07 Ввод слова с устройства ввода в ОЗУ (ВВОД)

08 Вывод слова из ОЗУ в устройство вывода (ВЫВОД)

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

языке требуется решить следующие		вопросы:
1. Распределить память для		данных, обрабатываемых про­
граммой, например, в начале памяти (табл. 3)
	Табл. 3. Таблица символов (ТС)
Имя переменной	Адрес в ОЗУ (для удобства используется десятичный адрес
	вместо двоичного адреса)
А		00000
В		00001
С		00002
"1,5"		00003
Е		00004

2. Распределить память для команд программы. Например, ус­ ловимся размещать программу, начиная с адреса 01000 (для удобст­ ва используется десятичный адрес вместо двоичного адреса).

3. Составить собственно программу, т.е. записать коды ма­ шинных команд с указанием места их размещения в ОЗУ. Напоми ­ наем, что реально в Э В М используются двоичные коды команд и

10

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

Проанализировав содержимое табл. 3, оценим возможности и особенности программирования на машинных языках.

В оперативном запоминающем устройстве (ОЗУ) между ме­ стом размещения данных и команд программы осталась "дырка" - ячейки с адресами 00005...00999, которую для полного использова­ ния памяти нужно ликвидировать. Однако заранее оценить размер памяти, необходимой для размещения данных и команд, нельзя или, по крайней мере, очень трудно.

Табл. 4. Машинная программа

1 Адрес	КОП	Адрес	Действие команды
команды	07	операнда
01000		00000	УВв -> ОЗУ по адресу 000000 (А)
01001	08	00000	Содержимое ячейки ОЗУ с адресом 00000 (А) - ^ УВыв
01002	07	00001	УВв -> ОЗУ по адресу 000001 (В)
01003	08	00001	Содержимое ячейки ОЗУ с адресом 00001 (В) —> УВыв
01004	07	00002	УВв -> ОЗУ по адресу 000002 (С)
01005	08	00002	Содержимое ячейки ОЗУ с адресом 00002 (С) —> УВыв
01006	01	00002	Содержимое ячейки ОЗУ с адресом 00002 (С) -^
			регистр А АЛУ
01007	06	00003	Содержимое регистра А АЛУ (С) разделить на
			содержимое ячейки ОЗУ с адресом 00003 (1.5) и
01008	02	00004	результат поместить в регистр А АЛУ
			Содержимое регистра А АЛУ (С/1.5) - ^ ОЗУ по адресу
01009	01	00000	00004 (Е)
			Содержимое ячейки ОЗУ с адресом 00000 (А) —>
			регистр А АЛУ
01010	05	00001	Содержимое регистра А АЛУ (А) умножить на
			содержимое ячейки ОЗУ с адресом 00001 (В) и
			результат поместить в регистр А АЛУ
01011	03	00004	Содержимое регистра А АЛУ (А*В) сложить с
			содержимым ячейки ОЗУ с адресом 00004 (С/1.5) и
01012	02	00004	результат поместить в регистр А АЛУ
			Содержимое регистра А АЛУ (А*В+С/1.5) -^	ОЗУ по
			адресу 00004 (Е)
01013	08	00004	Содержимое ячейки ОЗУ с адресом 00004 (А*В+С/1.5)
			-^ УВыв	1

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

Другие недостатки программирования с использованием ма­ шинного языка заключаются в следующем.

1. Действия, указанные в пп. 1 - 2 нетворческие, поэтому при их выполнении программист делает много ошибок. Вместе с тем их можно автоматизировать с помош;ью ЭВМ.

11

2. Реальные системы команд ЭВМ громоздки (сотни различ­ ных команд), а использование двоичных кодов команд программы трудоемко и ненаглядно. Машинную программу трудно восприни­ мать (см. табл. 4 без левого и правого столбцов).

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

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

1.2.2. Ассемблерные языки (на примере ПМ-ассемблера)

Ассемблерные языки отличаются от соответствующих машин­ ных языков следующими особенностями:

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

2. Размещение в ОЗУ данных и команд также автоматически выполняет ЭВМ, причем без "дырок". Действия, указанные в пп. 1 - 2 выполняет специальная системная программа-переводчик, назы­ ваемая транслятором (компилятором).

3. Оптимальность программы по быстродействию и занятой памяти практически сохраняется (проигрыш не более 5... 10 %). Это делает ассемблерные языки практически основными для системных программистов.

Пример программы на языке ПМ-ассемблер, подобный приме­ ру из подразд. i.2.1, приведен в [1] в разд. 7 (см. прилагаемый ком­ пакт-диск).

Перевод (перекодировка) ассемблерной программы на язык машинных команд производится транслятором по следующей схеме (рис. 1). Трансляция выполняется в два прохода.

Проход 1. Составляется таблица символов (ТС).

Проход 2. Выполняется перекодировка команд в двоичные ко­ ды (используются ТК и ТС).

1.2.3. Макроассемблерные языки

Макроассемблерные языки сейчас являются самыми мощными. Объясняется это тем, что макроассемблер обладает всеми возмож-

12

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

Пример. Предположим, что часто встречается вычисление

R^{X^+Y^)/{X'Y)

Текст программы	Таблица кодов
на ассемблере	операций (ТК)
	Таблица
	символов (ТС)

Текст программы на машинном языке

Рис. 1. Схема трансляции в два прохода

Соответствующая группа машинных команд оформляется в виде макроопределения, имеющего следующую структуру:

[Г 2		10	11	20 21	40
к	МЕТКА		ОПЕРАЦИЯ ОПЕРАНД		КОММЕНТАРИЙ
к	Стандартное			начало, MACRO	- ключевое слоъо,	SUB(X, Y, R) -

Кпридумывает программист

MACRO	SUB(X,	Y, R)
ЧТЕНИЕ	X	Тело

*	X
ЗАПИСЬ	Х2
ЧТЕНИЕ	Y
*	Y
+	Х2
/	X
/	Y	макроопределения
ЗАПИСЬ	R

MEND	Стандартный конец
Пусть, например, необходимо вычислить
С = (А^+В')/(А-В)	и G-={E^+F^)/(E-F)

Это можно сделать в программе с помощью однострочных

макровызовов:

13

2	10	11	20	21	40	41
МЕТКА		ОПЕРАЦИЯ		ОПЕРАНД		КОММЕНТАРИЙ
		S U B ( A ,	В ,	С)
		S U B ( E ,	F ,	G)

Здесь X, Y, R - формальные, а А, В, С и Е, F, G - фактические параметры. Вызов "SUB(A, В, С) " заменяется фактически модифици­ рованным телом макроопределения, в котором формальные пара­ метры X, Y, R заменены соответственно фактическими параметрами

Л, В, С.

Макроассемблер - основной язык системных программистов. В частности, программист может, при необходимости, разработать свой набор макроопределений - это эквивалентно разработке в рам­ ках макроассемблера "своего", специализированного языка с опера­ торами - макровызовами. При этом сохраняется высокая эффектив­ ность программ, написанных на макроассемблере. Проигрыш по бы­ стродействию и занятой памяти не превышает 10... 15 %.

1.2.4. Машинно-независимые языки. Процедурные и универсальные языки

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

/'*'

пример

на

языке

Си,

Вычисляем

D

:=

А *

В

+

С / 2

.

0

*

/

^include

(

<stdio.h>

±nt

main

void

)

{

float

Л,

B, C,

D;

"

%f

&B,

&C )

;

scanf(

%f

%f",

&A,

printf(

"

%f %f

%f".

A, B,

С ) ;

D=A*B+C/2.0;

%f",

D

) ;

printf(

"\n

return

0;

PROGRAM

PEMPAS

(

INPUT,

OUTPUT

)

;

{ Пример

на

языке

ПАСКАЛЬ.

Вычисляем

D

: =

A

* B

+

C

/

2

. 0 }

|

VAR

А ,

Б ,

С ,

D:

REAL;

BEGIN

{

Для

PRMPAS

READ(

А,

В,

С )

;

WRITE(

А,

В,

С

)

;

D :=

А

^

В

+

С

/

2.0;

WRITE(

D

)

END.

{

Для

PRMPAS

14

PROGRAM

PRMF7

7

С Пример

для

языка

ФОРТРАН?

7. Вычисляем

D

: =

A

' ^

B

- h C

/ 2 . 0

REJLL

А,

В,

С ,

D

READ

*г

^f

Br

С

PRINT

*r

А,

В,

С

D

=

А

^

В

+

С

/

2.0

PRINT

*,

D

STOP

END

100

REM

Пример

на

БЭИСИКе.

Вычисляем

D

: =

A

*

B

+

C / 2 . 0

110

INPUT

А,

В,

С

120

PRINT

А,

В,

С

130

PRINT

А

*

В

+

С /

2 .

0

140

END

\ / ^

Пример

на

языке

PL/1.

Вычисляем

D

:=

А

*

В

+

С

/

2.0

*/

PRMPL1:

PROCEDXmE

OPTIONS

(

MAIN

) ;

DECLARE

(

A,

Br

Cr

D

)

REAL

FLOAT

DEC

(

6

)

;

GET

LIST(

Ar

Br

С

)

;

PUT

LIST(

Ar

Br

С

)

;

D =

A

^

В

+

С

/

2.0

PUT

LIST

(

D

)

;

END

PRMPLl;

Из приведенных примеров видны удобства работы на машин­ но-независимых языках. По этой причине ясно, что языки програм­ мирования высокого уровня - основные языки проблемных програм­ мистов. Эффективность программ, написанных на языках высокого уровня, понижена в 2 - 4 раза. Для программ на языках Си/С++ по­ нижение эффективности составляет лишь 1,5 раза и объясняется это тем, что этот язык включает в себя многие средства ассемблерных языков.

ЧАСТЬ 1. БАЗОВЫЙ ЯЗЫК ПРОГРАММИРОВАНИЯ

2. ЯЗЫК ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ C++

Язык программирования Си был разработан в 1972 году Д. Ритчи в фирме Bell Laboratories (США) как универсальный язык системного программирования в связи с созданием популярной опе­ рационной системы UNIX. Эта операционная система (ОС) была, в основном, написана на языке Си, что обеспечило ее переносимость на любые ЭВМ. Действительно, для каждой архитектуры ЭВМ дос­ таточно написать только транслятор с языка Си и с его использова­ нием ОС UNIX легко переносится на новую ЭВМ, принадлежащую соответствующей архитектурной линии.

При разработке языка Си был принят компромисс мелсду низ­ ким уровнем языка ассемблера и высоким уровнем таких языков, как Паскаль, ФОРТРАН, БЭЙСИК, ПЛ/1 и др. Многие и многие опера­ ции языка Си (манипулирования строками, ввода-вывода и др.) вы­ несены за пределы языка и реализованы как подпрограммы, которые могут быть вызваны из Си-программ. Такое решение обеспечило

высокую эффективность языка Си (высокое быстродействие и ма­ лые затраты памяти).

Язык Си - современный язык, включающий управляющие кон­ струкции, рекомендуемые теоретическим и практическим програм­

мированием.	Такими	конструкциями являются	следование, ветвле­
ние, циклы;	модули,	называемые функциями.	Язык Си побуждает

программиста использовать в своей работе нисходящее проектиро­ вание, структурное программирование и пошаговую разработку мо­ дулей. В дополнение к сказанному, язык 0++, являющийся даль­ нейшим развитием языка Си, содержит такой важный инструмент, как средства объектно-ориентированного программирования (ООП).

Таким образом, если есть желание работать в среде програм­ мотехники, то один из первых вопросов, на который нужно ответить "Да" - это вопрос "Умеете ли Вы программировать на языках Си/С++?".

16

2.1. Введение. Структурное и модульное программирование

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

Что такое АЛГОРИТМ?		Как его записать?
	Аль Хорезми
Структурное		Дейкстра
программирование
Ветвления	Следование	Циклы
if - then - else		while
switch		do - while
		for

Рис. 2. Алгоритм и технология структурного программирования

Если посмотреть на верхнюю часть графического конспектарисунка, то внимание сразу привлекает слово АЛГОРИТМ.

2.1.1. Алгоритм и способы его записи

АЛГОРИТМ - одно из основных понятий современной матема­ тики и программирования. Само слово происходит от имени узбек­ ского математика IX в. Мухаммеда, уроженца Хорезма (по-арабски "Аль Хорезми"). Его работы по арифметике и алгебре были переве­ дены на латинский язык в XII в. и оказали большое влияние на раз­ витие математики в Европе. Сформулированные ученым правила выполнения четырех арифметических действий получили название "алгоризм", дальнейшая трансформация — "алгоритмус", "алгорифм" и "алгоритм". Интуитивное понятие алгоритма можно выразить сле­ дующим образом.

Алгоритм - строгая и четкая система правил, которая опреде­ ляет последовательность действий над некоторыми объектами и по-

17

еле конечного числа шагов приводит к достижению поставленной цели.

Примерами алгоритмов могут являться:

•рецепты приготовления блюд;

•пояснения, "как пройти", "как проехать";

•правило умножения целых чисел "столбиком" и т.п.

Вместе с тем, "школьная" таблица умножения не является ал­ горитмом.

Способы записи алгоритмов. Один и тот же алгоритм может быть записан (описан) различными способами. Наибольшее распро­ странение в практике программирования получили [2]:

•текстуальная (словесная) запись алгоритма;

•запись алгоритма с помощью схемы (разновидность визуального

способа -	формализма);		диаграммы	Нэсси-
• запись	алгоритма с	использованием
Шнейдермана (разновидность визуального			формализма);

•запись алгоритма с использованием Р-схемы (разновидность ви­ зуального формализма);

•запись алгоритма с помощью псевдокода^

•запись алгоритма в терминах языка программирования.

Эти способы записи алгоритмов не исключают друг друга, а используются последовательно, на различных этапах решения зада­ чи. Только три способа записи алгоритма — с использованием схемы, диаграммы Нэсси-Шнейдермана и Р-схемы - являются альтернатив­ ными на соответствующем этапе решения задачи.

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

Текстуальная запись алгоритма. Имеется следующий алго­ ритм, записанный в текстуальной форме:

1.Начало алгоритма.

2.Выполнить некоторое действие (оператор) si.

3.Если выполнено условие "Усл1", то выполнить операторы s2, s3 и перети к п. 4. Иначе - перейти к пп. 3.1.

3.1.Пока выполняется условие "Усл2", выполнять пп. 3.2 и 3.3. Иначе - перейти к п. 4.

3.2.Если выполнено условие "УслЗ", то выполнить опера­ тор s4, иначе — выполнить оператор s5.

3.3.Выполнить оператор s6.

4.Пока выполняется условие "Усл4", выполнять оператор s7. Иначе — перейти к п. 5.

5.Выполнить оператор s8.

6.Конец алгоритма.

18

Запись алгоритма с помощью схемы (ГОСТ 19.701 - 90, со­ вместим с меэюдународным стандартом). Запись того же самого алгоритма в виде схемы иллюстрирует рис. 3.

В случае простой схемы сравнительно несложно обеспечить ее бесспорную наглядность. Но по мере роста сложности отображаемо­ го фрагмента алгоритма (программы), его логическая структура на­ чинает "тонуть" в "клубке спагетти", в который постепенно превра­ щается схема алгоритма [2]. Поэтому практика использования схем алгоритмов уже давно считается устаревшей и программисты при­ меняют ее как инструмент разработки только эпизодически. Там, где стандарты организации требуют наличия схем алгоритмов, они поч­ ти неизменно рисуются после написания программы.

Запись алгоритма с помощью диаграммы Нэсси-Шнейдермана (рис. 4). Диаграмма Нэсси-Шнейдермана была предложена в сочета­ нии со структурным программированием как средство борьбы с проблемой "клубка спагетти", присущей схемам алгоритмов. Эта диаграмма, бесспорно, заменяет одномерное представление вложен­ ных операторов двумерным (см. рис. 4). Тем не менее, по мере роста сложности программного кода появляются проблемы отображения, поскольку элементы диаграммы быстро становятся все меньше и меньше. На рис. 4 приведена диаграмма Нэсси-Шнейдермана для того же самого алгоритма, что и ранее.

Запись алгоритма с помощью Р-схемы (рис. 5). Используемая при этом Р-технология программирования разработана в Институте Кибернетики АН УССР. Согласно Р-технологии программа должна быть представлена в форме нагруженного по дугам структурного графа (Р-схемы). Р-схема состоит из подграфов, каждый из которых имеет один вход и один выход. Вершины графа называются состоя­ ниями Р-схемы. Переходы из одного состояния в другое представ­ лены помеченными дугами, причем каждая дуга может быть поме­ чена условием перехода и действием, выполняемым в процессе вы­ полнения перехода. На рис. 5 приведена Р-схема для того же самого алгоритма.

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

19