Tower of Hanoi

用二进制来解汉诺塔问题

隐藏在汉诺塔中的分形曲线

汉诺塔问题I

对于传统的汉诺塔游戏我们做一个拓展，我们有从大到小放置的n个圆盘，开始时所有圆盘都放在左边的柱子上，按照汉诺塔游戏的要求我们要把所有的圆盘都移到右边的柱子上，请实现一个函数打印最优移动轨迹。

给定一个int n，表示有n个圆盘。请返回一个string数组，其中的元素依次为每次移动的描述。描述格式为： move from [left/mid/right] to [left/mid/right]。测试样例：

返回：move from left to right

Solution

class Hanoi {
 public:
  vector<string> getSolution(const int n) {
    res_.clear();
    getSolution(n, "left", "mid", "right");
    return res_;
  }

 private:
  void getSolution(const int n, const string& a, const string& b,
                   const string& c) {
    if (n == 1) {
      res_.emplace_back("move from " + a + " to " + c);
    } else {
      getSolution(n - 1, a, c, b);
      res_.emplace_back("move from " + a + " to " + c);
      getSolution(n - 1, b, a, c);
    }
  }

 private:
  vector<string> res_;
};

有一个int数组arr其中只含有1、2和3，分别代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，arr[i]的值代表第i+1个圆盘的位置。比如，arr=[3,3,2,1]，代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。如果arr代表的状态是最优移动轨迹过程中出现的状态，返回arr这种状态是最优移动轨迹中的第几个状态。如果arr代表的状态不是最优移动轨迹过程中出现的状态，则返回-1。

给定一个int数组arr及数组的大小n，含义如题所述，请返回一个int，代表所求的结果。测试样例：

[3,3]

返回：3

Solution

const int mod = 1e9 + 7;
class Hanoi {
 public:
  int chkStep(const vector<int>& pos, int n) {
    vector<int> pows(n);
    int last = 1;
    for (int i = 0; i < n; ++i) {
      pows[i] = last;
      last = (last << 1) % mod;
    }
    int cnt = n - 1;
    int res = 0;
    int a = 1, b = 2, c = 3;
    while (cnt >= 0) {
      if (pos[cnt] == b) {
        return -1;
      }

      if (pos[cnt] == a) {
        // 在原始位置，说明该列不用移动
        // 前cnt-1个盘子的目的地是b
        swap(b, c);
      } else {
        // 说明该列需要移动，那么就是需要移动前cnt-1列，需要操作2^cnt-1次，然后cnt列需要移动一次
        res = (res + pows[cnt]) % mod;
        // 说明前cnt-个盘子已经在b了，所以其实位置应该变为b
        swap(a, b);
      }
      --cnt;
    }
    return res;
  }
};

汉诺塔问题I

Solution

汉诺塔II

Solution

CATALOG

FEATURED TAGS