Помогите решить плиз...

← →
uzver.exe (2005-12-14 11:49) [0]

Даны числа А, В, К (А,В - от 0 до 10^9 и К от 0 до 30)
Надо найти кол-во натур чисел между А и В
таких, что кол-во единиц в записи этих чисел равно К

Сразу приходит на ум решение в лоб - то есть перебором

var
a,b,i:longint;
k:byte;
n:byte;{number of "ones"}

function count_one(inp:longint):byte;
var
cnt:byte;
begin
cnt:=0;
while (inp<>0) do begin
inp:=(inp-1) and inp;
cnt:=cnt+1;
end;
count_one:=cnt;
end;

n:=0;
readln(a);
readln(b);
readln(k);
for i:=a to b do begin
if count_one(i)=k then begin
n:=n+1;
end;
end;
writeln("Result is: ",n);

Код работает приемлемо при В-А<1000000 Помогите оптимизировать его...

← →
evvcom © (2005-12-14 12:17) [1]

> Помогите оптимизировать его

Да такое решение не оптимизируешь.
Мне первое, что приходит на ум, это решить эту задачу математически, а компьютер (программу) потом использовать только для того, чтобы посчитать результат полученной функции. Есть такая область в математике, комбинаторика называется, вот ее тебе и надо здесь применить.

← →
Digitman © (2005-12-14 12:37) [2]

> в записи этих чисел

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

> кол-во единиц

каких "единиц"-то ?

десятеричных ? двоичных ? N-чных ?

← →
Digitman © (2005-12-14 12:47) [3]

function GetDecimalOneCount(Value: dword): Integer;
begin
Result :=0;
while (Value > 0) do
begin
if Value mod 10 = 1 then
Inc(Result);
Value := Value div 10;
end;
end;

← →
uzver.exe (2005-12-14 14:26) [4]

Пардон, не уточнил.
Даны числа в Десятичной системе А и В(1≤A≤B≤10^9)
Надо найти кол-во чисел между А и В(A≤Z≤B)
таких, что кол-во единиц в ДВОИЧНОЙ записи этих
чисел было равно некому числу К, заданному в условии(1≤K≤30)

Один из вариантов - свести задачу к нахождению всех
вариантов построения числа z из k слогаемых, каждый из которых
равен двойке в какой либо степени(причём каждый раз новой)

еще пытался воспользоваться замечательным свойством ряда
чисел, вырыжающих кол-во единиц в дв. записи ряда натуральных чисел:
0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

0
0{0+1}
01{0+1}{1+1}
0112{0+1}{1+1}{1+1}{2+1}
01121223{0+1}{1+1}{1+1}{2+1}{1+1}{2+1}{2+1}{3+1}

таким образом:
0
01
0112
01121223
0112122312232334

но пока я зашел в тупик

← →
Digitman © (2005-12-14 14:33) [5]

function GetBinaryOneCount(Value: dword): Integer;
begin
Result :=0;
while (Value > 0) do
begin
if Value mod 2 = 1 then
Inc(Result);
Value := Value div 2;
end;
end;

function GetOctalOneCount(Value: dword): Integer;
begin
Result :=0;
while (Value > 0) do
begin
if Value mod 8 = 1 then
Inc(Result);
Value := Value div 8;
end;
end;

function GetHexadecimalOneCount(Value: dword): Integer;
begin
Result :=0;
while (Value > 0) do
begin
if Value mod 16 = 1 then
Inc(Result);
Value := Value div 16;
end;
end;

...

function GetBase/B>OneCount(Base: Integer; Value: dword): Integer;
begin
Result :=0;
while (Value > 0) do
begin
if Value mod Base = 1 then
Inc(Result);
Value := Value div Base;
end;
end;

...

← →
evvcom © (2005-12-14 14:44) [6]

ниче не понял из твоих уточнений. Смотри комбинаторику. Допустим (на пальцах) у тебя А=0, В = 99, К=1. Тебя устраивают 01, 10, 12..19, 21, 31, ..., 91: итого 18 чисел. Теперь математически. У тебя два знакоместа, на которых может размещаться всего одна единица, т.е. надо найти количество сочетаний 1 из 2 (так вроде это произносится, давно было). Получаешь ответ 2. Теперь на остальных местах может располагаться любая цифра кроме 1, т.е. 9 цифр. Итого 2*9=18.

← →
MBo © (2005-12-14 14:53) [7]

