Blog. Just Blog

Быстрый поиск

Введите фрагмент названия статьи для поиска

Поиск подстроки в строке по алгоритму Кнута-Морриса-Пратта

11.06.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter

Поиск подстроки в строке по алгоритму Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта, он же классический "КМП-алгоритм" - один из самых эффективных алгоритмов поиска подстроки в строке. Оптимизация достигается за счет того, что при возникновении несоответствия само искомое слово содержит достаточно информации, чтобы определить, где может начаться следующее совпадение, минуя лишние проверки. Скорость работы алгоритма линейно зависит от объема входных данных, то есть невозможно разработать более эффективный алгоритм с точки зрения вычислительной сложности.

Читать статью целиком »
Просмотров: 198 | Комментариев: 1

Сортировка перемешиванием на Ассемблере

26.05.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter
Сортировка перемешиванием, она же шейкерная или двунаправленная сортировка - оптимизированная разновидность алгоритма пузырьковой сортировки. В процессе сортировки выполняется многократный проход по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. Массив просматривается поочередно справа налево и слева направо, из-за этого алгоритм получил свое название. В результате каждого прогона крупные и мелкие элементы массива поочередно перемещаются в конец и начало массива соответственно. Границы рабочей части массива, то есть той части массива, где происходит движение, устанавливаются в месте последнего обмена на каждой итерации.
  1. ;----------------------------------------------------------------
  2. ; Функция сортировки массива DWORD перемешиванием
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;----------------------------------------------------------------
  5. ; Параметры:
  6. ;   lpArray - указатель на массив DWORD
  7. ;   dLen - количество элементов в массиве
  8. ;----------------------------------------------------------------
  9. proc shaker_sort lpArray:DWORD, dLen:DWORD
  10.         pusha
  11.  
  12.         mov     esi,[lpArray]
  13.         ; left
  14.         mov     eax,1
  15.         ; right
  16.         mov     ebx,[dLen]
  17.         cmp     ebx,2
  18.         jb      .loc_ret
  19.  
  20.         dec     ebx
  21.  
  22. .loc_loop_main:
  23.         ; swap_flag = false
  24.         xor     edi,edi
  25.  
  26.         mov     ecx,eax
  27. .loc_loop_1:
  28.         cmp     ecx,ebx
  29.         ja      .loc_done_1
  30.  
  31.         mov     edx,dword [esi+ecx*4-4]
  32.         cmp     dword [esi+ecx*4],edx
  33.         ; Для сортировки по возрастанию заменить на ja
  34.         jna     @f
  35.  
  36.         push    dword [esi+ecx*4-4]
  37.         push    dword [esi+ecx*4]
  38.         pop     dword [esi+ecx*4-4]
  39.         pop     dword [esi+ecx*4]
  40.  
  41.         ; swap_flag = true
  42.         inc     edi
  43. @@:
  44.         inc     ecx
  45.         jmp     .loc_loop_1
  46. .loc_done_1:
  47.         dec     ebx
  48.  
  49.         mov     ecx,ebx
  50. .loc_loop_2:
  51.         cmp     ecx,eax
  52.         jb      .loc_done_2
  53.  
  54.         mov     edx,dword [esi+ecx*4]
  55.         cmp     dword [esi+ecx*4-4],edx
  56.         ; Для сортировки по возрастанию заменить на jb
  57.         jnb     @f
  58.  
  59.         push    dword [esi+ecx*4-4]
  60.         push    dword [esi+ecx*4]
  61.         pop     dword [esi+ecx*4-4]
  62.         pop     dword [esi+ecx*4]
  63.  
  64.         ; swap_flag = true
  65.         inc     edi
  66. @@:
  67.         dec     ecx
  68.         jmp     .loc_loop_2
  69. .loc_done_2:
  70.         inc     eax
  71.  
  72.         or      edi,edi
  73.         jnz     .loc_loop_main
  74.  
  75. .loc_ret:
  76.         popa
  77.         ret
  78. endp
