Версия для печати темы

Автор: Altair 7.05.2009 13:30

Возникла такая задача:
есть число (допустим 8 разрядное, т.е. byte), необходимо определить есть ли в его двоичном представлении разрывы и по возможности определить их длину.
Под разрывом понимается последовательность нулей заключенная между единицами.
Например:
Числа не имеющие разрывов:
00000111₂
00111000₂
имеющие разрывы размера 1:
00101111₂
00000101₂
имеющие разрывы размера 2:
00100111₂
00001001₂

Я думаю суть задачи понятна.

Меня интересует не итерационный (в т.ч. и не рекурсивный) алгоритм решения.
Т.е. в цикле просмотреть все разряды, используя счетчик разрывов и длинны текущего разрыва это понятно, но мне кажется данная задача имеет еще какое-то неочевидное решение.
Допустим задача минимум - вообще определить есть ли хотя бы 1 разрыв ненулевой длинны.
Может быть это возможно сделать используя какие-то свойства чисел?

Автор: volvo 7.05.2009 13:54

Олег,
вообще-то это последовательность: http://research.att.com/~njas/sequences/A089311. Судя по тому, что ничего кроме варианта с циклами для нахождения члена последовательности предложено не было, маловероятно, что такое возможно...

Автор: Altair 7.05.2009 14:32

Спасибо!

Короче буду использовать цикл.


p.s. Ух ничего себе! Целая энциклопедия посвященная числовым последовательностям!

Автор: Altair 7.05.2009 16:47

Вобщем если кому надо будет:

type
 TNumber = byte;

function get_n_bit(x: TNumber; number: byte): byte;
begin

        get_n_bit := byte(((1 shl number) AND x) <> 0);

end;

function set_n_bit(x: TNumber; number: byte): TNumber;
begin

        set_n_bit := x or ( 1 shl number );

end;

function get_len_A089311_sequences(x:TNumber):byte;
{
 Возвращает длинну последовательности нулей в бинарном представлении числа.
 Если последовательности две и более, сумму длин всех.
}
var
 i,j:byte;
 flag:boolean;
 len_window, curr_len_window:byte;
begin
        flag := false; {начало единиц}
        len_window:=0;

        for i := 0 to sizeof(TNumber)*8-1 do begin
                if (get_n_bit(x,i) = 1) and (not flag) then flag := true;
                {
                 Если (get_n_bit(x,i) = 1) and ( flag ) То ничего не делаем, идут единицы
                 Если (get_n_bit(x,i) = 0) and (not flag) То ничего не делаем, идут нули а текущее окно уже посчитано
                }
                if (get_n_bit(x,i) = 0) and (flag) then begin
                        {вычисляем длинну всего окна}
                        j := i;
                        curr_len_window := 0;
                        while (get_n_bit(x,j) = 0) and (j <> sizeof(TNumber)*8-1) do begin
                                curr_len_window := curr_len_window + 1;
                                j:=j+1
                        end;

                        if j <> sizeof(TNumber)*8-1 then len_window := len_window + curr_len_window;

                        flag := false
                end
        end;
        get_len_A089311_sequences := len_window
end;

Тестовая программа

for i:=0 to 21 do begin

             writeln ( i,' = ', get_len_A089311_sequences( i ) );
             
end;

показывает, что считает вроде верно.