procedure TForm1.Button3Click(Sender: TObject); var NN, KK, A, B, BB, Cnt: Integer; Stop: Boolean; procedure Colex(n, k: Integer; J: DWord); begin if J > B then Exit; if n = 0 then begin if J >= A then Inc(Cnt) end else begin if k < n then begin J := J and not (1 shl (n - 1)); Colex(n - 1, k, J); end; if k > 0 then Colex(n - 1, k - 1, J or (1 shl (n - 1))); end; end; begin KK := 10; Cnt := 0; A := 0; B := 1048575; BB := B; NN := 0; while BB > 0 do begin Inc(NN); BB := BB shr 1; end; if NN >= KK then Colex(NN, KK, 0); Caption := Format("От %d до %d - %d чисел, в дв. записи которых %d ед.", [A, B, Cnt, KK]); end;

← →
uzver.exe (2005-12-14 15:04) [8]

Спасибо, Digitman © за такой развёрнутый ответ!
Но проблема моего кода не в функции Подсчета кол-ва, единиц
а в том, что по сути дела я перебираю все числа между А и В
и проверяю их:
подходят(if (GetBinaryOneCount(i)=k) then ...) - увеличиваю счетчик чисел,
а нет - то не увеличиваю
но если А=0 а В=1 000 000 000 то на выполнение уйдет слишком много времени(для ускорения я воообще отказался от дополнительной ф-и
и делаю подсчет единиц и проверку в теле одного цикла)
Может на ассемблере вставку сделать? хотя врятли это поможет - как сказал evvcom - я не там копаю.

← →
uzver.exe (2005-12-14 15:15) [9]

Спасибо большое MBo © - Все понял!

← →
MBo © (2005-12-14 15:34) [10]

>uzver.exe
Если получится сделать нерекурсивный алгоритм генерации следующей в колексикографическом порядке комбинации - будет работать быстрее.

← →
uzver.exe (2005-12-14 15:34) [11]

