迷宫的创建问题.cpp

八皇后问题的最好解法,利用回朔法的典型例子,还有其他几个好程序

#include <iostream>

#include <vector>

using namespace std;

class Needle

{

public:

    Needle() { a.push_back(100); }//每一个柱子都有一个底座

    void push(int n) { a.push_back(n); }

    int top() { return a.back(); }

    int pop() { int n = a.back(); a.pop_back(); return n; }

    int movenum(int n) { int i = 1;while (a[i] > n) i++; return a.size() - i; }

    int size() { return a.size(); }

    int operator [] (int n) { return a[n]; }

private:

    vector<int> a;

};

void  Hanoi(int n)

{

    Needle needle[3], ns;//3个柱子，ns是转换柱子时的保存栈，借用了Needle的栈结构

    int source = 0, target, target_m = 2, disk, m = n; 

    for (int i = n; i > 0; i--) needle[0].push(i);//在A柱上放n个盘子

    while (n)//问题规模为n，开始搬动

    {

       if (!m) { source = ns.pop(); target_m = ns.pop();

m = needle[source].movenum(ns.pop()); }//障碍盘子搬走后，回到原来的当前柱

       if (m % 2) target = target_m; else target = 3 - source - target_m;//规律1的实现

       if (needle[source].top() < needle[target].top())//当前柱顶端盘子可以搬动时，移动盘子

       {

           disk = needle[source].top();m--;

           cout << disk << " move " << (char)(source + 0x41) << " to "<< (char)(target + 0x41) << endl;//显示搬动过程

           needle[target].push(needle[source].pop());//在目标柱上面放盘子

           if (disk == n) { source = 1 - source; target_m = 2; m = --n; }

       }

       else//规律2的实现

       {

           ns.push(needle[source][needle[source].size() - m]);

ns.push(target_m); ns.push(source);

           m = needle[target].movenum(needle[source].top());

           target_m = 3 - source - target; source = target;

       }

    }

    

}