Użytkownik "vonBraun" <i...@g...pl> napisał w wiadomości
news:gd5tg5$cl$1@inews.gazeta.pl...
> Redart wrote:

> Mnie się pierwsza faza zadania "imaginowała" jako połówkowanie,
> połówkowanie połówek, połówkowanie połówek połowek itd. a potem
> jako objęcie maksymalnie zróżnicowanym wzorcem zapytań pozostałych
> jak np tu:
> 7 11 13 14 15
> x x x o o
> o x o x o
> x x o o o
>
>
> (co daje jeszcze jedna działającą końcówkę: hehe ale fajnie
> 5. Is the number in: 7, 11, 13?
> No
> 6. Is the number in: 11, 14?
> No
> 7. Is the number in: 7, 11?
> No
> Your guess was 15.
> )
> Ale na "bitach" o tym nie myślę :-(
> vB

;)))
Wczoraj już w łóżeczku, znalazłem algorytm, dzięki któremu działa metoda
Farta-Trenera ;)))
I w dodatku jest to metoda bardzo prosta, nie musimy sobie przygotowywać
zbiorów o
złożonych cechach i a bardzo kombinować. A z pewnością jest PEWNA ;)

Metoda opiera się na metodzie połówkowej eliminacji, ale wprowadzamy
dodatkowy zbiór pomocniczy
aby pracować z niepewnością.
A metoda wyglada tak:
Trzymamy liczby w trzech zbiorach:
C - zbiór 'czysty'
K - zbiór podejrzany, 'kwarantanna'
S - zbiór spalony, te liczby na pewno nie są rozwiązaniem.

0. Na początku wszystkie nasze liczby wrzucamy do C (nie mamy co do nich
żadnych wątpliwości).
I wykonujemy iterację:
1. Bierz połowę(dowolną ;) liczb ze zbioru czystego C oraz połowę z
kwarantanny K i wrzucaj do pytania.
Dodatkowe założenie, ważne w końcówce: jeśli zbiory nie dają się dzielić
dokładnie na pół, np. w C masz tylko
jeden element, to jeśli bierzesz z C ten element, to z K bierzesz o jeden
mniej. Jeśli np. w obu zbiorach masz
po jednej liczbie, to wybierasz tylko jedną z nich. Chodzi o to, by na końcu
nie utknąć na takich samych pytaniach
o dwie pozostałe liczby w C i K, jeśli nie ma już ich jak podzielić.

2. Jeśli odpowiedź jest NIE, to:
- wszystkie liczby z K o które pytaliśmy stają się spalone (przerzucamy do
S - wyczerpały limit zaufania :)
- wszystkie liczby z C o które pytaliśmy stają się podejrzane (przerzucamy
do kwarantanny K - utraciły pełne zaufanie)
Jeśli odpowiedź jest TAK, to działamy identycznie, ale nasze zaufanie spada
co do liczb, których nie było w zapytaniu:
- wszystkie liczby z K o które _nie_ pytaliśmy stają się spalone
(przerzucamy do S - wyczerpały limit zaufania :)
- wszystkie liczby z C o które _nie_ pytaliśmy stają się podejrzane
(przerzucamy do kwarantanny K - utraciły pełne zaufanie)
3. Jeśli masz jeszcze co dzielić - wracaj do 1.

Algorytm prowadzi nas jak po sznurku do sytuacji, w której w najgorszym
wypadku w kwarantannie zostaje tylko jedna
'niepewna' liczba i z braku alternatyw stanowi ona rozwiązanie.

Nie ma drogi 'wstecz', czyli metody 'przywracania zaufania' - dlatego
zbiorem spalonych możemy się
w ogóle nie zajmować. Interesują nas tylko C i K. Bierzemy na stół
rozwiązanie wskazane przez trenera:

C={0123456789ABCDEF} K={}
Wybieramy z C 0-7, z K nie mamy nic do wybrania:
1. Is the number in: 0, 1, 2, 3, 4, 5, 6, 7?
Yes
Przerzucamy do K i mamy:
C={01234567} K={89ABCDEF}
Wybieramy z C 4567, z K wybieramy 89AB:
2. Is the number in: 4, 5, 6, 7, 8, 9, 10, 11?
Yes
Z K wypadają CDEF, z C przerzucamy 0123 i mamy:
C={4567} K={012389AB}
Wybieramy z C 45, z K wybieramy 0123
3. Is the number in: 0, 1, 2, 3, 4, 5?
Yes
Z K wypadają 89AB, z C przerzucamy 67:
C={45} K={012367}
Z C wybieramy czwórkę, z K wybieramy 123:
4. Is the number in: 1, 2, 3, 4?
Yes
Piątka przelatuje do K, 067 idzie w zapomnienie. Pozostaje:
C={4} K={1235}
C już nie daje siędzielić. Bierzemy więc ten element z C a z K bierzemy 'o
jeden mniej', czyli 1 zamiast dwóch
(choć imho tu jeszcze nie jest to konieczne, moglibyśmy wziąć dwie).
5. Is the number in: 4, 5?
Yes
Ta odpowiedź powoduje, że w C nic się nie zmienia, ale z kwarantanny
wylatują 123. Pozostaje:
C={4} K={5}
Znowu decydujemy, by wziąć 4 a z K 'o jeden mniej' - czyli nic.
6. Is the number in: 4?
Yes
Piątka wypada, zostaje:
C={4} K={}

Ciekawe, że już w tym momencie, po 6-ciu pytaniach, mamy rozwiązanie ;) Nie
jest możliwe, by było nim 5,
bo już w dwóch pytaniach (4. i 6.) została ta możliwosć wyeliminowana. Na
pewno jest to 4. Można
sprawdzić - możemy tu zadać dowolne pytanie i nic ono już nie zmieni. ta
komfortowa
sytuacja wynika prawdopodobnie stąd, że jak sądzę algorytm stara się tak
odpowiadać, by
utrzymywać jak najliczniejszy zbiór liczb czystych, nawet kosztem
silniejszego ubytku w kwarantannie
- co zrobił w odpowiedzi 5 poświęcając 123 dla zachowania 4 w C.
Ale tak, czy owak, leży na łopatkach :) Gdyby w 5. odpowiedział N to
mielibyśmy w kwarantannie
{1234} i po kolejnych dwóch zapytaniach dzielących na pół zostałaby tylko
jedna z nich.
Wracając do przykładu:

Dla formalności zadajemy pytanie:
7. Is the number in: 4?
No
na samym końcu próbował jeszcze nas oszukać :) Przerzucamy więc czwórkę do
K.
C={} K={4} i nie ma alternatywy dla 4.
Your guess was 4.
Correctamundo!


Na koniec powstaje pytanie: czy wszystkie pokazane przez nas metody
sprowadzają się
do jakiejś jednej ? Na pierwszy rzut oka nie - np. w metodzie Farta-Trenera
budujemy kolejne zapytania w zależności od poprzednich wyników, w
poprzednich
metodach pierwsze zapytania (4 lub wszystkie 7 w hammingu) były 'sztywne'.
jednak wcale nie jestem pewien, że to 'dowód', raczej wręcz odwrotnie ;)
tylko trzeba by to elegancko ująć.