Перебор чисел

From

Eugene Anuchin (2:5070/96.2)

To

Dmitriy Gerasimenko

Date

2002-07-21T01:30:04Z

Area

RU.ALGORITHMS

Hi, Dmitriy !

 19 Июл 02 14:19, Dmitriy Gerasimenko wrote to All:

 DG> И спросил у меня радиотехник: "....нужно код разгадать у
 DG> магнитолки.... цифери я узнал, нужно сделать перебор." Спрошено -
 DG> сделано, причём с удовольствием. Код 4-ёх значный = 2514. N=
 DG> 4 Вложенные циклы отпадают, т.к. чем больше N тем больше
 DG> гемор....

 DG> Привожу код на С (Borlabd C++ 3.1 for DOS), который возможно и лучше
 DG> можно было сделать, а ? или нельзя ?

Я использовал рекурсию, программа находит все перестановки произвольной строки символов. Предполагается что все символы различны. Компилировалось fasm'ом. http://fasm.metro-nt.pl/fasm.zip (~200kb). Imho, получился довольно изящный и короткий (53 байта) алгориитм... Для строки '0123456789' выдает честных 3628800 перестановок менее чем за секунду (ессно без вывода на консоль). фича: после последней перестановки строка принимает первоначальный вид, как до перестановок.

        org 100h
        xor ch,ch   ;обнуляем старший байт счетчика
        mov bl,cnt  ;кол-во символов
        mov dx,buf  ;начало строки
        mov ah,9    ;печать в stdout
        int 21h
;----------------------
recur:  mov bh,bl   ;выполняем bh <- bl раз основной цикл
        dec bl      ;выполняем (bl-1) раз подпрограмму
next:   cmp bl,1    ;проверка концевика
        jna konec   ;если <=1, то перестаем вызывать подпрограмму
        push bx     ;иначе сохраняем оба счетчика
        call recur  ;вызываем подпрограмму
        pop bx      ;восстанавливаем оба счетчика
konec:  mov cl,bl   ;кол-во символов для сдвига
        mov di,dx   ;адрес приемника
        mov si,dx   ;адрес источника (след.символ)
        inc si
        mov al,[di] ;сохраняем младший символ, который щаз затрется
rep     movsb       ;сдвигаем 'сх' символов в младшие адреса
        stosb       ;сохраненный младший символ пишем в старший адрес
        dec bh      ;уменьшаем счетчик кол-ва проходов
        jnz print
        ret         ;если ноль, то выход из подпрограммы
print:  int 21h
        jmp next    ;следующий проход
;-----------------------------
buf     db  'abcd'  ;массив. вместо 'abcd' подставь '2514'
cnt = $-buf         ;количество элементов
        db 13,10,'$'



... Life - Sucks!
--- Не подохнешь - пpивыкнешь, не пpивыкнешь - подохнешь! (М. Жванецкий)
 * Origin: `Wireless' Евгений ael @irk. ru (2:5070/96.2)