Witam, nie dawno zasłyszałem zadania programistyczne. Niestety zapamiętałem część i nie jestem pewien czy mam wszystkie potrzebne dane.
Zadanie brzmi tak:
2 graczy. Wybieramy losową liczbę z zakresu 1-100000. Pierwszy gracz wybiera jedną cyfrę z podaj mu liczby (oprócz 0) i odejmuje wartość tej cyfry od podanej liczby. Obliczoną liczbę przekazuje graczowi nr 2 który wykonuje analogiczną operację. Gracze grają optymalnie. Gra kończy się gdy któryś z graczy uzyska 0.
Przykład: Startowa liczba 32:
Możliwe wybory Gracza 1 to 3 lub 2 a więc w kolejnej rundzie może przekazać graczowi drugiemu liczby 29 lub 30.
Nie jestem pewien czy tak wygląda całość zadania, i czy warunek końcowy jest dobrze zdefiniowany. Szukałem chwili w necie ale raczej ciężko po szczątkowych fragmentach zdania. Może ktoś natknął się na takie zadanie, lub kojarzy je z którejś ze stron typu Potyczki algorytmiczne.
Na moje tyle informacji co podałeś wystarczy. Tzn sprawdziłem swoje rozwiązanie dla 2 i 3 cyfrowych liczb, ale ogólny dowód chyba też bym przeprowadził. Więc podejrzewam, że dalej będzie działać. Innym fajnym zadankiem tego typu jest gra w zapałki masz n stosów zapałek. W każdej rundzie gracz musi zabrać co najamniej jedną (ale może wiecej i nie wiecej niż niż jest na stosie oczywiście) zapałkę. Może zabrać tylko z jednego stosu na rundę. I teraz dwa warianty przegrywa ten który bierze ostatni, albo wygrywa (też grają optymalnie, bo nie było by deterministyczne) -> o dziwo rozwiązania nie są symetryczne.
[Edit] ten który ostatni wykona odejmowanie i uzyska zero w wyniku operacji wygrywa, taki wariant rozważałem, bo w przeciwnym przypadku nie jestem pewny.
[Edit2] jednak wariant na przegrywa ten który dokona ostatniego odejmowania w sumie też jest prosty.
Jest też gra, że mamy siedem monet. Gracz który weźmie ostatnią monetę przegrywa. Można brać 1,2,3 monety. (Baldur’s Gate 2, Tron Bhaala, Mefit w Twierdzy Strażnika ^^)