Быстрый поиск
Введите фрагмент названия статьи для поиска
Поиск подстроки в строке по алгоритму Кнута-Морриса-Пратта
11.06.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter
Поиск подстроки в строке по алгоритму Кнута-Морриса-Пратта
Алгоритм Кнута-Морриса-Пратта, он же классический "КМП-алгоритм" - один из самых эффективных алгоритмов поиска подстроки в строке. Оптимизация достигается за счет того, что при возникновении несоответствия само искомое слово содержит достаточно информации, чтобы определить, где может начаться следующее совпадение, минуя лишние проверки. Скорость работы алгоритма линейно зависит от объема входных данных, то есть невозможно разработать более эффективный алгоритм с точки зрения вычислительной сложности.
Читать статью целиком »
Просмотров: 450 | Комментариев: 1
Сортировка перемешиванием на Ассемблере
26.05.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter
Сортировка перемешиванием, она же шейкерная или двунаправленная сортировка - оптимизированная разновидность алгоритма пузырьковой сортировки. В процессе сортировки выполняется многократный проход по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. Массив просматривается поочередно справа налево и слева направо, из-за этого алгоритм получил свое название. В результате каждого прогона крупные и мелкие элементы массива поочередно перемещаются в конец и начало массива соответственно. Границы рабочей части массива, то есть той части массива, где происходит движение, устанавливаются в месте последнего обмена на каждой итерации.Code (Assembler) : Убрать нумерацию
- ;----------------------------------------------------------------
- ; Функция сортировки массива DWORD перемешиванием
- ; by ManHunter / PCL (www.manhunter.ru)
- ;----------------------------------------------------------------
- ; Параметры:
- ; lpArray - указатель на массив DWORD
- ; dLen - количество элементов в массиве
- ;----------------------------------------------------------------
- proc shaker_sort lpArray:DWORD, dLen:DWORD
- pusha
- mov esi,[lpArray]
- ; left
- mov eax,1
- ; right
- mov ebx,[dLen]
- cmp ebx,2
- jb .loc_ret
- dec ebx
- .loc_loop_main:
- ; swap_flag = false
- xor edi,edi
- mov ecx,eax
- .loc_loop_1:
- cmp ecx,ebx
- ja .loc_done_1
- mov edx,dword [esi+ecx*4-4]
- cmp dword [esi+ecx*4],edx
- ; Для сортировки по возрастанию заменить на ja
- jna @f
- push dword [esi+ecx*4-4]
- push dword [esi+ecx*4]
- pop dword [esi+ecx*4-4]
- pop dword [esi+ecx*4]
- ; swap_flag = true
- inc edi
- @@:
- inc ecx
- jmp .loc_loop_1
- .loc_done_1:
- dec ebx
- mov ecx,ebx
- .loc_loop_2:
- cmp ecx,eax
- jb .loc_done_2
- mov edx,dword [esi+ecx*4]
- cmp dword [esi+ecx*4-4],edx
- ; Для сортировки по возрастанию заменить на jb
- jnb @f
- push dword [esi+ecx*4-4]
- push dword [esi+ecx*4]
- pop dword [esi+ecx*4-4]
- pop dword [esi+ecx*4]
- ; swap_flag = true
- inc edi
- @@:
- dec ecx
- jmp .loc_loop_2
- .loc_done_2:
- inc eax
- or edi,edi
- jnz .loc_loop_main
- .loc_ret:
- popa
- ret
- endp
Читать статью целиком »
Просмотров: 282 | Комментариев: 7
Сортировка вставками на Ассемблере
13.05.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter
Сортировка вставками - это алгоритм сортировки, который преобразует массив данных путем поочередного включения каждого элемента в упорядоченную последовательность элементов. Он подразумевает разделение массива на отсортированную и неотсортированную части. На каждом шаге из неотсортированной части выбирается элемент и вставляется в правильное место в отсортированной части. И так продолжается до тех пор, пока весь набор входных данных не будет отсортирован.Алгоритм работает следующим образом. Массив разделяется на две части: отсортированную (в начале пустая) и неотсортированную. На каждом шаге выбирается элемент из неотсортированной части массива. Этот элемент вставляется в отсортированную часть массива так, чтобы отсортированная часть оставалась упорядоченной. Граница между отсортированной и неотсортированной частями смещается, и процесс повторяется для оставшихся элементов. После выполнения всех шагов весь массив становится отсортированным.
Code (Assembler) : Убрать нумерацию
- ;----------------------------------------------------------------
- ; Функция сортировки массива DWORD методом вставок
- ; by ManHunter / PCL (www.manhunter.ru)
- ;----------------------------------------------------------------
- ; Параметры:
- ; lpArray - указатель на массив DWORD
- ; dLen - количество элементов в массиве
- ;----------------------------------------------------------------
- proc insertion_sort lpArray:DWORD, dLen:DWORD
- pusha
- mov esi,[lpArray]
- mov ecx,[dLen]
- xor edi,edi
- inc edi
- .loc_loop_1:
- mov ebx,dword [esi+edi*4]
- mov edx,edi
- dec edx
- .loc_loop_2:
- cmp edx,0
- jb @f
- cmp dword [esi+edx*4],ebx
- jbe @f
- push dword [esi+edx*4+4]
- push dword [esi+edx*4]
- pop dword [esi+edx*4+4]
- pop dword [esi+edx*4]
- dec edx
- jmp .loc_loop_2
- @@:
- mov dword [esi+edx*4+4],ebx
- inc edi
- cmp edi,ecx
- jb .loc_loop_1
- .loc_ret:
- popa
- ret
- endp
Читать статью целиком »
Просмотров: 347 | Комментариев: 0
Конвертирование строки из КОИ-8 в cp1251 и обратно
03.10.2023 | Категория: Образ мышления: Assembler | Автор: ManHunter
Кодировка KOI8-R
КОИ-8 - код обмена информацией - восьмибитовая кодовая страница, разработанная для кодирования букв кириллических алфавитов. КОИ-8 в свое время была широко распространена как основная русская кодировка в UNIX-совместимых ОС и в электронной почте. Существует несколько вариантов КОИ-8, в этой статье я расскажу, как можно конвертировать строку из KOI8-R (русская) в стандартную виндовую кодировку cp1251 и обратно.
Читать статью целиком »
Просмотров: 1522 | Комментариев: 2
Запись числа римскими цифрами на Ассемблере
18.09.2023 | Категория: Образ мышления: Assembler | Автор: ManHunter
Запись числа римскими цифрами на Ассемблере
Задачки на запись натурального числа римскими цифрами очень часто встречаются на различных олимпиадах по программированию. Я решил нарисовать свой вариант решения задачи на Ассемблере.
Натуральные числа записываются при помощи повторения этих цифр. При этом применяется следующее базовое правило: одна и та же букво-цифра не может повторяться в записи числа более 3-х раз подряд. Для этого введены дополнительные двухбуквенные комбинации и, если меньшая букво-цифра стоит перед большей, то меньшая вычитается из большей. В табличке это наглядно видно. Но ограниченный набор букво-цифр приводит к тому, что максимальное число, которое можно записать базовым набором римских цифр, не может превышать десятичного числа 3999 (MMMCMXCIX). Также в римской записи нет нулевого значения, отрицательных и дробных чисел.
Читать статью целиком »
Просмотров: 821 | Комментариев: 0