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

[Radarek]

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

Dlaczego nie?(IMG:http://forum.php.pl/style_emoticons/default/smile.gif) 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... (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)