[Algorytm] Czy dany wynik jest możliwy?

Gramy w kręgle amerykańskie (bowling).
Dla nieznających zasad skrót:

• jest 10 kręgli
• strącenie kręgla to 1 punkt
• każdy zawodnik oddaje dwa rzuty (frame)
• jeżeli w pierwszym rzucie strącone zostanie 10 kręgli to drugi rzut nie przysługuje, ale punkty zdobyte w dwóch kolejnych rzutach zostają dodane do wyniku uzyskanego w danej ramce (przypadek a)
• jeżeli gracz strąci 10 kręgli w danej ramce, ale w dwóch rzutach to do wyniku ramki zostaje dodany wynik kolejnego rzutu (przypadek b)
• gra składa się z 10 ramek, przy czym jeżeli w ostatniej będzie przypadek a to gracz ma prawo do kolejnego rzutu, jeżeli znowu będzie a to oddaje jeszcze jeden dodatkowy rzut i ustawione jest 10 kręgi. Jeżeli w ostatniej ramce nastąpi przypadek b to gracz oddaje jeszcze jeden dodatkowy rzut i ustawione jest 10 kręgi.

Zadanie:
Napisz algorytm, który pozwoli na określenie jakie rzuty powinien oddać gracz by osiągnąć podany wynik. Ograniczenie gracz MUSI zagrać 10 ramek.

miłego wieczoru życzę, bo problem co najmniej nie trywialny.

Jeżeli masz znaleźć wszystkie kombinacje rzutów, co dadzą dany wynik, to chyba bez brute-force'a się nie obejdzie.

Jeśli masz znaleźć tylko jeden przypadek, to gdzieś do okolic 100 pktów problem jest trywialny, powyżej próbuj końcowymi rzutami zgarniać same premie (co da wynik podzielny przez 10) i w jakiś sprytny sposób dobrać początek, by ostatecznie dopasować się do wyniku. Łatwiej będzie te kijowe rzuty pakować na początek, bo wtedy nie będą miały wpływu na wyniki rzutów premiowanych.

Przykład : 254

Od ramki 3 do ostatniej ściągamy wszystko w pierwszym rzucie, co daje nam 8x30 = 240 pktów
Rzuty z ramek 1 i 2 => po 7 kręgli = 14pktów

Razem : 254

Zapomnij o tym co napisałem, to jest bez sensu ;)

@kamykadze, zacząłeś dobrze. Jeżeli szukamy kombinacji dla wyniku poniżej 90 to zwyczaje dodawanie 9 i ostatnie rzuty tak by się zgadzało.
Podobnie jest z bardzo wysokimi wynikami. Tu szukamy najbliższej wielokrotności 30 i "dopełnienia", następnie najpierw staramy się wypełnić dopełnienie w liczbie rzutów mniejszej niż wielokrotność 30, a następnie same 30. Problemy pojawiają się przy rzutach średnich. Tu metoda wielokrotności 30 jest bardzo słaba ponieważ może się okazać, że ilość ramek do wypełnienia jest za mała.

ps. algorytm jest wredny, a nietrudny ;)

Na poczatku można zagrac tak, żeby cyfra jedności się zgadzała. Potem jak najszybciej dodać resztę liczby. Przecież kręglarz może byc bardzo pechowy i nie trafiać później wcale. :)

w dowolnym języku ?

glpk (programowanie liniowe) spokojnie problem "rozbije"

moja odpowiedź: programowanie w więzach (constraint programing).

jwoj, weź się możę zdecyduj, co? Oba ostatnie posty są Twoje...