Разработка алгоритма и программы сортировки массива из 20 чисел по возрастанию

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

КУРСОВОЙ ПРОЕКТ

по дисциплине

«Микропроцессорные устройства управления роботов и их программное обеспечение»

Разработка алгоритма и программы сортировки массива из 20 чисел по возрастанию

Исходные данные

13h, 11h, 01h, 17h, 07h, 03h, 21h, 32h, 32h, 12h, 42h, 34h, 22h, 14h, 55h, 11h, 17h, 77h, 31h, 12h.

Содержание

Введение

Блок-схема алгоритма работы программы

Алгоритм работы программы

Листинг программы

Результаты выполнения программы

Заключение

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

Введение

Программы можно писать не только для x86 компьютеров. Более того, большая часть процессоров в мире - НЕ x86. Основная часть микропроцессоров сейчас - это микроконтроллеры. В большинстве учебных заведений бывшего СССР изучение микроконтроллеров начинается с легендарного Intel 8051 (официальное название - MCS 51, также он известен как i8051 и MCS-51). У этого микроконтроллера есть assembler, очень похожий на ассемблер привычных нам процессоров x86 архитектуры. Этот контроллер применялся в старых клавиатурах, да и вообще много где он применялся. Будем называть этот микропроцессор Intel 8051 или MCS 51, потому что во всем мире он известен именно под этим названием.

Цель работы:

Необходимо отсортировать по возрастанию массив из 20 шестнадцатеричных чисел. Чтобы это сделать надо найти максимальный элемент и поместить в конец массива, потом второй по величине и поставить его на предпоследнее место массива и т.д.

Особенности микроконтроллера

Intel 8051 -- это 8 разрядный однокристальный микроконтроллер гардвардской архитектуры, впервые произведенный компанией Intel в 1980 году и предназначенный для использования во встраиваемых (embedded) системах. Он состоит из процессорного ядра (CPU), ОЗУ, ПЗУ, последовательного и параллельного порта, и еще небольшого количества дополнительных элементов. Программы для него можно писать на специализированном ассемблере, который очень напоминает ассемблер для x86-процессоров, или на языке С. Но, конечно, есть ограничения. У нас в распоряжении всего 128 байт ОЗУ (называется память DATA), 4 кбайта встроенного ПЗУ для хранения самой программы (память программ), и 64 кбайта в ПЗУ (называется XDATA - external data, или память данных). Зато есть прерывания.

Восьмиразрядные высокопроизводительные однокристальные микроЭВМ (ОМЭВМ) семейства МК51 выполнены по высококачественной n-МОП технологий (серия 1816) и КМОП технологии (серия 1830) .

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

ОМЭВМ КР1816ВЕ51 и КР1830ВЕ51 содержат масочно-программируемое в процессе изготовления кристалла ПЗУ памяти программ емкостью 4096 байт и рассчитаны на применение в массовой продукции. За счет использования внешних микросхем памяти общий объем памяти программ может быть расширен до 64 Кбайт.

ОМЭВМ КМ1816ВЕ751 содержит ППЗУ емкостью 4096 байт со стиранием ультрафиолетовым излучением и удобна на этапе разработки системы при отладке программ, а также при производстве небольшими партиями или при создании систем, требующих в процессе эксплуатации периодической подстройки. За счет использования внешних микросхем памяти общий объем памяти программ может быть расширен до 64 Кбайт.

ОМЭВМ КР1816ВЕ31 и КР183ОВЕ31 не содержат встроенной памяти программ, однако могут использовать до 64 Кбайт внешней постоянной или перепрограммируемой памяти программ и эффективно использоваться в системах, требующих существенно большего по объему (чем 4 Кбайт на кристалле) ПЗУ памяти программ.

Каждая из перечисленных выше микросхем является соответственно аналогом БИС 8051, 80С51, 8751, 8031, 80С31 семейства MCS-51 фирмы Intel (США).

Каждая ОМЭВМ рассматриваемого семейства содержит встроенное ОЗУ памяти данных емкостью 128 байт с возможностью расширения общего объема оперативной памяти данных до 64 Кбайт за счет использования внешних микросхем ЗУПВ.

Общий объем памяти ОМЭВМ семейства МК51 может достигать 128 Кбайт: 64 Кбайт памяти программ и 64 Кбайт памяти данных.

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

