[zwei]

#kombinatoryka #matematyka

nk, bo mi już mózg paruje

na ile sposobów można podmienić sekwencję n jedynek dwójkami lub trójkami, np.

11 -> jedna możliwość: 2
111 -> trzy możliwości: 21, 12, 3
1111 -> sześć możliwości: 211, 121, 112, 22, 31, 13
Ja bym to rozbił na takie podproblemy: zastępowanie samymi dwójkami, samymi trójkami, dwójkami i trójkami
No i teraz nie za bardzo wiem, jak to zliczać :/

Jedną dwójkę można podstawić na n-1 sposobów, jedną trójkę na n-2 sposobów
No i dalej mam pustkę we łbie xD bo wchodzą jakieś #!$%@?łe powtórzenia

[deryt]

@zwei:
Rozumiem że 4-ki 5-ki już nagle nie wchodzą w grę?
Jeśli wchodzą to easy, wyobrażasz sobie że 1-ki to piłki a pomiędzy nimi deski oznaczające nowe liczenie - deska jest lub nie ma, więc sposobów jest 2^(n-1)
Jeśli nie, to bardzo dziwne ograniczenie, zadanie jest skomplikowane i może nie być wzoru.

[zwei]

@deryt: tylko dwójki i trójki. Zadanie, które wygenerowało mi ten problem wymagało tylko policzenia tego do sekwencji czterech jedynek (zresztą dało się rozwiązać innym sposobem, ale ja obrałem taką drogę xd), więc sobie to po prostu rozpisałem, ale miło by było poznać wzór na to, to byłoby bardziej elegancko.

[deryt]

@zwei:
Po pierwsze twoje liczby są zaniżone o 1, bo same 1 to też rozwiązanie. Najwyżej sobie odejmiesz 1 na końcu.
Rekurencyjnie:
Szukamy R(n+1)- ilość sposobów dla n+1 jedynek, znając poprzednie.

Wszystkie (n+1) ciągi rozbijemy na 3 grupy w zależności czym się ten ciąg kończy:

Jeśli coś jest dobrym n-ciągiem, to dopisujemy "1" na końcu i jest dobrym (n+1) ciągiem.
Jeśli coś jest dobrym (n-1)-ciągiem, to dopisujemy "2" na końcu i

[zwei]

@deryt: matko boska xD dzięki, coś tak czułem, że sam bym nie dał rady