szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 15 gru 2004, o 01:14 
Użytkownik

Posty: 453
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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 15 gru 2004, o 14:32 
Gość Specjalny

Posty: 852
Lokalizacja: Lublin
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 ?
Góra
Mężczyzna Offline
PostNapisane: 15 gru 2004, o 16:04 
Użytkownik

Posty: 453
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....
Góra
Mężczyzna Offline
PostNapisane: 25 gru 2004, o 20:30 
Gość Specjalny
Avatar użytkownika

Posty: 357
Lokalizacja: Białogard/Warszawa
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 :P

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ć :D

Póki co mam tyle, ale myślę dalej... ;)
Góra
Mężczyzna Offline
PostNapisane: 14 sty 2005, o 12:56 
Użytkownik
Avatar użytkownika

Posty: 96
Lokalizacja: Warszawa / Stalowa Wola
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.
Góra
Mężczyzna Offline
PostNapisane: 14 sty 2005, o 16:16 
Użytkownik

Posty: 453
dokladnie, juz to znalazlem z miesiac temu o ty nimie i bardzo prosto wygooglalem sobie i taktyke znalazlem.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Najlepsza taktyka to gry z przedziałami.  valdemaar  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl