Ile razy trzeba strzelić kulką, żeby znikły wszystkie?

Definicja klasyczna. Prawdopodobieństwo warunkowe i całkowite. Zmienne losowe i ich parametry. Niezależność. Prawa wielkich liczb oraz centralne twierdzenia graniczne i ich zastosowania.
romaB
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 3 kwie 2013, o 23:18
Płeć: Mężczyzna
Lokalizacja: Polska

Ile razy trzeba strzelić kulką, żeby znikły wszystkie?

Post autor: romaB »

Czesc.

Zalozmy, ze jest taka gra, ktora polega na strzelaniu kulkami (jedna na raz) o N roznych kolorach. Kulki zlepiaja sie do siebie, a jezeli obok siebie stoi M o takim samym kolorze, to te znikaja. Cos jak tutaj, tylko ze uproszczone, w jednym wymiarze a nie dwoch:

Interesuje mnie jak obliczyc prawdopodobienstwo, ze po danej liczbie prob znikna wszystkie kulki (wylaczajac 0, gdy zadna kulka nie zostala wyrzucona).

Zrobilem program, ktory ma to symulowac dla N=2 i M=2. Dla wartosci wiekszych niz 2 nie mialem cierpliwosci, zeby czekac [nie wyglada na to, zeby skonczyl sie w rozsadnym czasie].

Podaje linka do wyniku z 5 prob, liczby 1..2 to kolor1...kolor2:
Awatar użytkownika
Errichto
Użytkownik
Użytkownik
Posty: 1629
Rejestracja: 17 mar 2011, o 18:55
Płeć: Mężczyzna
Lokalizacja: Suwałki
Podziękował: 28 razy
Pomógł: 272 razy

Ile razy trzeba strzelić kulką, żeby znikły wszystkie?

Post autor: Errichto »

Jeśli wypisujesz stan linijka po linijce, to znacznie spowalnia to program (chyba że wypisujesz do pliku). Także usuń wypisywanie - wtedy będzie to działać kilkaset razy szybciej.
Chociaż moim zdaniem program Ci za wiele nie pomoże z tym problemem. Ja bym raczej rozpatrywał to wszystko bez znikania kulek. Masz sobie jakieś ABAABCCCBBA... gdzie literki to kolory. Być może bardzo istotne jest spostrzeżenie, że wyzerowanie wszystkich kulek jest równoważne temu, że na początku i końcu musi być łącznie co najmniej \(\displaystyle{ M}\) liter koloru takiego jak pierwsza, a po wywalenie tych \(\displaystyle{ M}\) liter znowu na początku i końcu musi być łącznie jakieś \(\displaystyle{ M}\) takich samych liter. Możesz sobie to wyobrazić jako strukturę nawiasową - zamieniasz grupkę kulek do zniknięcia na znaki otwarcia i zamknięcia nawiasu. Po otwarciu nawiasu będą się pojawiały jakieś inne kulki ale muszą poznikać do czasu gdy trzeba będzie nawias zamknąć.
np. AABBBCCCA jest dobrym ciągiem liter dla \(\displaystyle{ M=3}\) a w nawiasach wygląda to tak: (()())
No i musisz to sobie przełożyć na problem kolorowych kulek i zrozumieć to.
Powyższe to tylko pomysł, niekoniecznie najlepszy. Problemem na przykład będzie zamknięcie nawiasu przed czasem, np. AABBBABBBAACCCA gdzie pierwsze literki wcale nie parują się z ostatnimi (aczkolwiek na tym przykładzie widać, że nie zmienia to nic w praktyce).
ODPOWIEDZ