Problem Solving►UVa

UVa 10017 - The Never Ending Towers of Hanoi

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

Solution

基本上就是河內塔的問題，用 std::vector<int> 記下每根柱子上的數字，河內塔的操作網路上很多，不在此贅述了。
記得處理總步數的判斷。

Code

UVa 10017
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstdio>
#include<vector>
using namespace std;

vector<int>s[3];
char c[3] = { 'A','B','C' };
int step, m;
void print()
{
    int size;

    putchar('\n');
    for (int i = 0; i < 3; i++)
    {
        printf("%c=>", c[i]);
        if (!s[i].empty())
        {
            printf("   ");
            size = s[i].size();
            for (int j = 0; j < size - 1; j++)
                printf("%d ", s[i][j]);
            printf("%d", s[i].back());
        }
        putchar('\n');
    }
}
void solve(int n, int from, int buffer, int to)
{
    if (step == m)
        return;

    if (n == 1)//move only one disc from "from" to "to"
    {
        step++;
        s[to].push_back(s[from].back());
        s[from].pop_back();
        print();
    }
    else
    {
        solve(n - 1, from, to, buffer);//move n-1 discs form "from" to "buffer"
        if (step == m)
            return;
        step++;
        //move n-th disc from "from" to "to"
        s[to].push_back(s[from].back());
        s[from].pop_back();
        print();
        solve(n - 1, buffer, from, to);//move n-1 disc form "buffer" to "to"
    }
}
int main()
{
    int n, Case = 1;
    while (scanf("%d%d", &n, &m) && n)
    {
        printf("Problem #%d\n", Case++);
        step = 0;
        for (int i = n; i; i--)
            s[0].push_back(i);

        print();
        solve(n, 0, 1, 2);

        for (int i = 0; i < 3; i++)
            s[i].clear();

        putchar('\n');
    }

    return 0;
}