Изучение принципов построения простейших микроконтроллеров и их микропрограммирования на основе МПК серии К1804

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

Разработка функциональной схемы микропроцессорной системы на БИС МПК К1804

Разработайте и представьте в отчете функциональную (структурную) схему микропроцессорной системы с 4n-разрядным ЦПЭ К1804ВС1 и БМУ, объединяющем m секций СУАМ К1804ВУ1. Значения n и m уточните у преподавателя. Приведите формат микрокоманды разрабатываемой системы.

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

Список литературы

1. В. Ф. Мелехин. Вычислительные машины, системы и сети: Учебник для студ. высш. учеб. заведений / В. Ф. Мелехин, Е. Г. Павловский. — М.: Издательский центр «Академия», 2010. — 550 с.

2. Григорьев В. Л. Программное обеспечение микропроцессорных систем. — М.: Энергоатомиздат, 1983.

3. Дурандин К. П., Ефремов В. Д., Жвариков В. А. и др. Микропроцессоры
в автоматике и вычислительной технике: Учебное пособие. — Л.: ЛПИ,
1986. — 80 с.

4. Организация микропроцессоров: Метод. указания / Сост. К. П. Дурандин, В. А. Жвариков, О. И. Иванов, Е. Г. Павловский. СПб., 1992. — 96 с.

Приложение 1

Система команд микропроцессоров КР580 и К1821

Условные обозначения:

А — аккумулятор, В, C, D, E, H, L — регистры общего назначения, обозначаемые в зависимости от выполняемой функции R_{S ­}(регистр источник, S — Source) или R_{D ­}(регистр приемник, D — Destination).

М — ячейка памяти (от memory). В нотации команд МП 8080 ячейка памяти М трактуется как своеобразный регистр, обращение к которому производится только с использование косвенной адресации. Адрес М размещается в регистровой паре HL.

BC, DE, HL — регистровые пары (RP), обозначаемые в командах по именам старших регистров пары: В — имя регистровой пары ВС, D — имя регистровой пары DE, Н — имя регистровой пары HL.

Кодирование регистров и регистровых пар представлено в табл. П1.

Таблица П1

Имя регистра	Код регистра	Имя регистровой пары RP	Код RP
B		В-пара
C
D		D-пара
E
H		H-пара
L
M		PSW
A		SP

addr — 16-битный адрес памяти; port — 8-битный адрес периферийного устрой­ства;

data8, data16 — 8-битные, 16-битные данные; В₂, В₃ — второй, третий байты команды;

Z/NZ, C/NC, PE/PO, P/M (знак S), C ' — признаки результата;

() — содержимое ячейки памяти или регистра, символическое имя которых заключено в скобки;

[ ] — адрес ячейки памяти

Список команд микропроцессора 8080 приведен в табл. П2, П3. В табл. П2 представлены команды, не воздействующие на флаги процессора. Это — команды пересылок, команды загрузки в стек и извлечения из стека (за исключением команды РОР PSW, которая изменяет флаги), команды передачи управления и команды управления микропроцессором. При выполнении команд этой группы признаки результата не изменяют своего значения. В табл. П3 представлены команды, при выполнении которых признаки результата (флаги) модифицируются в соответствии с значением результата. Таблицы П2 и П3 отличаются друг от друга наличием (табл. П3) или отсутствием колонки «признаки результата» (табл. П2).

Таблица П2

