Wieże Hanoi, Klasa, PHP 5 Opcje

[dr_bonzo]

Co to robi? Rozwiazuje "Wieze Hanoi", uzywa minimalnej liczby ruchow i pokazuje je kolejno.

PHP5 REQUIRED

[PHP] pobierz, plaintext 
<pre><?php
class HanoiStack
{
    private $arrStack = array();
    
    public function HanoiStack()
    {
    }
    
    public function pushItem( $intItem )
    {
        $intItem = intval( $intItem );
        
        if ( count( $this->arrStack ) === 0 )
        {
            array_push( $this->arrStack, $intItem );
        }
        else
        {
            if ( $intItem > $this->getLastItem() )
            {
                throw new Exception( 'Cannot put bigger brick on smaller (' . $intItem . ' on ' . $this->getLastItem() . ')' );
            }
            
            array_push( $this->arrStack, $intItem );
        }
    }
    
    public function popItem()
    {
        if ( count( $this->arrStack ) === 0 )
        {
            print_r( $this->arrStack );
            throw new Exception( 'Cannot pop intem from empty stack' );
        }
        
        return array_pop( $this->arrStack );
    }
    
    public function getLastItem()
    {
        if ( count( $this->arrStack ) === 0 )
        {
            return -1;
        }
        
        return $this->arrStack[ count( $this->arrStack ) - 1 ];
    }
    
    public function __toString()
    {
        $s = '[ ';
        
        foreach ( $this->arrStack as $v )
        {
            $s .= $v . ' ';
        }
        
        $s .= &#092;"]n\";
        return $s;
    }
}
 
class Hanoi
{
    private $arrStacks = array();
    
    private $intN;
    
    private $intMoves;
    
    public function Hanoi( $intN )
    {
        $this->intN = intval( $intN );
        
        for ( $i = 0; $i < 3; $i++ )
        {
            $this->arrStacks[ $i ] = new HanoiStack();
        }
        
        for ( $i = $this->intN - 1; $i >= 0; $i-- )
        {
            $this->arrStacks[ 0 ]->pushItem( $i ); 
        }
    }
    
