Kombinacje - Metoda: "Dziel i zwyciężaj" - Rekurencja
: 14 paź 2016, 19:48
Witam,
Kurcze mam zadanie do wykonania, ale nie wiem za bardzo jak się za nie zabrać.
Sprawa wygląda tak, że, mam sobie jakis prostokąt złożony z 0 i 1.
np.:
010
101
i teraz mam określić na ile sposobów można taki prostokąt podzielić, w taki sposób, aby najmniejsza część składała się minimum jednego zera i jednej jedynki.
Rozwiązanie dla takiego prostokąta to:
5 sposobów:
W ogóle ten wynik jest i ma być w modulo 10^9.
Nie mam pojęcia jak się zabrać za te zadanie, o czym warto poczytać. na razie rozpisuję sobie na kartce różne przykłady bo ten prostokąt może mieć wymiary maksymalne 20x20 i rozkminiam próbując znaleźć jakies zależności lub coś zauważyć po rozpisaniu. Ogarnąłem, że chyba ten pierwszy podział można zrobić po wierszach na: liczba_wierszy - 1, tak samo po kolumnach: liczba_kolumn -1.
Kurcze mam zadanie do wykonania, ale nie wiem za bardzo jak się za nie zabrać.
Sprawa wygląda tak, że, mam sobie jakis prostokąt złożony z 0 i 1.
np.:
010
101
i teraz mam określić na ile sposobów można taki prostokąt podzielić, w taki sposób, aby najmniejsza część składała się minimum jednego zera i jednej jedynki.
Rozwiązanie dla takiego prostokąta to:
5 sposobów:
W ogóle ten wynik jest i ma być w modulo 10^9.
Nie mam pojęcia jak się zabrać za te zadanie, o czym warto poczytać. na razie rozpisuję sobie na kartce różne przykłady bo ten prostokąt może mieć wymiary maksymalne 20x20 i rozkminiam próbując znaleźć jakies zależności lub coś zauważyć po rozpisaniu. Ogarnąłem, że chyba ten pierwszy podział można zrobić po wierszach na: liczba_wierszy - 1, tak samo po kolumnach: liczba_kolumn -1.