Powiedzmy, ze mamy \(\displaystyle{ n}\) krazkow na 3 wiezach. Chcemy napisac algorytm, ktory majac dane dwa ustawienia krazkow - \(\displaystyle{ A, B}\) (obydwa spelniajace zasady umieszczania krazkow na wiezach, tzn jesli \(\displaystyle{ m< k}\) to krazek \(\displaystyle{ k}\) nie moze lezec pod krazkiem \(\displaystyle{ m}\)) przestawi krazki z ustawienia \(\displaystyle{ A}\) do ustawienia \(\displaystyle{ B}\).
Wiadomo, ze mozna to zrobic najpierw zgarniajac wszystkie krazki na jedna kupke, a pozniej je rodzielac - poczynajac od krazka \(\displaystyle{ n}\) (najwiekszego). Zlozonosc bedzie wykladnicza. Da sie to zrobic jakos bardziej pomyslowo? (wiadomo, ze ponizej \(\displaystyle{ O(2^n )}\) nie zejdziemy