| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / 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-14 15:04:00) [21]

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

---

MBo   (2005-12-14 14:53:00) [22]


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;



---

evvcom   (2005-12-14 14:44:00) [23]

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

---

Digitman   (2005-12-14 14:33:00) [24]

function Get BinaryOneCount(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 Get OctalOneCount(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 Get HexadecimalOneCount(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 Get Base/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;

...

---

uzver.exe   (2005-12-14 14:26:00) [25]

Пардон, не уточнил.
Даны числа в Десятичной системе А и В(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 12:47:00) [26]

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;

---

Digitman   (2005-12-14 12:37:00) [27]

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


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


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


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

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

---

evvcom   (2005-12-14 12:17:00) [28]

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

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

---

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

Наверх