1) центральный восьмиразрядный процессор;

2) память программ объемом 4 Кбайт (только КМ1816ВЕ751, КР1816ВЕ51 и КР1830ВЕ51);

3) память данных объемом 128 байт;

4) четыре восьмиразрядных программируемых канала ввода-вывода;

5) два 16-битовых многорежимных таймера/счетчика;

6) систему прерываний с пятью векторами и двумя уровнями;

7) последовательный интерфейс;

8) тактовый генератор.

Аккумулятор. АСС -- регистр аккумулятора. Команды, предназначенные для работы с аккумулятором, используют мнемонику "А", например, MOV А, Р2.Мнемоника "АСС" используется, к примеру, при побитовой адресации аккумулятора. Так, символическое имя пятого бита аккумулятора при использовании ассемблера ASM51 будет следующим: АСС.5.

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

Регистр состояния программы. Регистр PSW содержит информацию о состоянии программы.

Указатель стека SP. 8-битовый регистр, содержимое которого инкрементируется перед записью данных в стек при выполнении команд PUSH и CALL. При начальном сбросе указатель стека устанавливается в 07Н, а область стека в ОЗУ данных начинается с адреса 08Н. При необходимости путем переопределения указателя стека область стека может быть расположена в любом месте внутреннего ОЗУ данных микроЭВМ.

Указатель данных. Указатель данных (DPTR) состоит из старшего байта (DPH) и младшего байта (DPL). Содержит 16-битовый адрес при обращении к внешней памяти. Может использоваться как 16-битовый регистр или как два независимых восьмибитовых регистра.

Порт0--ПортЗ. Регистрами специальных функций Р0, Р1, Р2, РЗ являются регистры-"защелки" соответственно портов Р0, Р1, Р2, РЗ.

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

Регистры таймера. Регистровые пары (TH0.TL0) и (TH1.TL1) образуют 16- битовые счетные регистры соответственно таймера/счетчика 0 и таймера/счетчика 1.

Регистры управления. Регистры специальных функций IP, IE, TMOD, TCON, SCON и PCON содержат биты управления и биты состояния системы прерываний, таймеров/счетчиков и последовательного порта. ОМЭВМ при функционировании обеспечивает:

-- минимальное время выполнения команд сложения -- 1 мкс;

-- аппаратное умножение и деление с минимальным временем выполнения команд умножения/деления -- 4 мкс

Блок-схема алгоритма работы программы

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

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

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

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

Процесс продолжается до использования всех чисел из внешней памяти.

После этого отсортированные элементы переписываются обратно во внешнюю память.

Использование памяти

Участки памяти:

Xdata: 0000h…0019h - область сортируемых чисел

data: 40h…53h - область, используемая для промежуточного хранения и сортировки чисел

Регистры:

DPTR: хранит адрес байта в XDATA (0000h..0019h).

A: используется как буфер для передачи данных из XDATA в DATA и для копирования данных из одного участка памяти в другой.

R0: хранит адрес обрабатываемого элемента в DATA (40h..53h)

R1: используется как локальный счетчик цикла.

R2: хранит данные из DPL для запоминания адреса текущего самого большего элемента.

Участок 36h:хранит текущее самое большое число.

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Рис 1.

Листинг программы

org 00h;смещение от начала

jmp start;переход к началу

org 50h;память данных

Start:

; ИНИЦИАЛИЗАЦИЯ

module_create_data: ;Модуль устанавливает начальные значения байтам в XDATA с адресами 00h..09h

mov DPTR, #0000h;адрес

mov A, #13h; 1-e число

movx @DPTR, A; занести число по адресу

inc DPTR;увеличить адрес на 1

mov A, #11h; 2-e число

movx @DPTR, A

inc DPTR

mov A, #01h; 3-e число

movx @DPTR, A

inc DPTR

mov A, #17h; 4-e число

movx @DPTR, A

inc DPTR

mov A, #07h; 5-e число

movx @DPTR, A

inc DPTR

mov A, #03h; 6-e число

movx @DPTR, A

inc DPTR

mov A, #21h; 7-e число

movx @DPTR, A

inc DPTR

mov A, #32h; 8-e число

movx @DPTR, A

inc DPTR

mov A, #32h; 9-e число

movx @DPTR, A

inc DPTR

mov A, #12h; 10-e число

movx @DPTR, A

mov A, #42h; 11-e число

