Подразделы

Другие разделы

Дата и время

16/11/2024 19:19:30

Авторизация

Зарегистрироваться
Восстановить пароль

8. Перестановки

Сложная задача на динамическое программирование, представление множеств в виде двоичных чисел.

Для нахождения НОД двух чисел используем следующую функцию.

function gcd(a,b:longint):longint;
begin
  if b=0 then gcd:=a
  else gcd:=gcd(b, a mod b);
end;

Чтобы ускорить вычисления, можно заполнить результаты вычисления НОД для элементов множества в таблице.

var
  _gcd:array[1..16,1..16]of longint;
...
  for i:=1 to n do
    for j:=1 to n do
      _gcd[i,j]:=gcd(p[i],p[j]);

Использование при реализации алгоритма динамического программирования запоминающей ранее вычисленные результаты функции позволяет не заботиться о правильном порядке заполнения таблицы с результатами для отдельных подзадач.

Функция count вычисляет количество `k`-перестановок подмножества из элементов, заданных параметром mask (в `j`-м бите числа стоит 1, если в подмножесто входит `(j+1)`-й элемент исходного множества), в которых на первом месте стоит `i`-й элемент исходного множества.

var
  c:array[1..16,1..65535]of int64; { таблица с результатами подзадач }
...
function count(i,mask:longint):int64;
var j:longint;
begin
  if c[i,mask]<0 then { значение еще не вычислялось }
  begin
    c[i,mask]:=0;
    for j:=1 to n do
      if (i<>j) and 
          ((mask and (1 shl (j-1)))<>0) and { есть в подмножестве }
          (_gcd[i,j]>=k) { НОД > k }
      then 
        { j-й элемент можно поставить следующим после i-го }
        c[i,mask]:=c[i,mask]+count(j,mask and not(1 shl (i-1)));
  end;
  count:=c[i,mask];
end;
...
  { начальная заполнение таблицы }
  mask:=(1 shl n)-1;
  for i:=1 to n do
    for j:=1 to mask do
      c[i,j]:=-1; { вычисления не выполнены }
  for i:=1 to n do
    c[i,1 shl (i-1)]:=1; { существует только одна перестановка из одного элемента }

После ввода необходимо отсортировать элементы множества, чтобы рассматривать перестановки в лексикографическом порядке.

var
  p:array[1..16]of longint;
  n,m,k,t,i,j,mask:longint;
...
  read(n,m,k);
  for i:=1 to n do
    read(p[i]);
  for i:=1 to n do
    for j:=i+1 to n do
      if p[i]>p[j] then
      begin
        t:=p[i];
        p[i]:=p[j];
        p[j]:=t;
      end;

После подготовительных операций выбираем, с какого элемента должна начинаться перестановка. Если количество перестановок, начинающихся с `j`-го элемента меньше `m`, рассматриваем в качестве кандидата `(j+1)`-й элемент, при этом из `m` вычитаем количество `k`-перестановок, начинающизся с `j`-го элемента. Если количество перестановок, начинающихся с `j`-го элемента больше или равно `m`, печатаем `j`-й элемент и убираем его из множества. Алгоритм выполняется, пока множество не опустеет, либо не будет найден ни один кандидат на первое место в перестановке.

var fl:boolean;
...
  i:=0; { предыдущий элемент перестановки }
  while mask<>0 do { пока не выведем все элементы из множества }
  begin
    fl:=false;
    for j:=1 to n do
    begin
      if (i<>j) and 
       ((mask and (1 shl (j-1)))<>0) and { есть в подмножестве }
       ((i=0) or (_gcd[i][j]>=k)) { НОД > k или 1 элемент перестановки }
      then
      begin
        if m<=count(j,mask) then 
        begin { попали на нужный элемент }
          write(p[j],' ');
          i:=j;
          mask:=mask and not(1 shl (j-1));
          fl:=true;
          break;
        end
        else
          m:=m-count(j,mask);
      end;
    end;
    if not fl then { нет подходящего элемента }
    begin
      writeln(-1);
      halt(0);
    end;
  end;
  writeln;

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

8. Перестановки