IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Рваное ли число?
сообщение
Сообщение #1


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Возникла такая задача:
есть число (допустим 8 разрядное, т.е. byte), необходимо определить есть ли в его двоичном представлении разрывы и по возможности определить их длину.
Под разрывом понимается последовательность нулей заключенная между единицами.
Например:
Числа не имеющие разрывов:
000001112
001110002
имеющие разрывы размера 1:
001011112
000001012
имеющие разрывы размера 2:
001001112
000010012

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

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


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Олег,
вообще-то это последовательность: A089311. Судя по тому, что ничего кроме варианта с циклами для нахождения члена последовательности предложено не было, маловероятно, что такое возможно...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Спасибо! good.gif

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


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


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


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

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;

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


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 19:13
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name