Как и с любыми другими разновидностями пузырьковой сортировки, время выполнения сильно зависит от упорядоченности исходного массива и от количества элементов в нем. Но в любом случае при сортировке перемешиванием сумма сравнений одинакова с пузырьковой сортировкой, а сумма обменов меньше.

Читать статью целиком »
Просмотров: 194 | Комментариев: 7

Сортировка вставками на Ассемблере

13.05.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter
Сортировка вставками - это алгоритм сортировки, который преобразует массив данных путем поочередного включения каждого элемента в упорядоченную последовательность элементов. Он подразумевает разделение массива на отсортированную и неотсортированную части. На каждом шаге из неотсортированной части выбирается элемент и вставляется в правильное место в отсортированной части. И так продолжается до тех пор, пока весь набор входных данных не будет отсортирован.

Алгоритм работает следующим образом. Массив разделяется на две части: отсортированную (в начале пустая) и неотсортированную. На каждом шаге выбирается элемент из неотсортированной части массива. Этот элемент вставляется в отсортированную часть массива так, чтобы отсортированная часть оставалась упорядоченной. Граница между отсортированной и неотсортированной частями смещается, и процесс повторяется для оставшихся элементов. После выполнения всех шагов весь массив становится отсортированным.
  1. ;----------------------------------------------------------------
  2. ; Функция сортировки массива DWORD методом вставок
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;----------------------------------------------------------------
  5. ; Параметры:
  6. ;   lpArray - указатель на массив DWORD
  7. ;   dLen - количество элементов в массиве
  8. ;----------------------------------------------------------------
  9. proc insertion_sort lpArray:DWORD, dLen:DWORD
  10.         pusha
  11.  
  12.         mov     esi,[lpArray]
  13.  
  14.         mov     ecx,[dLen]
  15.         xor     edi,edi
  16.         inc     edi
  17. .loc_loop_1:
  18.         mov     ebx,dword [esi+edi*4]
  19.  
  20.         mov     edx,edi
  21.         dec     edx
  22. .loc_loop_2:
  23.         cmp     edx,0
  24.         jb      @f
  25.         cmp     dword [esi+edx*4],ebx
  26.         jbe     @f
  27.  
  28.         push    dword [esi+edx*4+4]
  29.         push    dword [esi+edx*4]
  30.         pop     dword [esi+edx*4+4]
  31.         pop     dword [esi+edx*4]
  32.  
  33.         dec     edx
  34.         jmp     .loc_loop_2
  35. @@:
  36.         mov     dword [esi+edx*4+4],ebx
  37.  
  38.         inc     edi
  39.         cmp     edi,ecx
  40.         jb      .loc_loop_1
  41. .loc_ret:
  42.         popa
  43.         ret
  44. endp
Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время потребуется для выполнения сортировки. Также на время выполнения влияет исходная упорядоченность массива.

Читать статью целиком »
Просмотров: 232 | Комментариев: 0

Конвертирование строки из КОИ-8 в cp1251 и обратно

03.10.2023 | Категория: Образ мышления: Assembler | Автор: ManHunter

Кодировка KOI8-R

КОИ-8 - код обмена информацией - восьмибитовая кодовая страница, разработанная для кодирования букв кириллических алфавитов. КОИ-8 в свое время была широко распространена как основная русская кодировка в UNIX-совместимых ОС и в электронной почте. Существует несколько вариантов КОИ-8, в этой статье я расскажу, как можно конвертировать строку из KOI8-R (русская) в стандартную виндовую кодировку cp1251 и обратно.

Читать статью целиком »
Просмотров: 647 | Комментариев: 2

Запись числа римскими цифрами на Ассемблере

18.09.2023 | Категория: Образ мышления: Assembler | Автор: ManHunter

Запись числа римскими цифрами на Ассемблере

Задачки на запись натурального числа римскими цифрами очень часто встречаются на различных олимпиадах по программированию. Я решил нарисовать свой вариант решения задачи на Ассемблере.

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

Читать статью целиком »
Просмотров: 723 | Комментариев: 0

prev 01 02 03 04 05 06 07 08 09
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2024
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.08 сек. / MySQL: 3 (0.0046 сек.) / Память: 4.5 Mb
Наверх