Название команды	Мнемоника команды	Код операции	Параметры команды б ц т	Описание команды
К о м а н д ы п е р е с ы л к и д а н н ы х
Пересылки 8-битных данных	MOV RD,RS	1DS				(RS) → (RD)
MOV M,RS	16S				(RS) → (M)
MOV RD, M	1D6				(M) → (RD)
Загрузка регистра непосредственная	MVI RD,Data8	0D6 B2				B2 → (RD)
MVI M,Data8	O66 B2				B2 → (M)
Загрузка пары регистров непосредственная	LXI B,Data16	001 B2 B3				B2 → (C) B3 → (B)
LXI D,Data16	021 B2 B3				B2 → (E) B3 → (D)
LXI H,Data16	041 B2 B3				B2 → (L) B3 → (H)
LXISP,Data16	061 B2 B3				B2 B3 → (SP)
К о м а н д ы п е р е с ы л о к д а н н ы х в а к к у м у л я т о р и и з а к к у м у л я т о р а
Загрузка А (прямая)	LDA addr	072 B2 B3				[(B2)(B3)]→ (A)
Загрузка А (косвенная)	LDAX B					[(B)(C)] → (A)
LDAX D					[(D)(E)] → (A)
Запоминание А (прямое)	STA addr	062 B2 B3				(A) → [(B2)(B3)]
Запоминание А (косвенное)	STAX B					(A) → [(B)(C)]
STAX D					(A) → [(D)(E)]
Ввод	IN port	333 B2				[port] → (A)
Вывод	OUT port	323 B2				(A) → [port]
К о м а н д ы о б м е н а, з а г р у з к и и з а п о м и н а н и я с о д е р ж и м о г о р е г и с т р о в о й п а р ы HL
Обменять	XCHG					(H) ↔ (D) (L) ↔ (E)
XTHL					(L) ↔ ([SP]) (H) ↔ ([SP+1])
Загрузка (прямая)	LHLD addr	052 B2 B3				[(B2)(B3)] → (L) [(B2+1)(B3)]→(H)
Запоминание (прямое)	SHLD addr	042 B2 B3				(L)] → [(B2)(B3) (H)→[(B2+1)(B3)]
Загрузка указателя стека	SPHL					(H)(L) → (SP)
Загрузка счетчика команд	PCHL					(H)(L) → (PC)
К о м а н д ы з а г р у з к и в с т е к и и з в л е ч е н и я и з с т е к а
Загрузка стека	PUSH B					(B) → ([SP-1]) (C) → ([SP-2]) (SP):= (SP)-2
PUSH D					(D) → ([SP-1]) (E) → ([SP-2]) (SP):= (SP)-2
PUSH H					(H) → ([SP-1]) (L) → ([SP-2]) (SP):= (SP)-2
PUSH PSW					(A) → ([SP-1]) (F) → ([SP-2]) (SP):= (SP)-2
Извлечение из стека	POP B					([SP]) → (C) ([SP+1]) → (B) (SP):= (SP)+2
POP D					([SP]) → (E) ([SP+1]) → (D) (SP):= (SP)+2
POP H					([SP]) → (L) ([SP+1]) → (H) (SP):= (SP)+2
POP PSW					([SP]) → (F) ([SP+1]) → (A) (SP):= (SP)+2

Продолжение таблицы П2

К о м а н д ы б е з у с л о н о й п е р е д а ч и у п р а в л е н и я
Безусловный переход	JMP addr	303 B2 B3				B2 B3→ (PC)
Безусловный вызов подпрограммы	CALL addr	315 B2 B3				(PC)→[(SP –2)(SP) –1] (SP):=(SP) –2 B2 B3→ (PC)
Безусловный возврат из подпрограммы	RET					[(SP) (SP) +1] → (PC) (SP):=(SP) +2
Загрузка счетчика команд (множественное ветвление)	PCHL					(H)(L) → (PC)
Вызов прерывающей программы	RST N	3N7				(PC)→[(SP –2)(SP) –1] (SP):=(SP) –2 (PC):=000 0N0
К о м а н д ы у с л о в н о г о п е р е х о д а
Переход по нулевому значению флага Z (ненулевому результату)	JNZ addr	302 B2 B3				Переход по условию, заданному в команде. Если условие выполняется, то осуществляется переход к команде, размещенной по адресу B2 B3 B3 B2 → (PC). Если условие не выполняется, то осуществляется переход к следующей по порядку команде (PC):= (PC) +3
Переход по единичному значению флага Z (нулевому результату)	JZ addr	312 B2 B3
Переход по нулевому значению флага C (при отсутствии переноса)	JNС addr	322 B2 B3
Переход по единичному значению флага C (при наличии переноса)	JС addr	332 B2 B3
Переход по нулевому значению флага четности P (при отсутствии четности)	JPO addr	342 B2 B3
Переход по единичному значению флага четности P (при наличии четности)	JPE addr	352 B2 B3
Переход по нулевому значению флага знака S, (положительное значение)	JP addr	362 B2 B3
Переход по единичному значению флага знака S, (отрицательное значение)	JM addr	372 B2 B3
К о м а н д ы у с л о в н о г о в ы з о в а п о д п р о г р а м м
Вызов подпрограммы при Z = 0	CNZ addr	304 B2 B3		3/5	11/17	Вызов подпрограммы при выполнении усло-вия, заданного в команде. Если условие выпол-няется, то осущест-вляется переход к подпрограмме, т. е. к команде, размещен-ной по адресу B2 B3 B2 B3 → (PC). Если условие не выполняется, то осуществляется переход к следующей по порядку команде (PC):= (PC) +3
Вызов подпрограммы при Z = 1	СZ addr	314 B2 B3		3/5	11/17
Вызов подпрограммы при C = 0	СNС addr	324 B2 B3		3/5	11/17
Вызов подпрограммы при C = 1	СС addr	334 B2 B3		3/5	11/17
Вызов подпрограммы при отсутствии четности P=0	СPO addr	344 B2 B3		3/5	11/17
Вызов подпрограммы при наличии четности P=1	СPE addr	354 B2 B3		3/5	11/17
Вызов подпрограммы при положительном результате (S = 0)	СP addr	364 B2 B3		3/5	11/17
Вызов подпрограммы при отрицательном результате (S = 1)	СM addr	374 B2 B3		3/5	11/17

Продолжение таблицы П2

К о м а н д ы у с л о в н о г о в о з в р а т а и з п о д п р о г р а м м
Возврат из подпрограммы при ненулевом результате (Z = 0)	RNZ			1/3	5/11	Возврат из подпрограммы при выполнении условия, заданного в команде. Если условие выполняется, то осуществляется переход к команде, размещенной по адресу возврата из стека, [(SP) (SP) +1] → (PC) (SP):=(SP) +2 Если условие не выполняется, то осуществляется переход к следующей по порядку команде (PC):= (PC) +3
Возврат из подпрограммы при нулевом результате (Z = 1)	RZ			1/3	5/11
Возврат из подпрограммы при отсутствии переноса (C = 0)	RNС			1/3	5/11
Возврат из подпрограммы при наличии переноса (C = 1)	RС			1/3	5/11
Возврат из подпрограммы при отсутствии четности (P = 0)	RPO			1/3	5/11
Возврат из подпрограммы при наличии четности (P = 1)	RPE			1/3	5/11
Возврат из подпрограммы при положительном результате (S = 0)	RP			1/3	5/11
Возврат из подпрограммы при отрицательном результате (S = 1)	RM			1/3	5/11
К о м а н д ы у п р а в л е н и я м и к р о п р о ц е с с о р о м
Разрешение прерываний	EI					Формирование сигнала INTE=1
Запрещение прерываний	DI					Формирование сигнала INTE=0
Холостая команда	NOP					Переход к следующей команде без операции
Команда останова	HLT					Останов. Возможно продолжение программы по запросу прерывания

Таблица П3

Название команды	Мнемоника команды	Код операции	Признаки (флаги) результата s z c’ р с	Параметры команды б ц т	Описание команды
К о м а н д ы а р и ф м е т и ч е с к и х о п е р а ц и й
Сложение	ADD RS	20S	+	+	+	+	+				(A) + (RS) → (A)
ADD M		+	+	+	+	+				(A) + (M) → (A)
ADI Data8	306 B2	+	+	+	+	+				(A) + B2 → (A)
Сложение с переносом	ADC RS	21S	+	+	+	+	+				(A)+(RS)+ C→ (A)
ADC M		+	+	+	+	+				(A)+(M)+ C → (A)
ACI Data8	316 B2	+	+	+	+	+				(A)+ B2 + C → (A)
Вычитание	SUB RS	22S	+	+	+	+	+				(A) - (RS) → (A)
SUB M		+	+	+	+	+				(A) - (M) → (A)
SUI Data8	326 B2	+	+	+	+	+				(A) – B2 → (A)
Вычитание с заемом	SBB RS	23S	+	+	+	+	+				(A) - (RS) - C→(A)
SBB M		+	+	+	+	+				(A) - (M) - C→ (A)
SBI Data8	336 B2	+	+	+	+	+				(A) - B2 - C → (A)
Сравнение (неразрушающее вычитание)	CMP RS	27S	+	+	+	+	+				(A) - (RS)
CMP M		+	+	+	+	+				(A) - (M)
CPI Data8	376 B2	+	+	+	+	+				(A) - B2
Продолжение таблицы П3
Название команды	Мнемоника команды	Код операции	Признаки (флаги) результата s z c’ р с	Параметры команды б ц т	Описание команды
Инкремент (увеличение содержимого адресуемого источника на 1)	INR RD	0D4	+	+	+	+	-				(RD) + 1 → (RD)
INR M		+	+	+	+	-				(M) + 1 → (M)
INX B		-	-	-	-	-				(B)(C) + 1→(B)(C)
INX D		-	-	-	-	-				(D)(E) + 1→(D)(E)
INX H		-	-	-	-	-				(H)(L) + 1→(H)(L)
INX SP		-	-	-	-	-				(SP) + 1 →(SP)
Декремент (уменьшение содержимого адресуемого источника на 1)	DCR RD	0D5	+	+	+	+	-				(RD) – 1 → (RD)
DCR M		+	+	+	+	-				(M) – 1 → (M)
DCX B		-	-	-	-	-				(B)(C) - 1 →(B)(C)
DCX D		-	-	-	-	-				(D)(E) - 1 →(D)(E)
DCX H		-	-	-	-	-				(H)(L) - 1 →(H)(L)
DCX SP		-	-	-	-	-				(SP) - 1 →(SP)
Двойное сложение	DAD B		-	-	-	-	+				HL + BC → HL
DAD D		-	-	-	-	+				HL + DE → HL
DAD H		-	-	-	-	+				HL + HL → НL
DAD SP		-	-	-	-	+				HL + SP → HL
Десят. коррекция	DAA		+	+	+	+	+
К о м а н д ы л о г и ч е с к и х о п е р а ц и й
Логическое умножение	ANA RS	24S	+	+	-	+					(A) ^ RS → (A)
ANA M		+	+	-	+					(A) ^ M → (A)
ANI Data8	346 B2	+	+	-	+					(A) ^ B2→ (A)
Исключающее ИЛИ (сложение по mod 2)	XRA RS	25S	+	+	-	+					(A) RS → (A)
XRA M		+	+	-	+					(A) M → (A)
XRI Data8	356 B2	+	+	-	+					(A) B2 → (A)
Логическое сложение	ORA RS	26S	+	+	-	+					(A) RS → (A)
ORA M		+	+	-	+					(A) M → (A)
ORI Data8	366 B2	+	+	-	+					(A) B2 → (A)
Инвертирование А	CMA		-	-	-	-	-				→ (A)
К о м а н д ы ц и к л и ч е с к и х с д в и г о в
Сдвиг влево	RLC		-	-	-	-	+
Сдвиг вправо	RRC		-	-	-	-	+
Циклический сдвиг влево через перенос	RAL		-	-	-	-	+
Циклический сдвиг вправо через перенос	RAR		-	-	-	-	+
К о м а н д ы у п р а в л е н и я ф л а г о м С
Установка переноса	STC		-	-	-	-	+				1 → C
Инверсия переноса	CMC		-	-	-	-	+				→ C

Приложение 2

Типы машинных циклов МП КР580ВМ80А и состояние управляющих сигналов байта состояния для различных типов машинных циклов приведено в табл. П2.1.

Таблица П2.1

Машинный цикл	Кодирование управляющих сигналов байта состояния
В7 MEMR	В6 INP	В5 M1	В4 OUT	В3 HLTA	В2 STACK	В1 WO	B0 INTA
М1 Выборка кода операции
М2 Считывание из памяти
М3 Запись в память
М4 Считывание из стека
М5 Запись в стек
М6 Ввод (считывание ВУ)
М7 Вывод (запись ВУ)
М8 Прерывание
М9 Останов
М10 Прерывание при останове

Назначение отдельных бит В _i байта состояния [2]:

B₀ (INTA) — подтверждение прерывания (ППР). Используется для ввода в регистр команд МП команды RST из устройства, запрашивающего прерывание.

B₁ (WO) — запись/вывод (ВМП). Идентифицирует МП как источник информации (WO=0) при записи в память/выводе или как получатель информации (WO=1) при чтении из памяти/вводе.

B₂ (STACK) — (СТЕК). Источником адреса на шине адреса является указатель стека.

B₃ (HLTA) — подтверждение останова (ПОСТ). МП находится в состоянии останова.

B₄ (OUT) — вывод (ЗПВВ). На шине адреса установлен адрес порта вывода.

B₅ (M1) — машинный цикл выборки команды М1. Определяет выборку из программной памяти кода операции (первого байта команды).

B₆ (INP) — ввод (ЧТВВ). На шине адреса установлен адрес порта ввода.

B₇ (MEMR) — считывание из памяти (ЧТП). На шине адреса установлен адрес памяти.

Приложение 3

Примеры и варианты заданий лабораторного практикума

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

Варианты индивидуальных заданий

1. Нахождение минимального (максимального) числа в массиве;

2. Упорядочение элементов массива по возрастанию (убыванию);

3. Нахождение медианы массива элементов;

4. Определение моды массива элементов;

5. Вычисление элементов матрицы, полученной в результате суммирования двух исходных матриц;

6. Табличное преобразование кода;

7. Определение максимального двоичного значения в массиве из n чисел, представленных в коде Грея;

8. Транспонирование матрицы n × n;

9. Умножение «младшими разрядами вперед» двух n -разрядных чисел
(n = 4, 8);

10. Умножение «старшими разрядами вперед» двух n -разрядных чисел
(n = 4, 8);

11. Деление «с восстановлением остатка» двух 8-разрядных чисел с формированием 8-разрядного частного;

12. Деление «без восстановления остатка» двух 8-разрядных чисел с формированием 8-разрядного частного;

13. Определение n -го члена и суммы n членов ряда Фибоначчи;

14. Статическая индикация элементов массива чисел (матрицы, сомножи-телей и произведения, делимого, делителя и частного);

15. Динамическая индикация элементов массива чисел (матрицы, сомножителей и произведения, делимого, делителя и частного);

16. Управление макетом светофора;

17. Программный секундомер;

18. Реализация «бегущей» строки заданного текста.

19. Поиск максимального (минимального, срединного) из трех чисел методом «дерева» сравнений;

20. Определение числа нулей (единиц) в байте;

21. Определение числа совпадающих (несовпадающих) разрядов в двух байтах;

22. Определение числа переходов из 1 в 0 и из 0 в 1 в байте данных;

23. Определение числа переходов из 1 в 0 (из 0 в 1) в байте данных;

24. Определение максимальной последовательности нулей (единиц) в байте;

25. Определение делимости на три 8-разрядного числа;

26. Преобразование двоичных чисел в двоично-десятичные;

27. Преобразование двоично-десятичных чисел в двоичные.

При решении любой задачи необходимо:

1. Проанализировать задание и выбрать аппаратные и программные средства для решения. При разработке программ лабораторного практикума на этом этапе определяется состав операционной части МП, требуемый для решения задачи (выполняются соответствующие назначения регистров блока РОН — кто за что отвечает).

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

3. В соответствии с разработанным алгоритмом написать программу (микропрограмму) решения задачи с учетом особенностей конкретного МП.

4. Выполнить программирование задачи на стенде.

5. Провести настройку и тестирование программы.

6. Составить отчет, включающий:

– схему алгоритма;

– текст программы с необходимыми комментариями;

– результаты тестирования выполненной программы;

– выводы, отражающие особенности реализации при решении задачи с помощью конкретного МП.

Пояснения и рекомендации к программам индивидуальных заданий

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

Обработка массивов чисел (структур данных)

Под структурами данных (массивами) понимают наборы некоторым образом организованных данных. Различают простые структуры данных, в которых каждый элемент массива определяется своим номером (индексом), и сложные структуры, например двухсвязные списки, элементы которых вместе с данными должны содержать указатели преемника и предшественника. Программисту необходимо знать наиболее распространенные структуры данных и способы хранения их в памяти ВМ. Правильный выбор структуры данных позволяет уменьшить объем памяти и увеличить производительность системы. Чаще применяются простые структуры данных. Наиболее простой и распространенной структурой данных является одномерный массив. Он представляет собой конечный набор элементов одинаковой длины, который размещается в смежных ячейках памяти, начиная с некоторого начального адреса. Положение элемента в массиве определяется его индексом. Адрес элемента массива равен сумме базового адреса и индекса, умноженного на длину элемента в байтах.

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

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

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

Массив не обязательно должен быть линейным набором элементов. Он может быть и многомерным. Двумерный массив представляет набор данных, в котором доступ к любому из элементов осуществляется по двум индексам — номеру строки n_r и номеру столбца n_c. Пример двумерного массива показан на рис. П3.1.

	Столбец 1	Столбец 2	Столбец 3	Столбец 4
Строка 1	А(1,1)	А(1,2)	А(1,3)	А(1,4)
Строка 2	А(2,1)	А(2,2)	А(2,3)	А(2,4)
Строка 3	А(3,1)	А(3,2)	А(3,3)	А(3,4)
Строка 4	А(4,1)	А(4,2)	А(4,3)	А(4,4)

Рис. П3.1. Двумерный массив

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

А(1,1)		А(1,1)
А(2,1)		А(1,2)
А(3,1)		А(1,3)
А(4,1)		А(1,4)
А(1,2)		А(2,1)
А(2,2)		А(2,2)
А(3,2)		А(2,3)
А(4,2)		А(2,4)
А(1,3)		А(3,1)
А(2,3)		А(3,2)
А(3,3)		А(3,3)
А(4,3)		А(3,4)
А(1,4)		А(4,1)
А(2,4)		А(4,2)
А(3,4)		А(4,3)
А(4,4)		А(4,4)

Рис. П3.2. Отображение двумерного массива в памяти по столбцам (а) и по строкам (б)

а) б)

