/*====================================================================================
  File:  hanoi2.c
  Function:
    This program displays the solution of hanoi problem in every exact step.
  Author:
    baoyibao
  Date:
    2008/3/18
  Version:
    1.0
  ==================================================================================*/
#include <iostream>
#include <iomanip>

// the number of bricks
#define TOTAL_BRICK 6

// the length of characters in a line
#define LINE_LEN 80

using namespace std;

// print a specific character num_of_char times
void print_char( char ch, int num_of_char );

// print a line of brick
void print_a_brick( int num_of_brick );

// move a brick from one place to the other
void move_a_brick( int from[], int to[] );

// print all the hanoi bricks
void print_hanoi_brick( int left_brick[], int mid_brick[], int right_brick[] );

// the algorithm -- hanoi
void hanoi( int n, int from[], int mid[], int to[] );

// declare three integer arrays storing the number of bricks
int iLeft[TOTAL_BRICK];
int iMid[TOTAL_BRICK];
int iRight[TOTAL_BRICK];

int main()
{
    // initialize the integer arrays
    for ( int idx_left = 0; idx_left < TOTAL_BRICK; idx_left++ )
        iLeft[idx_left] = TOTAL_BRICK - idx_left;
    
    for ( int idx_mid = 0; idx_mid < TOTAL_BRICK; idx_mid++ )
        iMid[idx_mid] = 0;
    
    for ( int idx_right = 0; idx_right < TOTAL_BRICK; idx_right++ )
        iRight[idx_right] = 0;
    
    // print program message
    print_char( '=', LINE_LEN );
    cout << "\nFunction:" << endl;
    cout << "\tThis program displays the solution of hanoi problem in every exact step.";
    cout << "Author:\n\tbaoyibao" << endl;
    cout << "Date:\n\t2008/3/18" << endl;
    cout << "Version:\n\t1.0" << endl;
    print_char( '=', LINE_LEN );

    cout << "\n\nPress enter each time to see the next step..." << endl;
    
    // print the hanoi bricks before any moving step and wait for user input to continue
    print_hanoi_brick( iLeft, iMid, iRight );
    cin.get();

    // move the bricks and print the hanoi bricks for each moving step
    hanoi( TOTAL_BRICK, iLeft, iMid, iRight );
    
    return 0;
}


void print_char( char ch, int num_of_char )
{
    for ( int i = 0; i < num_of_char; i++ )
        cout << ch;
}

void move_a_brick( int from[], int to[] )
{
    int from_len = TOTAL_BRICK;
    int to_len = TOTAL_BRICK;
    int idx_from = 0;
    int idx_to = 0;

    // find the index of being moved element in "from"
    while ( from[idx_from] )
        idx_from++;

    // find the index of being store element in "to"
    while ( to[idx_to] )
        idx_to++;

    to[idx_to] = from[idx_from - 1];
    from[idx_from - 1] = 0;
}

void print_a_brick(int num_of_brick )
{
    int num_of_space = TOTAL_BRICK - num_of_brick;

    print_char( ' ', num_of_space );
    print_char( '=', num_of_brick );
    print_char( '|', 1 );
    print_char( '=', num_of_brick );
    print_char( ' ', num_of_space );
}

void print_hanoi_brick( int left_brick[], int mid_brick[], int right_brick[] )
{
    // the count of the moving steps
    static int cnt = 0;
    
    cout << "step " << cnt << ": \n";
    cnt++;
    
    for (int i = TOTAL_BRICK - 1; i >= 0; i-- )
    {
        print_a_brick( left_brick[i] );
        print_a_brick( mid_brick[i] );
        print_a_brick( right_brick[i] );
        cout << endl;
    }
    print_char( '-', LINE_LEN );
    cout << endl;
}

