Страница 1 из 1
Алгоритм перебора комбинаций (нужна помощь)
Добавлено: 13.01.2010 01:45:02
Rakshas
Задача стоит такая: необходимо выбрать все двоичные комбинации заданной длины с заданным весом.
Например:
длина задана 7, т.е. 0000000
вес - 3
надо выбрать комбинации
Пока реализовал это перебором всех комбинаций заданной длины, и подсчетом веса каждой комбинации.
Подскажите, есть ли другой, более быстрый, алгоритм.
Re: Алгоритм перебора комбинаций (нужна помощь)
Добавлено: 13.01.2010 09:07:47
Vadim
RakshasА если не перебирать всю длину, а создавать заданный вес в этой длине? Например сдвигом сначала одной единички, потом двух, потом всех трёх...
Re: Алгоритм перебора комбинаций (нужна помощь)
Добавлено: 13.01.2010 12:51:32
Putnick
Уважаемый Rakshas,
Поддерживаю Вадима
А если не перебирать всю длину, а создавать заданный вес в этой длине? Например сдвигом сначала одной единички, потом двух, потом всех трёх
и всё это — рекурсивно. Например, так:
Код: Выделить всё
program p9;
var
Dlina, Ves:Integer;
procedure GenStr(s:string; dl, v:integer);
var
i, j:integer;
s1:string;
begin
if V>dl then begin
WriteLn('Вес не может быть больше длины');
exit
end;
for i:=1 to dl-v+1 do begin
s1:='';
for j:=1 to i-1 do s1:=s1+'0';
s1:=s1+'1';
if V=1 then begin
for j:=i+1 to dl do s1:=s1+'0';
WriteLn(s+s1);
end else GenStr(s+s1, dl-i, v-1)
end;
end;
begin
Write('Укажите длину двоичной последовательности: ');
ReadLn(Dlina);
Write('Укажите вес двоичной последовательности: ');
ReadLn(Ves);
GenStr('',Dlina,Ves)
end.
С уважением, Алексей.
Re: Алгоритм перебора комбинаций (нужна помощь)
Добавлено: 14.01.2010 18:44:51
Rakshas
Алексей, Вадим.
Спасибо вам огромное.
Попробую модифицировать Ваш код для применения в своей программе.
С уважением, Сергей.
Re: Алгоритм перебора комбинаций (нужна помощь)
Добавлено: 09.03.2010 09:35:02
Timid
Этот метод будет очень медленным при большой длине числа.
Если длина не превышает 64, то лучше использовать числовое преобразование. Тип cardinal - целое без знака.
Код: Выделить всё
var
l,s:string;
n,m,r,k,i,sm:cardinal;
begin
readln(l,s); // ввод длина,вес
n:=strtoint(l);
m:=Math.IntPower(2,n)-1; // теперь в m - максимальное число в двоичном представлении, вроде 1111111 для 7
r:=strtoint(s);
k:=Math.IntPower(2,r)-1; // теперь в k - минимальное число в двоичном представлении, вроде 111 для 3;
for i:=k to m do begin
sm:=0;
// можно сделать цикл, но будет работать медленно, поэтому лучше "ручками" прописать 64 раза
sm:=sm+(i and 1); // накладываем маску на i, узнаем, есть ли бит в последней позиции
sm:=sm+((i shr 1) and 1); // сдвигаем вправо и накладываем маску - проверяем второй бит (справа)
sm:=sm+((i shr 2) and 2); // проверяем третий бит
.... // <-- здесь продолжаем проверки по образцу выше
if (sm=r) then begin // <-- вес подходит
writeln(IntToBin(i,r)); // <-- функция inttobin выводит целое i как двоичное число с r разрядами, погугли Delphi+IntToBin
end;
end;