    public function solve()
    {
        $this->printTowers();
        
        // z wiezy 0 na wieze 2
        if ( $this->intN <= 0 )
        {
            throw new Exception( 'Wrong intN' );
        }
        
        $i_max = intval( pow( 2, $this->intN ) - 1 );
        
        $intBrickOnePosition = 0;
        $intMoveDirection = ( $this->intN % 2 === 1 ) ? -1 : 1;
        
        for ( $i = 0; $i < $i_max; $i++ )
        {
            if ( $i % 2 === 0 )
            {
                // zdejmij jedynke (tu zero: indeksujemy klocki od zera)
                $intItem = $this->arrStacks[ $intBrickOnePosition ]->popItem();
                print( '(' . $intBrickOnePosition . ')--[ ' . $intItem . ' ]-->(' . ( $intBrickOnePosition + $intMoveDirection + 3 ) % 3 . ')' . &#092;"n\" );
                $intBrickOnePosition = ( $intBrickOnePosition + $intMoveDirection + 3 ) % 3;
                // i przenies ja w keirunku $intMoveDirection
                $this->arrStacks[ $intBrickOnePosition ]->pushItem( $intItem );
            }
            else
            {
                $arrTowerIndices = array();
                $arrTopItems = array();
                $x = 0;
                
                
                // znajdz wieze z min i max brickiem !== 1
                for ( $j = 0; $j < 3; $j++ )
                {
                    if ( $j !== $intBrickOnePosition )
                    {
                        $arrTowerIndices[ $x ] = $j;
                        $arrTopItems[ $x ] = $this->arrStacks[ $j ]->getLastItem();
                        $x++;
                    }
                }
                
                $intTowerWithSmallerTopItem = ( $arrTopItems[ 0 ] < $arrTopItems[ 1 ] ) ? $arrTowerIndices[ 0 ] : $arrTowerIndices[ 1 ];
                $intTowerWithBiggerTopItem = ( $arrTopItems[ 0 ] > $arrTopItems[ 1 ] ) ? $arrTowerIndices[ 0 ] : $arrTowerIndices[ 1 ];
                
                if ( $this->arrStacks[ $intTowerWithSmallerTopItem ]->getLastItem() === -1 )
                {
                    // zamien je to ta pierwsza jest pusta
                    $temp = $intTowerWithSmallerTopItem;
                    $intTowerWithSmallerTopItem = $intTowerWithBiggerTopItem;
                    $intTowerWithBiggerTopItem = $temp;
                }
                
                // przenies klocek
                $intItem = $this->arrStacks[ $intTowerWithSmallerTopItem ]->popItem();
                print( '(' . $intTowerWithSmallerTopItem . ')--[ ' . $intItem . ' ]-->(' . $intTowerWithBiggerTopItem . ')' . &#092;"n\" );
                $this->arrStacks[ $intTowerWithBiggerTopItem ]->pushItem( $intItem );
                
                
            }
            
            $this->printTowers();
        }
    }
    
    private function printTowers()
    {
        print( '0: ' );
        print( $this->arrStacks[ 0 ] );
        print( '1: ' );
        print( $this->arrStacks[ 1 ] );
        print( '2: ' );
        print( $this->arrStacks[ 2 ] );
        print( &#092;"n\" );
    }
}
 
 
class HanoiTowers
{
    public static function main()
    {
        try
        {
            $objHanoiTower = new Hanoi( 3 );
            $objHanoiTower->solve();
        }
        catch ( Exception $e )
        {
            print( $e );
        }
    }
}
 
HanoiTowers::main();
?></pre>
[PHP] pobierz, plaintext 

Ten post edytował dr_bonzo 2.06.2005, 17:47:06

[GrayHat]

mozna jakis exampel?

[dr_bonzo]

Ehhh... a chociarz uruchomiles ten skrypt?
Wystarczy go skopiowac i uruchomic -- wyswietli ci kolejne ruchy i kolejne stany wiez.

[GrayHat]

a wogole co to wierze hanoi??

[dr_bonzo]

WieZe -- google wiedzialo ale nie powiedzialo?
http://en.wikipedia.org/wiki/Tower_of_Hanoi

[Bielo]

Sam algorytm rozwiązywania Hanoi wygląda tak:

[PHP] pobierz, plaintext 
<?php
 
function hanoi($dyskow, $z, $na)//hanoi(ilosc dyskow do przelozenia, slupek na ktorym zaczynamy, slupek na ktory pr
z
nosimy)
{
	if($dyskow==1)
	{
		print(&#092;"Przesun dysk nr \".$dyskow.\" z \".$z.\" na \".$na.\"<br />\");
	}
	else
	{
		hanoi($dyskow-1, $z,  3-$z-$na);
		print(&#092;"Przesun dysk nr \".$dyskow.\" z \".$z.\" na \".$na.\"<br />\");
		hanoi($dyskow-1, 3-$z-$na, $na);
	}
}
 
?>
[PHP] pobierz, plaintext 

Przyklad pzepisany z ksiazki Helionu "Algorytmy, struktury danych i techniki programowania", sprawdzalem pieknie dziala.

Nie przygladalem sie za bardzo Twojemu skryptowi, ale mysle ze mozna bylo zrobic to krocej

[dr_bonzo]

Twoj algorytm jest rekurencyjny, a moj nie. Oba opisane sa w wikipedii:

Alternately move disc 1 and one of the larger discs. If two of the larger discs are available, always move the smaller one onto the larger. When you move an odd-numbered disc, always move it one peg clockwise; when you move an even-numbered disc, always move it one peg counterclockwise.

An even easier way to remember this solution is to notice that the smallest disk gets every second move, and always moves in the same direction. In between smallest disk moves, there is only one legal move that does does not involve moving the smallest disk again.

----

Nie przygladalem sie za bardzo Twojemu skryptowi, ale mysle ze mozna bylo zrobic to krocej

No pewnie, w ogole porzucic klasy, obsluge bledow, skrocic printTowers(), itd.

[Bielo]

to co ja napisalem to jest tylko algorytm, a nie caly skrypt. Po dodaniu do niego obslugi bledow i przerobieniu na wersje obiektowa, bylby chyba krotszy od Twojego, ale rozumiem tez uzycie wersji nerekurencyjnej

[Radarek]

A mi nawet nie chce sie czytac i probowac zrozumiec wersje iteracyjna, bo po co? Wersja rekurencyjna jest tak intuicyjna i zrozumiala, ze nie trzeba nic wiecej. To niesamowite, ze te kilka linijek jest poprawnym rozwiazaniem [i najoptymalniejszym] podanego problemu. Ale braw nie bije bo znalem juz wczesniej to rozwiazanie

[M4chu]

Najoptymalniejszym? Dla mnie najoptymalniejsze to najszybsze, a rekurencyjne takie napewno nie jest.

[dr_bonzo]

Ale braw nie bije bo znalem juz wczesniej to rozwiazanie

Prawda jest taka ze nudzilo mi sie tamtej nocy i napisalem ten algorytm.
A wpadlem na niego (rozwiazujac na papierze dziesiatki razy WH) dawno temu.

Wersja rekurencyjna jest tak intuicyjna i zrozumiala

A sprobuj go zastosowac w praktyce w realu...

[Bakus]

@Bielo: Jeżeli masz pomysł, to go rozwiń, napisz skrypt i umieść w osobnym temacie.

[Radarek]

Najoptymalniejszym? Dla mnie najoptymalniejsze to najszybsze, a rekurencyjne takie napewno nie jest.

Dlaczego nie? Zapewniam cie ze jest. Powiedz jaki jest powod dla ktorego mialo byc nie byc?

Prawda jest taka ze nudzilo mi sie tamtej nocy i napisalem ten algorytm.
A wpadlem na niego (rozwiazujac na papierze dziesiatki razy WH) dawno temu.

Przyznam ci sie, ze ja tez kiedys wpadlem na to rozwiazanie, ale mniejsza z tym.

A sprobuj go zastosowac w praktyce w realu...

Hm.. jesli pisze program to po to zeby robil cos za mnie. Np. program sortujacy za pomoca quicksorta lub heapsorta. Sprobuj zrobic to w praktyce. Bez sensu gadanie...

[bela]

Najoptymalniejszym? Dla mnie najoptymalniejsze to najszybsze, a rekurencyjne takie napewno nie jest.

Dlaczego nie? Zapewniam cie ze jest. Powiedz jaki jest powod dla ktorego mialo byc nie byc?

Udowodnij, że jest najoptymalniejsze

[Radarek]

Najoptymalniejszym? Dla mnie najoptymalniejsze to najszybsze, a rekurencyjne takie napewno nie jest.

Dlaczego nie? Zapewniam cie ze jest. Powiedz jaki jest powod dla ktorego mialo byc nie byc?

Udowodnij, że jest najoptymalniejsze

Hm.. ilosc ruchow potrzebnych do przeniesienia N krazkow wynosci 2^(n-1) i taka jest zlozonosc programu. Szybciej sie nie da. Zakladajac, ze wersja iteracyjna wykonuje taka sama ilosc ruchow to i tak jest mniej optymalna. Czemu? Bo zawiera wiecej instrukcji . Przepiszcie obra programy na C/C++, skompilujcie do kodu assemblerowego i porownajcie rozmiary kodu. Stawiam, ze mniejszy bedzie rekurencyjny.

[dr_bonzo]

Ale wez tez pod uwage wielokrotne wywolywanie funkcji, co takze zajmuje zasoby i cpu (trzeba utworzyc zmienne lokalne, odlozyc je na stos, wywolac funkcje, zdjac zmienne z powrotem, itd). Ale nie wiem, ktora z metod bedzie szybsza.

[Radarek]

Ale wez tez pod uwage wielokrotne wywolywanie funkcji, co takze zajmuje zasoby i cpu (trzeba utworzyc zmienne lokalne, odlozyc je na stos, wywolac funkcje, zdjac zmienne z powrotem, itd). Ale nie wiem, ktora z metod bedzie szybsza.

Tak wzialem to pod uwage. Rekurencyjne wywolanie funkcji to odlozenie na stos zmiennych lokalnych funkcji oraz adresu powrotu. Nie wierzysz chyba zeby wersja rekurencyjna bedzie dluzsza?

[onlyX]

A mi wyrzuciło taki błąd w tym pierszym skrypcie:

Kod

Parse error: parse error, expecting `T_OLD_FUNCTION' or `T_FUNCTION' or `T_VAR' or `'}'' in D:\usr\test\hanoi.php on line 4

[dr_bonzo]

Bo musisz miec PHP5.

PS. Uzupelniony 1szy post o to info

[piratt]

A wzial ktos pod uwage fakt ze w wersji rekurencyjnej skonczy sie baaardzo szybko pamiec? Rekurencja nie jest zalecana przy duzej liczbie wywolan.