И всётаки есть ещё более изящное решение
код MBo © при
А = 1
В = 1 000 000 000
К = 20
Считает слишком долго :(

← →
MBo © (2005-12-14 15:57) [12]

>Считает слишком долго :(
Мне проще было придумать рекурсивный алгоритм - но рекурсия может притормаживать.

Для лексикограф. порядка есть нерекурсивный алгоритм. Попробуй.

← →
uzver.exe (2005-12-14 16:39) [13]

А нет ли какой-то математической зависимости кол-ва чисел z от A, B, K?

← →
MBo © (2005-12-14 16:55) [14]

Для A=0 и B=2^N-1 нужных чисел будет C(n,k), для произвольной границы - сложнее.

← →
MBo © (2005-12-14 17:26) [15]

Кажется, придумал. Сейчас попробую оформить идею.

← →
uzver.exe (2005-12-14 18:02) [16]

Для К=1 искомые Z будут степени двойки:
1 2 4 8 16 32 64 128 и т.д.
Для К=2 искомые Z будут:
3 5 6 9 10 12 17 18 20 24 33 34 36 40 48 65 66 68 72 80 96
Нет ли закономерности в этой последовательности
Если есть, такая ф-я GetZ(position:int):int; то можно будет строить
эту последовательность для произвольного диапазона и К

Что касается поиска путём перестановок, то я представляю себе это так:
Находим Максимальную степень двойки, которая меньше В
Все степени от 0 до Макс становятся алфавитом для размещения в К
позициях, для каждого варианта делаем проверку,
попадает ли Z диапазон A-B - тогда кол-во размещений равно Max!/(Max-k)!
И для больших К придется делать слишком, много проверок z

← →
uzver.exe (2005-12-14 19:36) [17]

Неужели ни у кого нет никаких идей?

← →
MBo © (2005-12-14 22:27) [18]

>Неужели ни у кого нет никаких идей?
Есть, есть ;)
Практически мгновенно вычислится.
За логарифмическое время для A и B можно посчитать количество подходящих чисел, не превосходящих их, и получить разницу.

Идем от старшего бита к младшему. Если i-й бит установлен, добавляем к счетчику C(i,k), декрементируем k.
При этом следим за знаком k и еще за несколькими условиями.

← →
uzver.exe (2005-12-15 00:36) [19]

На словах я не совсем понял так что-ли?
Что за ф-я С(i,k) <=> mod?
Чем искать на произвольном диапазоне -
находим на 0-А и 0-В и вычитаем?

function eval(s,b,k:dword):dword;
var k1, k2, c1, c2, i:dword;
begin

k1:=k; //Для первого числа
for i:=31 to 0 do begin //От старшего к младшему
if (a and 2^i = 2^i) then begin //Если вернула True то на i-ом месте 1
c1:=c1+i mod k;//Что за ф-я такая - C
k1:=k1-1; //Декремент К
end;
end;

k2:=k; //Для второго числа
for i:=31 to 0 do begin
if (b and 2^i = 2^i) then begin
c2:=c2+i mod k;//????
k2:=k2-1; //Декремент К
end;
end;

result:=c2-c1;//Получаем разницу
end;

>Что за ф-я С(i,k)
Количество сочетаний из i по к

> Что за ф-я С(i,k)

Я же писал, читай комбинаторику. C(i, k) = i! / (k! * (i-k)!)

← →
uzver.exe (2005-12-15 13:47) [22]

Вот ф-я с - вроде работает, а вот остальное - нет
как следить за знаком К , - если к < 0 то выходить из цикла или что?

> При этом следим за знаком k и еще за несколькими условиями.

и за какими ещё условиями следить то

function factdivdiv( n, k1, k2 :LONGLONG):LONGLONG; var t,t2,i:LONGLONG; begin // computes (n! / k1! k2!) for combinations // assure k1 >= k2 if (k1 < k2) then begin i := k1; k1 := k2; k2 := i; end; if (k1 > n) then t := 0 else begin // accumulate the factors for k2 factorial t:=1; while (k2 > 1) do begin t := t * k2; k2:=k2-1; end; // accumulate the factors from n downto k1 t2:=1; while (n > k1) do begin t2 := t2 * n; n:=n-1; end; result := t2 div t; end; end; function C( n, r:LONGLONG):LONGLONG; begin // combinations of n things taken r at a time, order not impt. // Comb( n, 0 ) = 1, and Comb( n, n ) = 1 // Comb( n, r ) = 0 if r > n or r < 0 if ((r = 0) or (r = n)) then result:=1 else begin if ((r > n) or (r < 0)) then result:=0 else result:= factdivdiv( n, r, n-r ); end; end; function Sqr2(n:byte):LONGLONG; //Возвращает n-ю степень двойки var i:integer; begin result:=1 ; if n=0 then Exit; for i:=0 to n do result:=result*2; end; function eval(a,b,k:LONGLONG):LONGLONG; var k1, k2, c1, c2:LONGLONG; i:byte; begin k1:=k; //Для первого числа for i:=31 to 0 do begin //От старшего к младшему if (a and Sqr2(i) <> 0) then begin //Если вернула True то на i-ом месте 1 c1:=c1+c(i,k); k1:=k1-1; //Декремент К end; end; k2:=k; //Для второго числа for i:=31 to 0 do begin if (b and Sqr2(i) <> 0) then begin c2:=c2+c(i,k); k2:=k2-1; //Декремент К end; end; result:=c2-c1;//Получаем разницу end;

← →
pl (2005-12-15 15:21) [23]

Я бы вместо for i:=31 to 0 do begin //От старшего к младшему if (a and Sqr2(i) <> 0) then begin //Если вернула True то на i-ом месте 1 c1:=c1+c(i,k); k1:=k1-1; //Декремент К end
написал бы

for i:=63 to 0 do begin
a:=(l shr 1) or (l shl 63);
if (a mod 2 = 1) then begin
c1:=c1+c(i,k);
dec(k1);
end;
end;

и функцию Sqr2 выкинул нафиг

← →
uzver.exe (2005-12-15 17:03) [24]

Вот изрядно подкорректированный код, но он всё равно не фурычит:
Покажите как правильно плиз, а то у меня уже крыша едет:
function eval(a,b:DWORD;k:integer):integer; var k1, k2, c1, c2:integer; i:integer; begin c1:=0; c2:=0; k1:=k; //Для первого числа i:=31; while (i>=0) do begin //От старшего к младшему a:=(a shl 1) or (a shr 31); if ((a and 1)=1) then begin //Если вернула True то на i-ом месте 1 c1:=c1+c(i,k1); k1:=k1-1; //Декремент К if k1<0 then Exit; end; i:=i-1; end; k2:=k; //Для второго числа i:=31; while (i>=0) do begin b:=(b shl 1) or (b shr 31); if ((b and 1)=1) then begin c2:=c2+c(i,k2); k2:=k2-1; //Декремент К if k2<0 then Exit; end; i:=i-1; end; result:=c2-c1;//Получаем разницу end;

Почемуто немного "мажет", то есть почта дает правильный ответ, но
на 1 меньше, пытался C2:=1, но когда кол-во z вообще ноль,
(a=1,b=1,k=5) то облом
Обьясните где тут недочёт?

← →
uzver.exe (2005-12-15 19:32) [25]

Ау! Люди! Не молчите!

← →
uzver.exe (2005-12-15 23:28) [26]

Есть здесь кто нибудь?

← →
uzver.exe (2005-12-15 23:28) [27]

Есть здесь кто нибудь?

← →
uzver.exe (2005-12-25 21:53) [28]

Люди, уже неделя прошла! Помогите!

Помогите решить плиз... Найти похожие ветки