Sumy Binarnej Macierzy

Zadanie

Sprawdź czy istnieje macierz binarna (tj. jej wartości to tylko 0 lub 1) poprzez podaną sumę wartości każdego wiersza i kolumny. Jeśli taka macierz istnieje to podaj przykładową macierz spełniająca zadane warunki.

Przykład

Przypuśćmy, że dal pewnej macierzy suma wierszy wynosi [3, 5, 3, 2], a suma kolumn to odpowiednio [2, 3, 2, 3, 3]. Macie opisana przez takie sumy istnieje. Przykładowo:

1. 0 1 1 0 1
2. 1 1 1 1 1
3. 0 0 1 1 1
4. 1 0 0 1 0

Implementacja

Poprawność danych

Do poprawnego zaprogramowania omawianego zadania należy wpierw wyjaśnić z czego wynikają sumy. Po pierwsze każda wartość "1" wpływa zarówno na wartość sumy w danym wierszu oraz sumy w danej kolumnie. Innymi słowy suma sum kolumn i wierszy musi się zgadzać. Ponadto suma wierszy może być maksymalnie taka jaka ilość niezerowych kolumn oraz analogicznie dla sum kolumn. Wynika to z faktu, że jeśli są 3 niezerowe kolumny to maksymalna suma w danym wierszu to 3. Oczywiście może być mniejsza lub równa, ale nie może być większa.

1. static bool CzyPoprawneSumy(int* w_sumy, int n, int* k_sumy, int m)
2. {
3.   int k_uzyte = 0, k_max = 0;
4.   int w_uzyte = 0, w_max = 0;
5.   int suma = 0;
6.   for(int i = 0; i < n; i++)
7.   {
8.     int w = w_sumy[i];
9.     suma += w;
10.     w_max = std::max(w_max, w);
11.     w_uzyte += w > 0 ? 1 : 0;
12.   }
13.   for (int i = 0; i < m; i++)
14.   {
15.     int k = k_sumy[i];
16.     suma -= k;
17.     k_max = std::max(k_max, k);
18.     k_uzyte += k > 0 ? 1 : 0;
19.   }
20.   return suma == 0 && k_max <= w_uzyte && w_max <= k_uzyte;
21. }

W celu uniknięcia deklarowania dwóch zmiennych sumy wierszy są dodawane do zbiorczej zmiennej, a sumy kolumn odejmowane. Jeśli zmienna na koniec ma wartość 0 to znaczy, że sumy były sobie równe. Dodatkowo przeglądając sumy wiersz i kolumn wyszukiwane jest równocześnie ich maksimum oraz ile zostało użytych wierszy/kolumn. Na koniec sprawdzamy czy któryś wiersz/kolumna nie chciał wykorzystać więcej kolumn/wierszy niż było to możliwe.

Generowanie macierzy

Po sprawdzeniu danych wejściowych można na ich podstawie wygenerować binarną macierz. Zadanie to sprowadza się do przejrzenia każdego pola i ustawieniu go na 1 tylko wtedy, gdy w danym wierszu oraz kolumnie pola sumy pozostają niezerowe.

1. static int** GenerujMacierz(int* w_sumy, int n, int* k_sumy, int m)
2. {
3.   int** macierz = new int*[n];
4.   for (int x = 0; x < n; x++)
5.   {
6.     macierz[x] = new int[m];
7.     for (int y = 0; y < m; y++)
8.     {
9.       if (w_sumy[x] > 0 && k_sumy[y] > 0)
10.       {
11.         macierz[x][y] = 1;
12.         w_sumy[x]--;
13.         k_sumy[y]--;
14.       }
15.       else {
16.         macierz[x][y] = 0;
17.       }
18.     }
19.   }
20.   return macierz;
21. }

Powyższy algorytm generuje tylko jedną z wielu możliwych macierzy, które spełniają warunki zadania. Jako zadanie dodatkowe warto spróbować napisać program, który wypisze wszystkie możliwe macierze.

Testowanie funkcji

Poniższy kod wczytuje dane od użytkownika, a następnie sprawdza czy na ich podstawie może istnieć macierz binarna zgodna z warunkami zadania. Jeśli tak to dodatkowo zostanie wygenerowana macierz.

1. static void WypiszMacierz(int** macierz, int n, int m)
2. {
3.   for (int x = 0; x < n; x++)
4.   {
5.     for (int y = 0; y < m; y++)
6.     {
7.       std::cout << macierz[x][y] << " ";
8.     }
9.     std::cout << std::endl;
10.   }
11. }
13. int main()
14. {
15.   int n, m;
16.   std::cout << "Podaj wymiary n x m:\n";
17.   std::cin >> n >> m;
18.   std::cout << "Podaj sumy wierszy:\n";
19.   int* w_sumy = new int[n];
20.   for (int i = 0; i < n; i++)
21.     std::cin >> w_sumy[i];
22.   std::cout << "Podaj sumy kolumn:\n";
23.   int* k_sumy = new int[m];
24.   for (int i = 0; i < m; i++)
25.     std::cin >> k_sumy[i];
26.   bool czy_istnieje = CzyPoprawneSumy(w_sumy, n, k_sumy, m);
27.   if (czy_istnieje)
28.   {
29.     std::cout << "Sumy poprawne\n";
30.     std::cout << "Przykladowa macierz:\n";
31.     int** macierz = GenerujMacierz(w_sumy, n, k_sumy, m);
32.     WypiszMacierz(macierz, n, m);
33.   }
34.   else
35.   {
36.     std::cout << "Nie sa to poprawne sumy";
37.   }
38. }

• Kod źródłowy Implementacja