movx @DPTR, A

inc DPTR

mov A, #34h; 12-e число

movx @DPTR, A

inc DPTR

mov A, #22h; 13-e число

movx @DPTR, A

inc DPTR

mov A, #14h; 14-e число

movx @DPTR, A

inc DPTR

mov A, #55h; 15-e число

movx @DPTR, A

inc DPTR

mov A, #11h; 16-e число

movx @DPTR, A

inc DPTR

mov A, #17h; 17-e число

movx @DPTR, A

inc DPTR

mov A, #77h; 18-e число

movx @DPTR, A

inc DPTR

mov A, #31h; 19-e число

movx @DPTR, A

inc DPTR

mov A, #12h; 20-e число

movx @DPTR, A

;СОРТИРОВКА

module_sort_massiv: метка начала сортировки

mov R0, #53h

metka1: метка главного цикла сортировки

mov 54h, #00h

mov R2, DPL

jmp module_search_massiv переход на метку поиска макс

metka_vozvrata1: метка возврата из поиска макс эл.

mov DPL, R2

mov A, #00h

dec DPL

movx @DPTR, A

mov @R0, 54h

dec R0

cjne R0, #3Fh, metka1

jmp module_data_to_xdata переход на метку вывода данных

;ДОПОЛНИТЕЛЬНЫЕ МОДУЛИ

module_search_massiv: начало кода поска макс эл массива

mov DPTR, #0000h

metka2: главный цикл поиска 

movx A, @DPTR

inc DPTR

mov R1, DPL

cjne A, 54h, metka3 

metka_vozvrata2: перед возвратом

cjne R1, #14h, metka2 переход на метку вложенного цикла

jmp metka_vozvrata1 переход на возврат из поиска

metka3:

jc metka_vozvrata2 продолжаем сканировать

mov 54h, A

mov R2, DPL

jmp metka_vozvrata2 пока все не переберем программа в цикле

;ПЕРЕМЕЩЕНИЕ ОТСОРТИРОВАННЫХ ЧИСЕЛ ОБРАТНО ВО ВНЕШНЮЮ ПАМЯТЬ

module_data_to_xdata:

mov DPTR, #0000h

mov R0, #40h

metka4: цикл вывода

mov A, @R0

movx @DPTR, A

inc DPTR

inc R0

cjne R0, #54h, metka4 на метку цикла

final:

end.

Результаты выполнения программы:

до сортировки	После сортировки
13h	01h
11h	03h
01h	07h
17h	11h
07h	11h
03h	12h
21h	12h
32h	13h
32h	14h
12h	17h
42h	17h
34h	21h
22h	22h
14h	31h
55h	32h
11h	32h
17h	34h
77h	42h
31h	55h
12h	77h

сортировка массив число команда

Таблица команд и число их выполнения:

mov DPTR, #0000h	21
mov R0, #53h	21
movx @DPTR, A	60
inc DPTR	420
inc R0	20
cjne R0, #3Fh, metka1	460
dec R0	20
mov @R0, 54h	20
mov A, #31h	40
mov 54h, #00h	20
mov R2, DPL	560
jmp metka_vozvrata	180
movx A, @DPTR	420
cjne A, 54h, metka3	400
jc metka_vozvrata2	400
mov 54h, A	140
mov DPL, R2	20
dec DPL	20
mov A, @R0	20

Время затраченное программой на своё выполнение:

t = 5 + 20 + 20 + 40 + 60 + 20 + 100 + 80 + 40 + 400 + 40 + 60 + 1680 + 540 + 420 + 1200 + 800 + 280 + 1320 + 40 + 40 = 7305 тактов = 609 циклов = 203 мкс

Объём памяти занимаемый программой:

V = 24 * (1 + 20 + 20 + 20 + 20 + 20 + 20 + 40 + 400 + 20 + 560 + 180 + 420 + 400 + 400 + 440 + 20) + 12 * (1 + 20 + 20 + 20 + 40 + 20 + 140 + 20) = 74916 байт = 73Кб

Заключение

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

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

Герасимов В.В. «Микропроцессорное устройство и управление роботов» лекции 2012.

http://atdevil.ru/wp-content/uploads/2011/02/mcs51.pdf

Юсупов Ю.А. “Система команд микроконтроллеров MCS-51”, 2010.

Размещено на Allbest.ru