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:
Ile razy trzeba strzelić kulką, żeby znikły wszystkie?
- Errichto
- 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?
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).
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).