W dniu 2013-05-12 21:21, Vax pisze:
> W dniu 2013-05-12 19:24, bartekltg pisze:
>> W dniu 2013-05-12 17:14, Vax pisze:
>
>> No nie wiem, uwaga o przeszukiwaniu kazdej kombinacji na całej
>> tablicy kliknięć sugeruje, że nawet nie przeczytałeś dokładnie:/
>
> ten ustęp tyczył rozwiązania "kombinacje wszystkich kliknięć w tablicę"
> vs "kombinacje wszystkich kliknięć w krótszy bok". Jeżeli złożoność
> drugiego określamy jako 2^(N*M) to także nie uwzględniając złożoności
> "testu".

No to wypadałoby to dorzucić do złożoności:) Ok, da sie to poprawić

Rozpatrywanie tego algorytmu jest mało sensowne, ale skoro chcesz:
mamy 2^(m*n) prób. W każdej musimy wygenerować tablicę opisującą
stan lampek. Jeśli rzeczywiście będziemy budować ją od początku,
wykonamy O(m*n) operacji. Ale nie musimy tego robić, wystarczy, że
naniesiemy poprawki. Jeśli różnił się jeden bit, poprawka jest w 5
miejscach. Super. Jeśli przeszukujemy wszystkie kombinacje włączony/
wyłączony jak liczby naturalne, zamortyzowany koszt jest również stały.
Można użyć też kodów Graya, wtedy następna kombinacja na pewno będzie
się różniła tylko o jeden bit (a wygenerowanie graya z kolejnych liczb
to jeden shift i jeden xor:)).

Rzeczywiście da się więc zrobić każdą iterację z 2^(m*n) testów
w czasie stałym. Tylko po co;)

pzdr
bartekltg