nalezy okreslic kiedy i dla ktorego gracza istnieje taktyka wygrywajaca i najlepiej podac ta taktyke
w grę grają 2 osoby, ruchy wykonywane są na zmiane,
do gry potrzebne sa 3 worki w kazdym jest pewna ilosc pereł,
w kadzym ruchu gracz moze zabrac dowolna całkowitą ilosc pereł z dowolnego worka,
przy czym nie moze wyciagac pereł z kilku worków naraz,
przegrywa ten gracz ktory wyciagnie ostatnia perłę
mozna to rozszerzyc na dowolna całkowita ilosc worków.
zadanie to nie jest zadnym zadadniem olimpiskim,natknąłem się jedynie na taką gre i chciałbym wiedzieć jak grac by wygrac, napisalem program ale brute-force ze przy danych rzedu 10, 10, 10 po godzinie nie wypluwa wyniku, licze jednak ze da sie to zrobic sila ludzkiego umyslu.
GRA Z PERŁAMI - taktyka wygrywajaca
-
- Użytkownik
- Posty: 852
- Rejestracja: 23 paź 2004, o 10:17
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Pomógł: 28 razy
GRA Z PERŁAMI - taktyka wygrywajaca
daj na poczatek mniejsze dane zeby zobaczyc czy algorytm jest poprawny
pozniej mozesz probowac optymalizacji algorytmu dla wyzszych wartoci parametrow na podstawie wynikow uzyskanych dla ich nizszych wartosci
btw algorytm napisany iteracyjnie czy rekurencyjnie ?
pozniej mozesz probowac optymalizacji algorytmu dla wyzszych wartoci parametrow na podstawie wynikow uzyskanych dla ich nizszych wartosci
btw algorytm napisany iteracyjnie czy rekurencyjnie ?
GRA Z PERŁAMI - taktyka wygrywajaca
jest poprawny sprawdzalem
rekurencyjnie,
ale to jest glupi bruteforce bo mozna robic bruteforce byle inteligentnie, a ten jest akurat debilny... ,
wolalbym jednak rozwiazanie bez uzycia komputera...
btw zoptymalizuje ten program bo naprawde jest idiotyczny....
rekurencyjnie,
ale to jest glupi bruteforce bo mozna robic bruteforce byle inteligentnie, a ten jest akurat debilny... ,
wolalbym jednak rozwiazanie bez uzycia komputera...
btw zoptymalizuje ten program bo naprawde jest idiotyczny....
- Arbooz
- Gość Specjalny
- Posty: 357
- Rejestracja: 13 gru 2004, o 20:44
- Płeć: Mężczyzna
- Lokalizacja: Białogard/Warszawa
- Podziękował: 3 razy
- Pomógł: 7 razy
GRA Z PERŁAMI - taktyka wygrywajaca
Hmm, ciekawe zagadnienie...
Póki co doszedłem do czegoś takiego:
Sytuacja A: w każdym z worków mamy po jednej perle. Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja B: jeden worek pusty, w dwóch pozostałych mamy po dwie perły. Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja C: w jednym worku jedna perła, w drugim worku dwie perły, w trzecim worku trzy perły. Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja D: jeden worek pusty, w dwóch pozostałych równa ilość pereł (większa od 1). Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja E: jeden worek pusty, w drugim worku jedna perła, w trzecim worku dowolna ilość pereł (większa od 0). Osoba, która teraz wyciąga perły, WYGRYWA.
Moim zdaniem, strategię wygrywającą, może przyjąć gracz, który wykonuje ruch jako pierwszy. W sytuacji, gdy na początku w dwóch workach jest taka sama liczba pereł wyciągamy wszystkie perły z trzeciego worka doprowadzając tym samym do sytuacji D. WYGRALIŚMY
Tą sytuację zostawmy więc, jest ona zbyt prosta
Załóżmy więc, że w każdym worku jest różna ilość pereł. Załóżmy także, że w każdym worku jest conajmniej jedna perła (w przeciwnym razie w pierwszym ruchu moglibyśmy doprowadzić do sytuacji D tym samym WYGRYWAJĄC). Załóżmy także, że w przynajmniej dwóch workach znajduje się więcej niż 3 perły (w przeciwnym razie w pierwszym ruchu moglibyśmy doprowadzić do sytuacji C tym samym WYGRYWAJĄC).
Zatem w tej sytuacji proponuję zacząć od wyciągnięcia pereł z worka, w którym jest ich najmniej, tak, by została w nim jedna perła. Teraz:
a) Jeśli nasz przeciwnik wyciągnie tą jedną perłę, którą my zostawiliśmy, w naszym ruchu możemy doprowadzić do sytuacji D tym samym WYGRYWAJĄC.
b) Jeśli nasz przeciwnik wyciągnie taką ilość pereł, że wyrówna ilości pereł w dwóch pozostałych workach, to my wyciągamy tą jedną perłę, cośmy ją na początku zostawili otrzymując sytuację D kopiąc tym samym przeciwnikowi tyłek (znaczy się WYGRYWAJĄC;))
c) Jeśli nasz przeciwnik będzie się wystrzegał zagrań z wersji a) i b) będzie musiał wyciągać perły z dwóch pozostałych worków tak by liczba pereł w tych workach pozostawała różna. Podobnie będziemy musieli postępować my, żeby role się nie odwróciły Takie granie doprowadzi w końcu do sytuacji A lub C. Pozostaje nam teraz ustalić, jak to rozegrać, żeby wygrać
Póki co mam tyle, ale myślę dalej...
Póki co doszedłem do czegoś takiego:
Sytuacja A: w każdym z worków mamy po jednej perle. Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja B: jeden worek pusty, w dwóch pozostałych mamy po dwie perły. Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja C: w jednym worku jedna perła, w drugim worku dwie perły, w trzecim worku trzy perły. Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja D: jeden worek pusty, w dwóch pozostałych równa ilość pereł (większa od 1). Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja E: jeden worek pusty, w drugim worku jedna perła, w trzecim worku dowolna ilość pereł (większa od 0). Osoba, która teraz wyciąga perły, WYGRYWA.
Moim zdaniem, strategię wygrywającą, może przyjąć gracz, który wykonuje ruch jako pierwszy. W sytuacji, gdy na początku w dwóch workach jest taka sama liczba pereł wyciągamy wszystkie perły z trzeciego worka doprowadzając tym samym do sytuacji D. WYGRALIŚMY
Tą sytuację zostawmy więc, jest ona zbyt prosta
Załóżmy więc, że w każdym worku jest różna ilość pereł. Załóżmy także, że w każdym worku jest conajmniej jedna perła (w przeciwnym razie w pierwszym ruchu moglibyśmy doprowadzić do sytuacji D tym samym WYGRYWAJĄC). Załóżmy także, że w przynajmniej dwóch workach znajduje się więcej niż 3 perły (w przeciwnym razie w pierwszym ruchu moglibyśmy doprowadzić do sytuacji C tym samym WYGRYWAJĄC).
Zatem w tej sytuacji proponuję zacząć od wyciągnięcia pereł z worka, w którym jest ich najmniej, tak, by została w nim jedna perła. Teraz:
a) Jeśli nasz przeciwnik wyciągnie tą jedną perłę, którą my zostawiliśmy, w naszym ruchu możemy doprowadzić do sytuacji D tym samym WYGRYWAJĄC.
b) Jeśli nasz przeciwnik wyciągnie taką ilość pereł, że wyrówna ilości pereł w dwóch pozostałych workach, to my wyciągamy tą jedną perłę, cośmy ją na początku zostawili otrzymując sytuację D kopiąc tym samym przeciwnikowi tyłek (znaczy się WYGRYWAJĄC;))
c) Jeśli nasz przeciwnik będzie się wystrzegał zagrań z wersji a) i b) będzie musiał wyciągać perły z dwóch pozostałych worków tak by liczba pereł w tych workach pozostawała różna. Podobnie będziemy musieli postępować my, żeby role się nie odwróciły Takie granie doprowadzi w końcu do sytuacji A lub C. Pozostaje nam teraz ustalić, jak to rozegrać, żeby wygrać
Póki co mam tyle, ale myślę dalej...
- mgol
- Użytkownik
- Posty: 96
- Rejestracja: 13 sty 2005, o 15:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa / Stalowa Wola
GRA Z PERŁAMI - taktyka wygrywajaca
Podobna gra, tylko z odwróconymi warunkami wygrywającymi i przegrywającymi (i zamiast worków z perłami słupki kwadratów, ale to to samo) to NIM.
GRA Z PERŁAMI - taktyka wygrywajaca
dokladnie, juz to znalazlem z miesiac temu o ty nimie i bardzo prosto wygooglalem sobie i taktyke znalazlem.