Zadanie programistyczne - szukam orginalnej treści


(Grzelix) #1

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.


(Drobok) #2

Była kiedyś taka gra, ale mi się zdaje że odejmowało się cyfry od 1-3 czy jakoś tak, a nie cyfry z liczby.


(kostek135) #3

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.


(soanvig) #4

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 ^^)