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. def CzyPoprawneSumy(w_sumy, k_sumy):
2.   k_uzyte = 0
3.   k_max = 0
4.   w_uzyte = 0
5.   w_max = 0
6.   suma = 0
7.   for w in w_sumy:
8.     suma += w
9.     w_max = max(w_max, w)
10.     w_uzyte += 1 if w > 0 else 0
11.   for k in k_sumy:
12.     suma -= k
13.     k_max = max(k_max, k)
14.     k_uzyte += 1 if k > 0 else 0
15.   return suma == 0 and k_max <= w_uzyte and w_max <= k_uzyte

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. def GenerujMacierz(w_sumy, k_sumy):
2.   n = len(w_sumy)
3.   m = len(k_sumy)
4.   macierz = []
5.   for x in range(n):
6.     macierz.append([0] * m)
7.     for y in range(m):
8.       if(w_sumy[x] > 0 and k_sumy[y] > 0):
9.         macierz[x][y] = 1
10.         w_sumy[x] -= 1
11.         k_sumy[y] -= 1
12.   return macierz

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. def WypiszMacierz(macierz):
2.   for wiersz in macierz:
3.     print(*wiersz)
5. print("Podaj wymiary n x m:")
6. n, m = [int(x) for x in input().split()]
7. print("Podaj sumy wierszy:")
8. w_sumy = [int(x) for x in input().split()]
9. print("Podaj sumy kolumn:")
10. k_sumy = [int(x) for x in input().split()]
11. czy_istnieje = CzyPoprawneSumy(w_sumy, k_sumy)
12. if (czy_istnieje):
13.   print("Sumy poprawne")
14.   print("Przykładowa macierz:")
15.   macierz = GenerujMacierz(w_sumy, k_sumy)
16.   WypiszMacierz(macierz)
17. else:
18.   print("Nie są to poprawne sumy")

• Kod źródłowy Implementacja