Рубрики

Программа 8085 для бинарного поиска

Обязательное условие — бинарный поиск
Проблема — Напишите программу на ассемблере в микропроцессоре 8085, чтобы найти заданное число в списке из 10 чисел. Если найден магазин 1 на выходе, иначе магазин 2 на выходе. Также сохраните количество итераций и индекс элемента, если он найден.

Пример: пусть список будет следующим:

Test-1: 
Input: 21H (at 3000H)
Output: 1 (success) in 3001H,
2 (index) in 3002H, and
3 (iteration number) in 3003H.

Test-2: 
Input: 22H (at 3000H)
Output: 2 (failure) in 3001H,
X (don't care) in 3002H, and
4 (iteration before failure) in 3003H 

Успенский —
Предположим, что данные для сравнения хранятся в 3000H, список чисел от 3010H до 3019H, а результаты сохраняются следующим образом: число итераций в 3003H, успех / неудача (1/2) в 3001H и индекс в 3002H

Алгоритм —

  1. Переместите 0 в Accumulator и сохраните его в 3003H, чтобы указать количество итераций на данный момент.
  2. Переместите 0 и 9 в регистры L и H соответственно.
  3. Загрузите данные для поиска в Аккумулятор с 3000H и сдвиньте их в регистр B.
  4. Получите количество итераций из 3003H, увеличьте его на единицу и сохраните в 3003H.
  5. Переместите значение регистра H в Аккумулятор и сравните с регистром L.
  6. Если генерируется перенос, двоичный поиск завершен, поэтому переходите к шагу 20.
  7. Добавьте значение регистра L в аккумулятор и поверните его вправо.
  8. Сохраните значение Аккумулятора в регистре C и установите флаг переноса принудительного сброса, если он установлен.
  9. Загрузите начальный адрес массива в пару регистров DE.
  10. Добавьте значение аккумулятора в регистр E и сохраните результат в E.
  11. Переместите 0 в Аккумулятор и используйте команду ADC, чтобы добавить любой возможный перенос, сгенерированный в результате предыдущего добавления, и сохранить его в Регистре D.
  12. Загрузите значение, на которое указывает пара DE, и сравните с Регистром B. Если генерируется перенос, перейдите к шагу 15, а если установлен флаг Zero, перейдите к шагу 17.
  13. Переместите значение регистра C в аккумулятор и уменьшите значение аккумулятора.
  14. Переместите значение Аккумулятора в H и JUMP обратно к шагу 4.
  15. Переместите значение регистра C в «Аккумулятор» и увеличьте значение «Аккумулятор».
  16. Переместите значение Аккумулятора в L и JUMP обратно к шагу 4.
  17. Переместите 1 в рекламный магазин Аккумулятор в 3001H, чтобы указать на успех.
  18. Переместите значение регистра C в аккумулятор и сохраните его в 3002H, чтобы сохранить индекс.
  19. Прыжок к утверждению 21.
  20. Переместите 2 в Аккумулятор и сохраните его в 3001H, чтобы указать сбой.
  21. Завершить программу.

Программа —

;

AddressLabelInstructionComment
2000HLDA 3000HLoad value to search for
2003HMOV B, ASave it in register B2004HMVI A, 02006HSTA 3003HStore iteration number2009HM0V L, A200AHMVI A, 9200CHMOV H, AStoring high and low indices in H-L pair done200DHstart_loop:LDA 3003HLoad iteration number2010HINR AIncrement iteration number2011HSTA 3003HStore back in 3003H2014HMOV A, HStore high index in Accumulator2015HCMP LCompare with lower index2016HJC loop_endIf carry generated, this means high is less than low so binary search over2019HADD LAdd high to low202AHRARRight rotate to divide by two and generate mid202BHMOV C, ASave mid in register C202CHJNC resetIf carry flag unset, go directly to reset.202FHCMCForce unset carry flag2030HresetNOP2031HLXI D, 3010HLoad start address in D-E pair2034HADD EAdd mid to E to get the offset2035HMOV E, AGet the changed address back in E so it becomes a pointer to arr[mid]2036HMVI A, 0Handle possible overflow2038HADC D2039HMOV D, AMemory index handled203AHLDAX DLoad the array element in accumulator203BHCMP BCompare with value to search203CHJC else_blockImplies value is greater than value at mid, so we need low=mid+1203FHJZ printIf zero flag set, match found. Jump to print block2042HMOV A, CNeither executed so value<mid and we need high=mid-12043HDCR Amid=mid-12044HMOV H, Ah=mid2045HJMP start_loopJump back2046Helse_blockMOV A, CWe need low=mid+12047HINR Amid=mid+12048HMOV A, Ll=mid2049HJMP start_loop204CHprintMVI A, 1Move 1 to Accumulator204EHSTA 3001HStore it in 3001H to indiate success2051HMOV A, CMove index, that is mid, back to Accumulator2052HSTA 3002HStore it in 3002H2055HJMP true_endJump to end of the code2058Hloop_endMVI A, 2205AHSTA 3001HStore 2 in 3001H to indicate failure205DHtrue_endHLTTerminate

Пояснение —

  1. Мы перемещаем значение более высокого и более низкого индекса (в данном случае 9 и 0) в регистры H и L соответственно на шаге 2
  2. Более высокие и более низкие индексы сравниваются на шаге 5. При получении переноса, который указывает низкий> высокий, мы переходим к концу цикла, иначе переходим к шагу 6.
  3. В шагах 7 и 8 мы добавляем значение регистров H и L и поворачиваем его вправо, что эквивалентно (high + low) / 2, чтобы найти индекс, скажем, на языке C
  4. На шаге 10 мы добавляем значение mid к начальному адресу массива, чтобы он действовал как смещение, аналогично тому, как * (arr + x) и arr [x] идентичны в C.
  5. Шаг 11 гарантирует отсутствие переполнения.
  6. На шаге 12 мы сравниваем значение в середине индекса со значением, которое нужно найти. Если он равен, мы выпрыгиваем из цикла и устанавливаем значения соответствующим образом.
  7. Если они не равны, шаг 12 соответственно разветвляется, чтобы позволить нам увеличивать / уменьшать середину на 1 и перемещать это значение в регистр L / H по мере необходимости (точно так же, как выполняется высокий = средний-1 или низкий = средний + 1 в C) и вернитесь к началу цикла, то есть к шагу 2.

Примечание. Этот подход потерпит неудачу, если элемент для поиска будет меньше, чем наименьший элемент в массиве. Чтобы справиться с этим, добавьте дополнительный ноль в начало цикла и переместите значения 10 и 1 в пару HL на шаге 2 соответственно.

Рекомендуемые посты:

Программа 8085 для бинарного поиска

0.00 (0%) 0 votes