void hanoi( int n, int one[], int two[], int three[] )
{
    if ( n == 1 )
    {
        move_a_brick( one, three );
        print_hanoi_brick( iLeft, iMid, iRight );
        cin.get();
    }
    else
    {
        hanoi( n - 1, one, three, two );
        move_a_brick( one, three );
        print_hanoi_brick( iLeft, iMid, iRight );
        cin.get();
        hanoi( n - 1, two, one, three );
    }
}
以下是原先用vector<int>(而不是int[])实现的代码：
-------------------------------------------------------------------------------------------------------------------------------------------
#include <iostream>
#include <vector>

#define NUM_OF_BRICK 2

using namespace std;

void print_char( char ch, int num_of_char );
void print_a_brick( int num_of_brick, int total_brick );
void move_a_brick( vector<int> from, vector<int> to );
void print_hanoi_brick( vector<int> left_brick, vector<int> mid_brick, vector<int> right_brick );
void hanoi( int n, vector<int> from, vector<int> mid, vector<int> to );

vector<int> vLeft;
vector<int> vMid;
vector<int> vRight;

int main()
{
    
    for ( int idx_left = NUM_OF_BRICK; idx_left > 0; idx_left-- )
        vLeft.push_back( idx_left );

    for ( vector<int>::iterator it = vLeft.begin(); it < vLeft.end(); it++ )
        cout << *it << endl;
    
    for ( int idx_mid = NUM_OF_BRICK; idx_mid > 0; idx_mid-- )
        vMid.push_back( 0 );
    
    for ( int idx_right = NUM_OF_BRICK; idx_right > 0; idx_right-- )
        vRight.push_back( 0 );

    print_hanoi_brick( vLeft, vMid, vRight );

    hanoi( NUM_OF_BRICK, vLeft, vMid, vRight );
    
    return 0;
}

void print_char( char ch, int num_of_char )
{
    for ( int i = 0; i < num_of_char; i++ )
        cout << ch;
}

void move_a_brick( vector<int> from, vector<int> to )
{
    vector<int>::iterator iter_from = from.begin();
    vector<int>::iterator iter_to = to.begin();

    while ( (*iter_from != 0) && (iter_from < from.end()) )
        iter_from++;

    while ( (*iter_to != 0) && (iter_to < to.end()) )
        iter_to++;

    to.insert( iter_to, *(iter_from - 1) );
    to.pop_back();

    from.erase( iter_from - 1 );
    from.push_back(0);
}

void print_a_brick(int num_of_brick, int total_brick )
{
    int num_of_space = total_brick - num_of_brick;

    print_char( ' ', num_of_space );
    print_char( '=', num_of_brick );
    print_char( '|', 1 );
    print_char( '=', num_of_brick );
    print_char( ' ', num_of_space );
}

void print_hanoi_brick( vector<int> left_brick, vector<int> mid_brick, vector<int> right_brick )
{
    int total_brick = left_brick.size();
    int num_of_left = left_brick.size();
    int num_of_mid = mid_brick.size();
    int num_of_right = right_brick.size();
    static int cnt = 0;

    cout << "Step: " << cnt++ << endl;
    
    for (int i = total_brick - 1; i >= 0; i-- )
    {
        print_a_brick( left_brick.at(i), total_brick );
        print_a_brick( mid_brick.at(i), total_brick );
        print_a_brick( right_brick.at(i), total_brick );
        cout << endl;
    }
    print_char( '-', 30 );
    cout << endl;
}

void hanoi( int n, vector<int> one, vector<int> two, vector<int> three )
{
    if ( n == 1 )
    {
        move_a_brick( one, three );
        print_hanoi_brick( vLeft, vMid, vRight );
    }
    else
    {
        hanoi( n - 1, one, three, two );
        move_a_brick( one, three );
        print_hanoi_brick( vLeft, vMid, vRight );
        hanoi( n - 1, two, one, three );
    }
}--

[[it] 本帖最后由 baoyibao 于 2008-3-19 12:14 编辑 [/it]]

汉诺塔用递归很简单很简单,但我就不知道啥意识

写lz得代码很烦心得..我不太喜欢那种_加_的代码..虽然很强大.但是肯了会不舒服..帮你顶了...

那天有人发了个用递归的，我看了两个小时，终于把递归的执行过程搞懂了呵呵