🚀 go-pugleaf

On Mon, 19 Jan 1998, Adam Borowski wrote:

> n - ilosc bramek
> m - ilosc bitow liczby
>  albo na odwrot

Czy mnie RAM nie myli czy tam ilosc bitow nie odpowiadala ilosci bramek ?
;) Anyway, algorytm w ksiazce nie byl wykladniczy tylko liniowy (to po
prustu kwestia podejscia) ... i zlozonosc byla okolo
iloscbramek*ilosckombinacji. Poniewaz zliczanie kombinacji po wstepnych
obliczeniach sprowadzalo sie tak naprawde do
log(iloscbramek)*ilosckombinacji. Dla pesymistycznych danych wynosilo to 
7 (log(100)) * 100 000 = 700.000 czyli ponizej 0.1 sekundy na pentium
a optymalny to bylo
iloscbramek*(Iloscbitow ktore trzeba sprawdzic), co w pesymistycznej
sytuacji dawalo
100 * 100 = 10.000 , czyli ponizej 0.01 sekundy na pentium ... 

Rozwiazanie optymalne polegalo na zliczaniu po calych blokach liczb,
rozwiazanie trywialne sprowadzalo sie do sprawdzenia po kolei wszystkich
kombinacji. To drugie bylo o wiele prostsze i latwiejsze do napisania
(chociaz akurat to bylo zadanie z pierwszego etapu.... wiec nieduzy
problem, choc np. mi udalo sie niedpatrzyc jednej literowki w optymalnym
;) 

A co do algorytmow to temat nadaje sie do dyskusji - ale moze by
oryginalny nadawca bardziej wyprecyzowal o co mu chodzi. Rozwiazania
specyficznych problemow niewiele dadza, proponuje zajrzec do paru ksiazek
(polecam Cormen : Wstep do Algortymow; Banachowski: Algorytmy i Struktury
Danych etc... )

--
   [ p00h ]____[ Stanisław Paśko ]____[ sp174751@students.mimuw.edu.pl ]
  /                                                                     \
 |                                                                       | 
  \_____________________________________________________________________/