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

[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.