Текущ брой на Списание ИнфоМан
 


НОИ 2005 - 2 кръг, Задача A2. МАТРИЦИ

Условието на задачата може да прочетете тук.

Решение

Първо, лесно се забелязва, че матрица с 9 реда и 9 стълба с по една единица във всеки ред и стълб е разделящ код, затова се опитваме да построим кодове с повече от 9 стълба.

Ще разгледаме алгоритъм за решаване на задачата, който използва рекурсия, за да генерира отговора, но работи достатъчно бързо (от порядъка на няколко минути). Решението се базира на следните две важни наблюдения. На първо място, ако имаме някакъв разделящ код и разменим по произволен начин два реда или два стълба, получената матрица продължава да бъде бъде разделящ код. Това се вижда лесно – изискванията на условието на задачата не се нарушават.

Второ, ако имаме решение, можем чрез краен брой размени на местата на редове и стълбове да получим ново решение, за което както редовете, така и стълбовете са сортирани лексикографски. Достатъчно е да сортираме стълбовете, след това редовете, после отново стълбовете и след това редовете и т.н.

Следователно, можем да разглеждаме само матрици, в които редовете и стълбовете са подредени лексикографски. Тогава първият стълб е от вида 00...011...1.

В програмата стълбовете и редовете са представени за удобство с двоични числа, вместо с низове. От свойството на разделящите кодове следва, че няма еднакви стълбове.

След като генерираме поредния стълб, проверяваме дали условията са изпълнени, т.e. дали редовете са в нарастващ ред и матрицата продължава да отговаря на изискванията за разделящ код (забележете, че е достатъчно да проверим само дали включването на новия стълб запазва свойството, като няма нужда да проверяваме всички тройки стълбове, а само всички двойки стари стълбове плюс новия стълб). Ако е така, преминаваме рекурсивно към генериране на следващия стълб.

След работа на посочения алгоритъм се оказва, че най-добрият отговор на задачата съдържа 12 стълба.

Лесно може да направим следното допълнително подобрение. Нека броят на единиците в първия стълб е w. Програмата последователноразглежда случаите w=1,2,…,9. Ако в матрицата има стълб с по-малко от w единици, може да го преместим на първо място и като сортираме редовете ще стигнем до вече разглеждан случай. Затова е достатъчно да разглеждаме само стълбове, които иматпоне w единици.

Примерна реализация:

#include <iostream>
using namespace std;

const int M = 9; // number of rows
const int N =20; // max number of columns
const int COL_MAX = (1<<M)-1; // = 111111111(2)

int Col[N]; // columns as binary numbers
int Row[M]; // rows as binary numbers
/* Up to equivalence we are looking for
   matrices such that Col[0]<Col[1]<...<Col[n]
   and Row[0]<Row[1]<...<Row[M-1]
*/

int nMax=9; // A trivial solution with 9 columns is known.

void makeRows(int n)
{ for(int i=0; i<M; i++)
  { Row[i]=0;
    for(int j=0; j<=n; j++)
    { Row[i] <<= 1;  // shift left
      if(Col[j] & (1<<(M-1-i))) Row[i] += 1;
    }
  }
}

bool okSort(int n)
{ for(int i=0; i<M-1; i++)
    if(Row[i]>Row[i+1]) return 0;
  return 1;
}

bool okCode(int n)
{ int p,q,u;
  for(p=0; p<=n-2; p++)
    for(q=p+1; q<=n-1; q++)
    { if(( Col[p] & ~Col[q] & ~Col[n])==0) return 0;
      if((~Col[p] &  Col[q] & ~Col[n])==0) return 0;
      if((~Col[p] & ~Col[q] &  Col[n])==0) return 0;
    }
  return 1;
}

void showCode(int n)
{ cout << "n = " << n+1 << endl;
  for(int i=0; i<M; i++)
  { for(int j=0; j<=n; j++)
      if (Row[i] & (1<<(n-j))) cout << "1 ";
      else cout << "0 ";
    cout << endl;
  }
}

void genCol(int n)
{ for(int x=Col[n-1]+1; x<=COL_MAX; x++)
    { Col[n]=x;
      makeRows(n);
      if(okSort(n) && okCode(n))
      { if(n+1>nMax)
        { nMax=n+1; showCode(n); }
        genCol(n+1);
      }
    }
}

void main()
{ for(int w=1; w<=M; w++)
  { Col[0]=(1<<w)-1; // = 00...011..1 with M-w 0's and w 1's
    genCol(1);
  }
  cout << "Press Enter..."; cin.get();
}

Автор: Стоян Капралов


обратно към брой 27