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[] k_sumy)
2. {
3.   int k_uzyte = 0, k_max = 0;
4.   int w_uzyte = 0, w_max = 0;
5.   int suma = 0;
6.   foreach (int w in w_sumy)
7.   {
8.     suma += w;
9.     w_max = Math.Max(w_max, w);
10.     w_uzyte += w > 0 ? 1 : 0;
11.   }
12.   foreach (int k in k_sumy)
13.   {
14.     suma -= k;
15.     k_max = Math.Max(k_max, k);
16.     k_uzyte += k > 0 ? 1 : 0;
17.   }
18.   return suma == 0 && k_max <= w_uzyte && w_max <= k_uzyte;
19. }

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

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)
2. {
3.   for (int x = 0; x < macierz.GetLength(0); x++)
4.   {
5.     for (int y = 0; y < macierz.GetLength(1); y++)
6.     {
7.       Console.Write("{0} ", macierz[x, y]);
8.     }
9.     Console.WriteLine();
10.   }
11. }
13. static void Main(string[] args)
14. {
15.   Console.WriteLine("Podaj wymiary n x m:");
16.   string[] data = Console.ReadLine().Split();
17.   int n = Convert.ToInt32(data[0]);
18.   int m = Convert.ToInt32(data[1]);
19.   Console.WriteLine("Podaj sumy wierszy:");
20.   data = Console.ReadLine().Split();
21.   int[] w_sumy = new int[n];
22.   for (int i = 0; i < n; i++)
23.     w_sumy[i] = Convert.ToInt32(data[i]);
24.   Console.WriteLine("Podaj sumy kolumn:");
25.   data = Console.ReadLine().Split();
26.   int[] k_sumy = new int[m];
27.   for (int i = 0; i < m; i++)
28.     k_sumy[i] = Convert.ToInt32(data[i]);
29.   bool czy_istnieje = CzyPoprawneSumy(w_sumy, k_sumy);
30.   if (czy_istnieje)
31.   {
32.     Console.WriteLine("Sumy poprawne");
33.     Console.WriteLine("Przykładowa macierz:");
34.     int[,] macierz = GenerujMacierz(w_sumy, k_sumy);
35.     WypiszMacierz(macierz);
36.   }
37.   else
38.   {
39.     Console.WriteLine("Nie są to poprawne sumy");
40.   }
41.   Console.ReadKey();
42. }

• Kod źródłowy Implementacja