помогите с задачкой

← →
jacksotnik (2011-04-20 14:22) [0]

Есть такая задача:
Решить как минимум двумя способами (простым и быстрым) следующую задачу: написать функцию, которая возвращает количество нулевых бит в символах строки (не считая нулевой символ в конце строки). Значит один способ я сообразил вот собственно он:
function TZero_bits.CountZeroBits(str: string): integer;
var s_bin,bit:string; i,j,symb,zero_count:integer;
begin
zero_count:=0;
for i:=1 to length(str) do
begin
s_bin:="";
symb:=ord(str[i]); //получение десятичного кода символа
//Преобразование в двоичный код
while symb >= 1 do
begin
bit:=IntToStr(symb mod 2);
symb:=symb div 2;
s_bin:=bit+s_bin;
end;
//считаем нулей
for j:=1 to length(s_bin) do
begin
if s_bin[j] = "0" then
inc(zero_count);
end;
end;
result:= zero_count;
end;

А вот второй способ(быстрый) чето совсем догнать не могу. Может кто поможет?

← →
KilkennyCat © (2011-04-20 14:29) [1]

быстро будет, когда все известно. что есть символ? байтовое значение. байт может принимать 255 значений. каждое из этих значений содержит какое-то и всегда одно и тоже количество нулевых бит. Думаю, дальше догадаешься сам.

← →
oldman © (2011-04-20 14:35) [2]

> //Преобразование в двоичный код
> while symb >= 1 do
> begin
> bit:=IntToStr(symb mod 2);
> symb:=symb div 2;
> s_bin:=bit+s_bin;
> end;

symb=10
по твоему алгоритму s_bin="0111"
и это правильно?

← →
oldman © (2011-04-20 14:38) [3]

то есть 0101
а должно быть 1010

← →
oldman © (2011-04-20 14:43) [4]

> байт может принимать 255 значений

может таки 256?
или 0 не считается?

← →
jacksotnik (2011-04-20 14:47) [5]

> symb=10
> по твоему алгоритму s_bin="0111"
> и это правильно?

в моем алгоритме надо выделить каждый символ отдельно и просуммировать в нем количество нулевых бит, к чему ты этот вопрос задал я не пойму. Прочти внимательнее задание. Ну что друзья поможет кто-то с вторым вариантом?

← →
RWolf © (2011-04-20 14:49) [6]

> А вот второй способ(быстрый) чето совсем догнать не могу.
> Может кто поможет?

элементарно подсчитываешь число нулевых бит для каждого символа заранее и складываешь в табличку прямо в исходнике.
при разборе строки просто берёшь готовое число для каждого символа.

← →
jacksotnik (2011-04-20 14:49) [7]

> что есть символ?

ASCII символ. Точнее его двоичный код. Вот надо в двоичном коде посчитать кол-во нулевых бит

← →
jacksotnik (2011-04-20 14:52) [8]

в своем варианте я сначала symb:=ord(str[i]); получаю десятичный код символа потом перевожу десятичное число в двоичную строку и в ней уже считаю нолики

← →
oldman © (2011-04-20 14:53) [9]

> Ну что друзья поможет кто-то с вторым вариантом?

Гугль поможет.

набери в строке поиска "количество нулевых бит в символах строки"

Судя по количеству найденных подобных просьб либо ты на куче форумов, либо задача из учебника.
Копипастить ответы, извини, я не буду.

← →
oldman © (2011-04-20 14:58) [10]

> jacksotnik (20.04.11 14:47) [5]

А тебе не кажется, что слово "бит" что-то значит?
То еcть, для "1" количество нулевых бит равно не 0, а 7,
поскольку не "1", а "00000001"

← →
oldman © (2011-04-20 15:07) [11]

http://www.rsdn.ru/forum/dotnet/3482639.flat.aspx

поможет?

← →
oldman © (2011-04-20 15:15) [12]

zero_count:=0;
a:="87767665.....0" // длина а=256
for i:=1 to length(str) zero_count:=zero_count+a[ord(str[i])]
result:= zero_count;

смешно. предложили аж в [1]
мы ветку не читаем? нам решение нужно копи и пасте?

← →
jacksotnik (2011-04-20 15:26) [13]

для каждого символа заранее прописать кол-во нулей? Этож жесть ето что для всех сидеть и пересчитывать

← →
oldman © (2011-04-20 15:30) [14]

Пуск-Программы-Служебные-Стандартные-Калькулятор
Режим = Инженерный
Набираем число в dec, кликаем на bin
И так 256 раз

Вам шашечки или ехать?

← →
MBo © (2011-04-20 15:36) [15]

>Этож жесть ето что для всех сидеть и пересчитывать
Один раз делаешь это своей же медленной программой, выводя результаты для каждого символа.

← →
jacksotnik (2011-04-20 15:37) [16]

Нашел вот такую функцию вроде все работает только не пойму стабильно для каждого символа показывает нулей на один больше чем надо

function TZero_bits2.GetZeroBitCount(const s: string): integer;
const
//число нулевых бит в тетрадах 0..15
ZBits:array[0..15] of integer = (4,3,3,2, 3,2,2,1, 3,2,2,1, 2,1,1,0);
var
i:integer;
begin
Result:=0;
for i:=1 to Length(s) do
inc(Result,Zbits[byte(s[i]) and 15]+Zbits[byte(s[i]) shr 4]);
end;

← →
Плохиш © (2011-04-20 15:39) [17]

> jacksotnik (20.04.11 14:47) [5]

> Прочти внимательнее задание. Ну что друзья поможет кто-то
> с вторым вариантом?
>

Сколько готов заплатить?

← →
jacksotnik (2011-04-20 15:40) [18]

Нисколько!

> jacksotnik (20.04.11 15:40) [18]
> Нисколько!

Придется платить военкому. Или ректору.

← →
jacksotnik (2011-04-20 15:47) [20]

)))))))) У меня эти времена слава богу уже давно позади

позади военком или ректор?
разжевали уже все. работы на час максимум.

1. Заводишь константу массив [0..255] of byte;
2. В каждый i-й элемент массива прописываешь количество нулей, содержащееся в двоичном представлении i
3. функция приобретает вид
function SumNulBits(const Value: AnsiString): Integer const BitsArray: array [0..255] of byte = (8, 7, 7, 6, 7, 6, ....., 1, 0); var i: Integer; begin Result := 0; for i := 1 to Length(Value) do Result := Result + BitsArray[Ord(Value[i])]; end;4. Не забываешь следить за размером result (дабы за $7FFFFFFF не вышел).

всё.

> для каждого символа заранее прописать кол-во нулей? Этож
> жесть ето что для всех сидеть и пересчитывать

Ты программист, или StringList собачий?
Напиши программку, которая генерит массив констант и сохраняет в текстовый файл.
Хотя (если честно), не факт, что это будет быстрее, чем с калькулятором 256 вариантов перебрать.

> KilkennyCat (20.04.2011 14:29:01) [1]

В военное время 256 значений

> jacksotnik (20.04.2011 14:49:07) [7]

То есть ANSI это уже не символ?

> jacksotnik (20.04.2011 15:47:20) [20]

Значит для другого пишешь?

помогите с задачкой Найти похожие ветки