dp. Mozliwosci przejscia labiryntu przy pomocy kostki.

pytanie zadane 5 czerwca 2017 w C i C++ przez maciek259 Nowicjusz (240 p.)
zamknięte 9 czerwca 2017 przez maciek259

Potrzebuje pomocy w zadaniu:

Chcesz ukraść skarb faraona, znajdujący się na ostatnim polu w tablicy. Każde pole może zawierać pułapkę(posiada wtedy wartość '0') Możesz się poruszać tylko przy rzucie kostką, czyli od 1 do 6 pol na przód. Jeśli trafisz na pułapkę lub wyjdziesz na pole za skarbem- umierasz. Na ile różnych sposobów możesz dojść do skarbu?

Wejscie:

N-liczba pól w zakresie int. K-odpowiedź musi być reszta z dzielenia możliwych dróg przez K. String zawierający same '1' i '0' bez odstępow. Przykładowo dla n=7 k=21 I stringa 1101001 odpowiedzia jest 4.

Napisałem to rekreacyjnie, ale nie umiem przyspieszyć tego programu. Proszę o jakąś poradę na optymalizację tego kodu.

https://pastebin.com/v1zNVvyB

komentarz zamknięcia: Rozwiązane

1 odpowiedź

odpowiedź 6 czerwca 2017 przez d0n Mądrala (6,440 p.)
wybrane 9 czerwca 2017 przez maciek259

Najlepsza

Napisany przez ciebie kod ma wykładniczą złożoność obliczeniową. Po prostu generujesz wszystkie możliwości, i to nie tylko te, które pozwalają dojść do celu. Złożoność twojego rozwiązania to O(6^n). Zadanie to da się rozwiązać liniowo, właśnie za pomocą dynamic programming. Zastanów się jak mając informacje na ile sposobów dojść do pola nr 1, obliczyć na ile sposobów przejść do pola nr 2, potem nr 3 i uogólnij liczenie na ile sposobw da sie dojsc do pola j, mając obliczone na ile sposobów dojsc do pól od 1 do j - 1. Jeżeli nie dojdziesz do tego jak to zrobic, to pytaj w komentarzu.

Finalnie najwazniejsza czesc rozwiazania moze sie zawrzec w 5 linijkach kodu. powodzenia :)

komentarz 7 czerwca 2017 przez maciek259 Nowicjusz (240 p.)

Myślałem nad tym, ale każda formuła o jakiej pomyślałem dawała na dłuższą metę błędne wyniki. Mógłbym prosić o ten sposób na liczenie możliwości przejście na n-te pole? Myślałem o jakichś skojarzeniach z Fibonaccim albo potegach dwójki, niestety nie dało mi to rozwiązania.

komentarz 7 czerwca 2017 przez d0n Mądrala (6,440 p.)

Chodzi o to, że:
ilość sposobów na jakie da się dojść do pola 'j' = (ilość sposobów na jaki da się dojść do pola 'j - 1') + (ilosc sposobow na jaki da sie dojsc do pola 'j - 2') + .... + ( ilosc sposobow na jaki da sie dojsc do pola j - 6)
Wyjatkami sa pola pulapki, gdzie nie liczymy tego co powyzej tylko po prostu zapisujemy 0, trzeba pamietac, że jezeli j równe powiedzmy 3, to nie mozemy się odnieść do np. tab[j - 6], co mozna latwo pominac robiac za duza tablice i zostawiajac na poczatku zera.