汉诺塔问题-记录

偶尔看到了汉诺塔这个问题,作为益智题从正向分析了一下,很难解. 编程解的思路倒是很清晰.简单记录一下

#include <iostream>
#include <vector>


struct Stock
{
    std::vector<int> plates;
    int id = 0;
};

Stock g_stocks[3];

void plotOneStock(const Stock& stk)
{
    printf("* ");
    for (int i = 0; i < stk.plates.size(); ++i)
    {
        printf("%d ", stk.plates[i]);
    }
}

void plotStocks()
{
    printf("=====================\n");
    plotOneStock(g_stocks[0]);
    printf("\n");
    plotOneStock(g_stocks[1]);
    printf("\n");
    plotOneStock(g_stocks[2]);
    printf("\n");
}

struct OneMove
{
    OneMove(Stock& src_stk, Stock& dest_stk)
    {
        if (dest_stk.plates.size() > 0 && src_stk.plates.back() > dest_stk.plates.back())
        {
            throw "shit";
        }
        plotStocks();
        src = src_stk.id;
        dest = dest_stk.id;
        weight = src_stk.plates.back();
        src_stk.plates.pop_back();
        dest_stk.plates.push_back(weight);
    }

    int src = -1;
    int dest = -1;
    int weight = -1;
};


void moveAtoC(Stock& stkA, Stock& stkB, Stock& stkC, int num_to_move, std::vector<OneMove>& moves)
{
    if (num_to_move == 1)
    {
        OneMove move(stkA, stkC);
        moves.push_back(move);
        return;
    }
    moveAtoC(stkA, stkC, stkB, num_to_move - 1, moves);
    OneMove move{stkA, stkC};
    moves.push_back(move);
    moveAtoC(stkB, stkA, stkC, num_to_move - 1, moves);
}

int main()
{
    const int N = 10;

    g_stocks[0].id = 0;
    g_stocks[1].id = 1;
    g_stocks[2].id = 2;
    std::vector<OneMove> moves;
    for (int i = 0; i < N; ++i)
    {
        g_stocks[0].plates.push_back(N - i);
    }
    moveAtoC(g_stocks[0], g_stocks[1], g_stocks[2], N, moves);
    std::cout << "Hello World!\n";
}