Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Помогите решить плиз... [D7, WinXP]

Страницы: 1 2 >
uzver.exe © (2005-12-14 11:49:00)
Даны числа А, В, К (А,В - от 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 Помогите оптимизировать его...

uzver.exe (2005-12-25 21:53:00) [1]
Люди, уже неделя прошла! Помогите!

uzver.exe (2005-12-15 23:28:00) [2]
Есть здесь кто нибудь?

uzver.exe (2005-12-15 23:28:00) [3]
Есть здесь кто нибудь?

uzver.exe (2005-12-15 19:32:00) [4]
Ау! Люди! Не молчите!

uzver.exe (2005-12-15 17:03:00) [5]
Вот изрядно подкорректированный код, но он всё равно не фурычит:
Покажите как правильно плиз, а то у меня уже крыша едет:
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) то облом
Обьясните где тут недочёт?

pl (2005-12-15 15:21:00) [6]
Я бы вместо 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 13:47:00) [7]
Вот ф-я с - вроде работает, а вот остальное - нет
как следить за знаком К , - если к < 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;

evvcom (2005-12-15 09:11:00) [8]

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

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

MBo (2005-12-15 06:22:00) [9]
>Что за ф-я С(i,k)
Количество сочетаний из i по к

uzver.exe (2005-12-15 00:36:00) [10]
На словах я не совсем понял так что-ли?
Что за ф-я С(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;

MBo (2005-12-14 22:27:00) [11]
>Неужели ни у кого нет никаких идей?
Есть, есть ;)
Практически мгновенно вычислится.
За логарифмическое время для A и B можно посчитать количество подходящих чисел, не превосходящих их, и получить разницу.

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

uzver.exe (2005-12-14 19:36:00) [12]
Неужели ни у кого нет никаких идей?

uzver.exe (2005-12-14 18:02:00) [13]
Для К=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

MBo (2005-12-14 17:26:00) [14]
Кажется, придумал. Сейчас попробую оформить идею.

MBo (2005-12-14 16:55:00) [15]
Для A=0 и B=2^N-1 нужных чисел будет C(n,k), для произвольной границы - сложнее.

uzver.exe (2005-12-14 16:39:00) [16]
А нет ли какой-то математической зависимости кол-ва чисел z от A, B, K?

MBo (2005-12-14 15:57:00) [17]
>Считает слишком долго :(
Мне проще было придумать рекурсивный алгоритм - но рекурсия может притормаживать.

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

uzver.exe (2005-12-14 15:34:00) [18]
И всётаки есть ещё более изящное решение
код MBo © при
А = 1
В = 1 000 000 000
К = 20
Считает слишком долго :(

MBo (2005-12-14 15:34:00) [19]
>uzver.exe
Если получится сделать нерекурсивный алгоритм генерации следующей в колексикографическом порядке комбинации - будет работать быстрее.

uzver.exe (2005-12-14 15:15:00) [20]
Спасибо большое MBo © - Все понял!

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »