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

Составление программы сортировки по возрастанию массив из 20 шестнадцатеричных чисел, просматривающей все исходные числа во внешней памяти и выбирающей самое большое число. Блок-схема алгоритма работы программы. Таблица команд и число их выполнения.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 24.05.2015
Размер файла 23,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на 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


Подобные документы

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

    курсовая работа [44,0 K], добавлен 09.11.2014

  • Решения задачи графическим и программным способами. Описание алгоритма решения графическим способом, укрупненная схема алгоритма. Ввод элементов двумерного массива, вывод преобразованного массива, разработка программы на языке pascal, листинг программы.

    курсовая работа [115,5 K], добавлен 22.05.2010

  • Разработка алгоритма выполнения операций умножения двоичных чисел в формате расширенной точности на сумматоре обратного кода. Преобразование входной строки в десятичное число. Разработка алгоритма арифметической операции. Тестирование программы-эмулятора.

    курсовая работа [119,1 K], добавлен 24.06.2012

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

    лабораторная работа [438,5 K], добавлен 16.07.2015

  • Анализ технического задания. Разработка программы по вычислению функции на языке ассемблер для микропроцессора Кр580ВМ80. Алгоритмы программного умножения, деления, сложения, вычитания и сдвига влево многобайтных чисел. Расчет времени работы программы.

    курсовая работа [88,2 K], добавлен 19.09.2012

  • Особенности поиска среднеарифметического значения элементов массива. Общая характеристика проблем разработки в среде Turbo Pascal программы упорядочивания массива по возрастанию. Рассмотрение основных этапов разработки программы на языке PASCAL.

    курсовая работа [896,7 K], добавлен 18.05.2014

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

    дипломная работа [1,0 M], добавлен 15.06.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.