Как и в одномерном массиве, в двумерном массиве положение элемента определяется его индексом. Адрес элемента массива равен сумме базового адреса и общего индекса IND, который зависит от способа размещения массива в памяти:

IND = i * n_r + j, если массив хранится по строкам,

IND = i + j * n_c, если массив хранится по столбцам,

здесь i — номер строки, j — номер столбца, n_r и n_с — число строк и столбцов.

Обработка двумерных массивов выполняется подпрограммами, содержащими два цикла. Во внешнем цикле производится инкремент i, а во внутреннем (вложенном) — инкремент j.

Типовыми задачами при работе с одномерными массивами данных являются:

– нахождение минимального (максимального) числа в массиве;

– упорядочение элементов массива по возрастанию (убыванию);

– нахождение медианы массива элементов;

– определение моды массива элементов;

– вычисление элементов матрицы, полученной в результате суммирования двух исходных матриц;

– табличное преобразование кода.

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

П3.1. Выбор одного из m чисел по заданному критерию. Критерием выбора может быть: максимальное число, минимальное, «медианное», наибольшее четное и др.

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

Большое число сравнений, характерное для классической пузырьковой сортировки является недостатком этого метода, поскольку требует значительных временных затрат. Известно несколько способов, позволяющих уменьшить время сортировки. Например, можно учесть, что после очередного i -го просмотра массива все элементы в позициях n – i + 1 оказываются упорядоченными и просмотр массива можно начинать (n – i)-го элемента. Отмеченное свойство пузырьковой сортировки позволяет уменьшить общее число сравнений и, благодаря этому, ускорить процесс упорядочения элементов массива.

Число сравнений при сортировке можно также уменьшить, если учесть, что в большинстве случаев массив оказывается отсортированным после меньшего, чем n – i, числа просмотров и последующие просмотры оказываются ненужными. Для исключения ненужных просмотров используют следующий прием. В программу вводят переменную — специальный указатель обмена, с помощью которого фиксируют наличие хотя бы одной перестановки в просмотре. Значение указателя обмена анализируется после окончания просмотра массива. При ненулевом указателе последний сбрасывается, и весь массив просматривается вновь. Сортировка заканчивается, когда при очередном просмотре массива обмены не фиксируются.

Существенного сокращения числа сравнений при решении задачи выбора одного из m чисел по заданному критерию можно достичь, используя алгоритм «дерева» сравнений и переходов. На рис. П3.3 представлен достаточно очевидный алгоритм «дерева» сравнений для массива из трех элементов. При его реализации выполняется только ограниченное число операций сравнения, вследствие чего этот алгоритм является значительно более быстродей­ствующим по сравнению с алгоритмами сортировки. Для нахождения медианы в массиве из трех элементов требуется пять операций сравнения, при этом медиана для конкретного набора элементов определяется максимум за три сравнения.

Недостатком данного метода является его неэффективность по затратам памяти с ростом размерности массива. По этой причине метод «дерева» сравнений используют только для массивов малой размерности, как правило, не более чем из трех элементов.

.

Алгоритм поиска максимального/минимального числа естественно проще. В частности для поиска максимального значения из трех элементов (алгоритм поиска на рис. П3.3 выделен пунктиром) требуется не более двух сравнений.

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