有五个具有五种不同颜色的房间排成一排；

每个房间里分别住着一个不同国籍的人；

每个人都在喝一种特定品牌的饮料，抽一特定品牌的烟，养一特定的宠物；

没有任意两个人在抽相同品牌的香烟，或喝相同品牌的饮料，或养相同的宠物。

　　问题：谁在养鱼作为宠物？

　　爱因斯坦给出如下线索：

英国人住在红色的房子里；

瑞典人养狗作为宠物；

丹麦人喝茶；

绿房子紧挨着白房子，在白房子的左边；

绿房子的主人喝咖啡；

抽Pall Mall牌香烟的人养鸟；

黄色房子里的人抽Dunhill牌香烟；

住在中间那个房子里的人喝牛奶；

挪威人住在第一个房子里面；

抽Blends牌香烟的人和养猫的人相邻；

养马的人和抽Dunhill牌香烟的人相邻；

抽BlueMaster牌香烟的人喝啤酒；

德国人抽Prince牌香烟；

挪威人和住在蓝房子的人相邻；

抽Blends牌香烟的人和喝矿泉水的人相邻。

          
           国家           房子           宠物           饮料           香烟
           挪威           黄色             猫         矿泉水        Dunhill
           丹麦           蓝色             马             茶         Blends
           英国           红色             鸟           牛奶       PallMall
           德国           绿色             鱼           咖啡         Prince
           瑞典           白色             狗           啤酒     BlueMaster
*/
/*
算法思路：
以房子的位置为主序，把国籍，颜色，宠物，饮料，香烟都作为该房子的一个成员，每一个成员都有可能
处在任何位置，为所有成员穷举每一个位置，再根据已知条件进行适当剪枝，找到唯一的解
*/

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

int main(void)
{
 string Title[5] = {"国籍","颜色","宠物","饮料","香烟"};
 struct {
  string nation;
  string color;
  string pet;
  string drink;
  string cigarette;
 } House[5];//房子从左到右编号

 House[0].nation = "挪威";//挪威人住在第一个房子里面
 House[1].color = "蓝色";//挪威人和住在蓝房子的人相邻,即蓝房子是第2个房子
 House[2].drink = "牛奶";// 住在中间那个房子里的人喝牛奶

 for (int e=1; e<5; e++) //表示英国人的房子序号
 for (int r=1; r<5; r++)//表示瑞典人的房子序号
 for (int d=1; d<5; d++)//表示丹麦人的房子序号
 for (int g=0; g<5; g++)//表示绿房子的序号
 for (int p=0; p<5; p++)//表示抽Pall Mall牌香烟的人的房子序号
 for (int y=0; y<5; y++)//表示黄色房子的序号
 for (int b=0; b<5; b++)//表示喝啤酒人的房子序号
 for (int h=0; h<5; h++)//表示养马的人的房子序号
 for (int cat=0; cat<5; cat++)//表示养猫的人的房子序号
 {
  int Germany = 10 - 0 - e - r - d; //表示德国人的房子序号,德国人抽Prince牌香烟；
  int Blends = 10 - p - y - b - Germany;//表示抽Blends牌香烟的人的房子序号
  int white = 10 - 1 - e - g - y; //表示白房子的序号
  int water = 10 - 2 - d - g - b; //表示喝矿泉水的人的房子序号
  int fish = 10 - r - p - h - cat;//表示养鱼的人的房子序号
  
  bool A1 = (e!=1); //英国人住在红色的房子里；根据房子和国家判断
  bool A2 = (r!=e); //瑞典人养狗作为宠物；根据国家和宠物判断
  bool A3 = (d!=e && d!=r && d!=2);//丹麦人喝茶；根据国家和饮料判断
  bool A4 = (g!=1 && g!=2 && g!=e && g!=d);//绿房子的主人喝咖啡；根据颜色和饮料判断
  bool A5 = (p!=r); //抽Pall Mall牌香烟的人养鸟；根据香烟和宠物判断
  bool A6 = (y!=e && y!=1 && y!=g && y!=p);//黄色房子里的人抽Dunhill牌香烟；根据颜色和香烟判断
  bool A7 = (b!=2 && b!=d && b!=g && b!=p && b!=y);//抽BlueMaster牌香烟的人喝啤酒；根据香烟和饮料判断
  bool A8 = (h!=r && h!=p && (h==y+1 || h==y-1));//养马的人和抽Dunhill牌香烟的人相邻,根据香烟和宠物判断
  bool A9 = (white == g + 1); //绿房子紧挨着白房子，在白房子的左边；
  bool A0 = (cat==Blends-1 || cat==Blends+1);//Blends牌香烟的人和养猫的人相邻；
  bool A11 = (water==Blends-1 || water==Blends+1);//抽Blends牌香烟的人和喝矿泉水的人相邻
  
  if (A1 && A2 && A3 && A4 && A5 && A6 && A7 && A8 && A9 && A0 && A11)
  {//把满足条件的序号填入结构数组
   House[e].nation = "英国";
   House[e].color = "红色";
   House[r].nation = "瑞典";
   House[r].pet = "狗";
   House[d].nation = "丹麦";
   House[d].drink = "茶";
   House[g].color = "绿色";
   House[g].drink = "咖啡";
   House[p].cigarette = "Pall Mall";
   House[p].pet = "鸟";
   House[y].color = "黄色";
   House[y].cigarette = "Dunhill";
   House[b].cigarette = "BlueMaster";
   House[b].drink = "啤酒";
   House[h].pet = "马";
   House[Germany].nation = "德国";
   House[Germany].cigarette = "Prince";
   House[Blends].cigarette = "Blends";
   House[white].color = "白色";
   House[water].drink = "矿泉水";
   House[cat].pet = "猫";
   House[fish].pet = "鱼"; 
   
   goto end;
  }
 }
end:
 for (int i=0; i<5; i++)
  cout << Title[i] << "\t";
 cout << endl << endl;
 
 for (int i=0; i<5; i++)
 {
  cout << House[i].nation << "\t";
  cout << House[i].color << "\t";
  cout << House[i].pet << "\t";
  cout << House[i].drink << "\t";
  cout << House[i].cigarette << "\t";
  cout << endl;
 }
 //输出到文件
 ofstream out("爱因斯坦的思考题.txt");
 for (int i=0; i<5; i++)
  out << Title[i] << "\t";
 out << endl << endl;
 
 for (int i=0; i<5; i++)
 {
  out << House[i].nation << "\t";
  out << House[i].color << "\t";
  out << House[i].pet << "\t";
  out << House[i].drink << "\t";
  out << House[i].cigarette << "\t";
  out << endl;
 }
 out.close();
 
   system("pause");
   return 0;
}

总体设计：
一。读取文件信息
    1。从文件中把所有汉语拼音及对应汉字读入内存。因为文件中的每个拼音及其所有同音字处在同一行中，故可用一个指针数组*storage[]存储文件内容，数组的每个元素指向文件中的一行。

二。读取用户数据
    2。读取用户输入的字符串，并对其进行适当的转换，判断字符串是否合法，并屏蔽非法字符得到一个只包含合法数字字符的新字符串。

三。处理用户数据，并请用户选择正确的拼音和汉字
    3。采用递归的方法，求出数字字符串对应的所有拼音组合，把所有满足条件的拼音组合添加到线性链表letterList。
    4。把匹配的拼音组合按顺序显示到屏幕，请用户选取一个组合。
    5。根据选中的拼音组合，到*storage[]中找到相应的汉字，并按顺序输出到屏幕，请用户选取一个汉字。
    6。输出用户选取的汉字，同时输出到文件。

四。重复步骤2-6，直到用户选择退出。

详细设计：
一。读取文件信息
1。从文件中把所有汉语拼音及对应汉字读入内存。因为文件中的每个拼音及其所有同音字处在同一行中，故可用一个指针数组*storage[]存储文件内容，数组的每个元素指向文件中的一行。因为工程中很多函数都要用到指针数组*storage[]，因此把它设置成全局变量。
实现函数：void ReadFile(const char fileName[]);
/*
函数声明：void ReadFile(const char fileName[]);
函数功能：从指定的文件中把所有汉语拼音及对应汉字读入一个指针数组*storage[]（全局变量），
  数组的每个元素指向文件中的一行。
输入变量： const char fileName[]，指定的文件名，其中存储了汉字库
输出变量：*storage[]，全局变量，每个元素指向一个包含某拼音组合及其对应汉字的字符串
返回值： 无 
*/

二。读取用户数据
2。读取用户输入的字符串buf，并对其进行适当的转换，判断字符串是否合法，并屏蔽非法字符得到一个只含合法数字字符的新字符串value。
转换规则：先找到结束键'1'，删除结束键之后的字符。若无结束键'1'，value[i] = '\0';并结束程序;
然后在buf中逆序查找#号，直到找到#号或遇到buf的第一个元素为止。若找到#号，则把#号之后的合法字符（数字）复制到value；
若未找到#号，则把buf的所有合法字符（数字）复制到value；若只输入结束键'1'，表示用户选择离开。
实现函数：void ReadValue(char value[]);
/*
函数声明：void ReadValue(char value[]);
函数功能：读取用户输入的字符串buf，并对其进行适当的转换。
    转换规则：先找到结束键'1'，删除结束键之后的字符。
    若无结束键'1'，value[i] = '\0';；并结束程序;
    然后在buf中逆序查找#号，直到找到#号或遇到buf的第一个元素为止。
    若找到#号，则把#号之后的合法字符（数字）复制到value；
    若未找到#号，则把buf的所有合法字符（数字）复制到value；
    若只输入结束键'1'，表示用户选择离开。
输入变量： char value[]，用来存储用户输入的合法字符的字符串
输出变量： char value[]，用来存储用户输入的合法字符的字符串
返回值： 无  
*/

三。处理用户数据，并请用户选择正确的拼音和汉字
    此部分可分成三个步骤：先分析并得到正确的拼音组合，再根据拼音组合得到正确的汉字，最后输出该汉字。
3。 获取正确的拼音组合：（若value[0] = '\0';，则跳到第6步）
实现函数：void OutPutSpell(char letters[]，const char value[]);
/*
函数声明：void OutPutSpell(char letters[]，const char value[]);
函数功能：根据整理后得到的字符串value，找出对应的所有拼音组合，创建一个线性链表letterList，
把所有满足条件的拼音组合添加到letterList。把存储在letterList中的拼音组合按顺序显示到屏幕，
请用户选取一个组合，并把用户选择的拼音存储到letters。 然后销毁线性链表。
输入变量：char letters[]，用来存储用户选择的拼音组合 
  const char value[]，用来存储用户输入的合法字符的字符串 
输出变量：char letters[]，用来存储用户选择的拼音组合
返回值： 无
*/

该函数包括四个主要功能函数：
LNode GetLetterList(const char value[]);
void ChooseSpell(LNode head, char letters[]);
void RecursionAnalyse(const char *keyboard[], const char value[], int pos, char buf[], LNode Head);
void DistroyList(LNode List);

/*
函数声明：LNode GetLetterList(const char value[]); 
函数功能：首先创建一个指针数组用来存储键盘上的数字字母组合，以该数字为下标，即
const char *keyboard[10] = {NULL, NULL,"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
创建一个空的线性链表LNode letterList。
然后调用函数RecursionAnalyse,采用递归的方法，求出数字字符串对应的所有拼音组合，并把它们添加到链表letterList。
输入变量： const char value[]，用来存储用户输入的合法字符的字符串
输出变量： 无
返回值： LNode letterList，由拼音组合所组成的链表，它的空间在程序执行过程中动态分配
*/
/*
函数声明：void ChooseSpell(LNode head, char letters[]);
函数功能：把存储在链表letterList中的拼音组合按顺序显示到屏幕，请用户选取一个组合，
  若用户输入#号存储letters[0] = '\0'；
  若用户输入*号，则继续输出后面的拼音组合，直到全部输出'；
  若用户输入了有效的选择，存储所选择的拼音组合到letters。
  若用户输入非法字符或在末页输入*号，报错并要求重新输入。
输入变量：LNode Head，线性链表letterList 的头结点
  char letters[]，用来存储用户选择的拼音组合 
输出变量：char letters[]，用来存储用户选择的拼音组合
返回值： 无
*/
/*
函数声明：void RecursionAnalyse(const char *keyboard[], const char value[], int pos, char buf[], LNode Head);    
函数功能：递归调用本函数，求出所有的拼音组合，每求出一个拼音组合便将其构造成一个字符串，
  把该字符串作为结点数据插入链表letterList。
输入变量： const char *keyboard[]，用来存储手机键盘信息的指针数组，根据输入的数字可以得到相应的字母
  const char value[]，用来存储用户输入的合法字符的字符串
  int pos， 当前所处理的value的元素的下标
  LNode Head，线性链表letterList 的头结点 
输出变量： LNode Head，线性链表letterList 的头结点 
返回值： 无
*/
/*
函数声明：void DistroyList(LNode List);
函数功能：销毁链表letterList。
输入变量：LNode *List，指向线性链表letterList的指针
输出变量：无
返回值： 无
*/

4。获取正确的汉字：（若letters[0] = '\0'，则跳到第6步）
实现函数：void OutPutCharacters(const char letters[], char characters[]);
/*
函数声明：void OutPutCharacters(const char letters[], char character[]);
函数功能：到*storage[]中找到与letters匹配的元素，将相应的汉字按顺序输出到屏幕，
  请用户选取一个汉字，
  若用户输入#号或非法字符，存储NULL到character；
  若用户输入*号，则继续输出后面的汉字，直到全部输出，然后存储NULL到character；
  若用户输入了有效的选择，存储所选择的汉字到character。
输入变量：const char letters[]，用来存储用户选择的拼音组合 
  char character[]，用来存储用户选择的汉字 
输出变量：char character[]，用来存储用户选择的汉字 
返回值： 无
*/
该函数包括三个主要功能函数：
int MatchCharacters(const char letters[], int pos);
void SaveCharacters(char charactersStorage[][3], char source[]);
void ChooseCharacters(char character[], const char charactersStorage[][3]);

/*
函数声明：int MatchCharacters(const char letters[], int pos);
函数功能：判断storage[pos]中的拼音组合是否与字符串letters相同
输入变量： const char letters[]，用来存储用户选择的拼音字符串
     int pos， 当前所处理的storage的指针元素的下标
输出变量：无
返回值： 相同则返回1，否则返回0
*/
/*
函数声明：void SaveCharacters(char charactersStorage[][3], char source[]);
函数功能：把source中的汉字存储到charactersStorage中
输入变量：char charactersStorage[][3]， 用来存储与拼音letters对应的所有汉字
    char source[], storage的一个指针元素，它的拼音部分与letters相同
输出变量： char charactersStorage[][3]， 用来存储与拼音letters对应的所有汉字
返回值：无
*/
/*
函数声明：void ChooseCharacters(char character[], const char charactersStorage[][3]);
函数功能：把存储在charactersStorage中的汉字按顺序显示到屏幕，请用户选取一个组合，
  若用户输入#号存储character[0] = '\0'；
  若用户输入*号，则继续输出后面的汉字，直到全部输出'；
  若用户输入了有效的选择，存储所选择的汉字到character。
  若用户输入非法字符或在末页输入*号，报错并要求重新输入。
输入变量：char character[]，用来存储用户选择的汉字 
  const char charactersStorage[][3]，用来存储所有同音字 
输出变量：char character[]，用来存储用户选择的汉字 
返回值： 无
*/

5。显示用户选取的汉字到屏幕，同时按照追加的方式输出到指定文件 。
实现函数：void PrintCharacter(const char character[], const char fileName[]);
/*
函数声明：void PrintCharacter(const char character[], const char fileName[]);
函数功能：显示用户选取的汉字到屏幕，同时按照追加的方式输出到指定文件 。
输入变量：const char character[]，用来存储用户选择的汉字
  const char fileName[]，指定的文件名，用来追加存储用户选择的汉字
输出变量：char character[]，用来存储用户选择的汉字 
返回值： 无
*/

6。重复步骤2-5，直到用户选择退出。

注意：这里只列出了一些主要函数，其他功能函数由程序员自行设计。要求每个函数均要做好单体测试后再加入工程中。

我所理解的快速排序算法
      快速排序是在实践中最快的已知排序算法，它的平均运行时间是O（NlogN）。该算法之所以特别快，主要是由于非常精练和高度优化的内部循环。在队列中寻找合适的枢点元素，并按枢点元素划分序列，是快速排序算法的关键。
      为简单起见，我这里数组的第一个元素作为枢点元素，重新排列数组，使得枢点元素之前的元素都小于枢点元素，而枢点元素之后的元素都大于或等于枢点元素。
      在这里我提供算法的两种实现：
第一种：
template <class T>
int Parttion(T a[], int low, int high)
{
      T x = a[low];

      while (low < high)
      {
            while (low < high && a[high] >=  x)
                  high--;
            a[low] = a[high];

            while (low < high && a[low] <  x)
                  low++;
            a[high] = a[low];
      }

      a[low] = x;
      return low;
}
第二种：
template <class T>
int Parttion(T a[], int low, int high)
{
      T x = a[low];
      int i = low;
     
      for (int j=low+1; j<=high; j++)
      {
            if (a[j] <= x)
            {
                  i++;
                  if (i != j)
                        Swap(a[i], a[j]);
            }
      }
     
      Swap(a[low], a[i]);
      return i;
}

template <class T>
void Swap(T & a, T & b)
{
      T t = a;
      a = b;
      b = t;
}

快速排序的驱动程序：
template <class T>
void QuickSort(T a[], int len)
{
      Qsort(a, 0, len-1);
}

template <class T>
void Qsort(T a[], int low, int high)
{
      if (low < high)
      {
            int k = Parttion(a, low, high);
            Qsort(a, low, k-1);
            Qsort(a, k+1, high);
      }
}

我所理解的堆排序算法
      堆排序在最坏的情况下，其时间复杂度也能达到O（nlogn）。相对于快速排序来说，这是它最大的优点，此外，堆排序仅需要一个记录大小供交换用的辅助存储空间。
      堆排序的数据结构是二叉堆，二叉堆的特点有两个，一个是它是一棵完全二叉树，另一个是它的根结点小于孩子结点，所以我们很容易找到它的最小结点----根结点；当然如果你想找到最大结点的话，那就要扫描所有的叶子结点，这是很费时间的，如果你想找的是最大结点的话，你最好把它弄成一个大顶堆，即一棵根结点大于孩子结点的完全二叉树。
      二叉堆通常用数组来实现，它舍弃下标0，从下标1开始置数，则很容易满足，对于数组中任意位置i上的元素，其左儿子的位置在2i上，右儿子的位置在2i+1上，双亲的位置则在i/2上。
      堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间，然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根，把它作为排序后的数组的第一个元素,然后使二叉堆的长度减1，并通过上移使得新得到的序列仍为二叉堆，再提取新二叉堆的第一个元素到新数组。依此类推，直到提取最后一个元素，新得到的数组就是排序后的数组。
算法如下：
template <class T>
void Insert(T a[], int len, T x)//把x插入到原长度为len的二叉堆，注意保证新二叉堆不越界
{
      int i;
      for (i=len; i/2>0 && a[i/2]>x; i/=2)
            a[i] = a[i/2];
      a[i] = x;
}

template <class T>
T DeleteMin(T a[], int len)//删除二叉堆的根，并通过上移使得新得到的序列仍为二叉堆
{
      if (len == 0)
            exit(1);
      T min = a[1];//二叉堆的根
      T last = a[len--];//二叉堆的最后一个元素

      int c;
      int i;
      for (i=1; i*2<=len; i=c)//把二叉堆的某些元素往前移，使得新得到的序列仍为二叉堆
      {
            c = i * 2;//i的左儿子
            if (c != len && a[c+1] < a[c])//若i有右儿子，且右儿子小于左儿子，c指向右儿子
                  c++;

            if (last > a[c])//若i的小儿子小于二叉堆的最后一个元素，把其移到i的位置
                  a[i] = a[c];
            else
                  break;
      }
      a[i] = last; //把二叉堆的最后一个元素放到适当的空位，此时得到的序列仍为二叉堆

      return min;
}

template <class T>
void HeapSort(T a[], int len)
{
      T *ca = new T[len+1]; //复制原数组到二叉堆
      ca[0] = 0;
      for (int i=0; i<len; i++) //把元素依次插入到二叉堆
            Insert(ca, i+1, a[i]);

      for (int i=0; i<len; i++)//依次提取二叉堆的根作为排序后的数组的元素
      {
            a[i] = DeleteMin(ca, len-i);
      }

      a[len-1] = ca[1]; //注意不能忘了最后一个元素

      delete []ca;
}
      在《数据结构习题与解析》（李春葆 编著 清华大学出版社）中看到一个类似的算法，它是把原数组构建成一个大顶堆，然后把大顶堆的第一个元素与最后一个元素交换；再把前n-1个元素重新构造成一个大顶堆，把新大顶堆的第一个元素与最后一个元素交换；依此类推，直到新大顶堆只有一个元素，这样就得到了一个有序的二叉堆。
算法如下：
template <class T>
void HeapSort(T a[], int len)
{
      T *ca = new T[len+1];
      ca[0] = 0;
      for (int i=0; i<len; i++)
            ca[i+1] = a[i];

      for (int i=len/2; i>0; i--) //建立初始堆
            HeapAdjust(ca, len, i);

      for (int i=len; i>1; i--)//进行len-1次循环，完成堆排序
      {
            Swap(ca[1], ca[i]); //新大顶堆的第一个元素与最后一个元素交换
            HeapAdjust(ca, i-1, 1);//筛a[1]元素，得到i-1个元素的堆
      }

      for (int i=0; i<len; i++)
            a[i] = ca[i+1];

      delete []ca;
}

template <class T>
void HeapAdjust(T a[], int len, int left) //将i与其小儿子交换位置
{
      if (len == 0)
            exit(1);

      T x = a[left];
      int i = left;
      int c = 2 * i;
      while (c <= len)
      {
            if (c < len && a[c+1] > a[c])//若i有右儿子，且右儿子大于左儿子，c指向右儿子
                  c++;
            if (last < a[c])//若i的大儿子大于二叉堆的最后一个元素，把其移到i的位置
            {
                  a[i] = a[c];
                  i = c;
                  c = 2 * i;
            }
            else
                  break;
      }
      a[i] = x; //把原二叉堆的第一个元素放到适当的空位
}

template <class T>
void Swap(T & a, T & b)
{
      T t = a;
      a = b;
      b = t;
}

      还有一种方法是每次都要重新调整大顶堆，使得父亲比儿子大，这样调整的函数较简单，
但因为每次都要遍历一半的元素，时间复杂度较大。
算法如下：
template <class T>
void HeapSort(T a[], int len)
{
      T *ca = new T[len+1];
      ca[0] = 0;
      for (int i=0; i<len; i++)
            ca[i+1] = a[i];

      for (int i=len/2; i>0; i--) //把原数组构建成一个大顶堆
            HeapAdjust(ca, len, i);
      Swap(ca[1], ca[len]); //把大顶堆的第一个元素与最后一个元素交换
     
      for (int i=len-1; i>0; i--)
      {
            for (int j=i/2; j>0; j--)//遍历长度为i的堆，得到新的大顶堆
                  HeapAdjust(ca, i, j);
            Swap(ca[1], ca[i]);
      }
     
      for (int i=0; i<len; i++)
            a[i] = ca[i+1];

      delete []ca;
}

template <class T>
void HeapAdjust(T a[], int len, int i) //将i与其小儿子交换位置
{
      int c = 2 * i;

      if (c < len)
      {
            T & max = (a[c] > a[c+1])? a[c] : a[c+1];
            if (a[i] < max)
                  Swap(a[i], max);
      }
      else
      {
            if (a[i] < a[c])
                  Swap(a[i], a[c]);
      }
}

template <class T>
void Swap(T & a, T & b)
{
      T t = a;
      a = b;
      b = t;
}

      模仿构造大顶堆的方法，我们可以调用HeapAdjust()构造一个二叉堆，并提取二叉堆的根到新数组，
然后把原二叉堆的最后一个元素放到根的位置，再调用HeapAdjust()构造一个新二叉堆，依此类推。
算法如下：
template <class T>
void HeapSort(T a[], int len)
{
      T *ca = new T[len+1];
      ca[0] = 0;
      for (int i=0; i<len; i++)
            ca[i+1] = a[i];

      for (int i=len/2; i>0; i--) //把原数组构建成一个大顶堆
            HeapAdjust(ca, len, i);
      a[0] = ca[1];
      ca[1] = ca[len]; //把二叉堆的最后一个元素放到根的位置

      for (int i=len-1; i>0; i--)
      {
            for (int j=i/2; j>0; j--)
                  HeapAdjust(ca, i, j);
            a[len-i] = ca[1];
            ca[1] = ca[i]; //把二叉堆的最后一个元素放到根的位置
      }

      delete []ca;
}

template <class T>
void HeapAdjust(T a[], int len, int i)
{
      int c = 2 * i;

      if (c < len)
      {
            T & min = (a[c] < a[c+1])? a[c] : a[c+1];
            if (a[i] > min)
                  Swap(a[i], min);
      }
      else
      {
            if (a[i] > a[c])
                  Swap(a[i], a[c]);
      }
}

template <class T>
void Swap(T & a, T & b)
{
      T t = a;
      a = b;
      b = t;
}
      后面两种方法采用的是递归，容易理解，但时间复杂度较高，因为比前两种要慢上很多，所以不可能是O（nlogn），估计是O（n^2），但具体我也不会算，请高手指教。

#ifdef _WIN32
using namespace std;
#endif

static void hanoi(int height)
{
    int fromPole, toPole, Disk;
    int *BitStr = new int[height],
        *Hold   = new int[height];
    char Place[]  = {'A', 'B', 'C'};
    int i, j, temp;

    for (i=0; i < height; i++)
    {
        BitStr[i] = 0;
        Hold[i] = 1;
    }
    temp = 3 - (height % 2);
    int TotalMoves = (1 << height) - 1;
    for (i=1; i <= TotalMoves; i++)
    {
        for (j=0 ; BitStr[j] != 0; j++)
        {
            BitStr[j] = 0;
        }
        BitStr[j] = 1;
        Disk = j+1;
        if (Disk == 1)
        {
            fromPole = Hold[0];
            toPole = 6 - fromPole - temp;
            temp = fromPole;
        }
        else
        {
            fromPole = Hold[Disk-1];
            toPole = 6 - Hold[0] - Hold[Disk-1];
        }
        cout << "Move disk " << Disk << " from " << Place[fromPole-1]
             << " to " << Place[toPole-1] << endl;
        Hold[Disk-1] = toPole;
    }
}

int main(int argc, char *argv[])
{
    cout << "Towers of Hanoi: " << endl
         << "moving a tower of n disks from pole A to pole B by using pole C" << endl;
    cout << "Input the height of the original tower: ";
    int height;
    cin >> height;
    hanoi(height);

    system("PAUSE");
    return EXIT_SUCCESS;
}
 ////////////////////////////////////////////////////////////
 我在这里根据《数学营养菜》（谈祥柏 著）提供的一种方法，编了一个程序来实现。
*/
/*
算法介绍：
首先容易证明，当盘子的个数为n时，移动的次数应等于2^n - 1。
一位美国学者发现一种出人意料的方法，只要轮流进行两步操作就可以了。
首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上。
根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
若n为奇数，按顺时针方向依次摆放 A C B。
（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；
若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。
即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘
这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。
*/
#include <iostream>
using namespace std;

const int MAX = 64; //圆盘的个数最多为64

struct st{  //用来表示每根柱子的信息
      int s[MAX]; //柱子上的圆盘存储情况
      int top; //栈顶，用来最上面的圆盘
      char name; //柱子的名字，可以是A，B，C中的一个
     
      int Top()//取栈顶元素
      {
            return s[top];
      }
      int Pop()//出栈
      {
            return s[top--];
      }
      void Push(int x)//入栈
      {
            s[++top] = x;
      }
} ;

long Pow(int x, int y); //计算x^y
void Creat(st ta[], int n); //给结构数组设置初值
void Hannuota(st ta[], long max); //移动汉诺塔的主要函数

int main(void)
{
      int n;
      cin >> n; //输入圆盘的个数
     
      st ta[3]; //三根柱子的信息用结构数组存储
      Creat(ta, n); //给结构数组设置初值

      long max = Pow(2, n) - 1;//动的次数应等于2^n - 1
      Hannuota(ta, max);//移动汉诺塔的主要函数

      system("pause");
      return 0;
}

void Creat(st ta[], int n)
{
      ta[0].name = 'A';
      ta[0].top = n-1;
      for (int i=0; i<n; i++) //把所有的圆盘按从大到小的顺序放在柱子A上
            ta[0].s[i] = n - i;
           
      ta[1].top = ta[2].top = 0;//柱子B，C上开始没有没有圆盘
      for (int i=0; i<n; i++)
            ta[1].s[i] = ta[2].s[i] = 0;
           
      if (n%2 == 0) //若n为偶数，按顺时针方向依次摆放 A B C
      {
            ta[1].name = 'B';
            ta[2].name = 'C';
      }
      else  //若n为奇数，按顺时针方向依次摆放 A C B
      {
            ta[1].name = 'C';
            ta[2].name = 'B';
      }
}

long Pow(int x, int y)
{
      long sum = 1;
      for (int i=0; i<y; i++)
            sum *= x;

      return sum;
}

void Hannuota(st ta[], long max)
{
      int k = 0; //累计移动的次数
      int i = 0;
      int ch;
      while (k < max)
      {
            //按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
            ch = ta[i%3].Pop();
            ta[(i+1)%3].Push(ch);
            cout << ++k << ": " << "Move disk " << ch << " from " << ta[i%3].name << " to " << ta[(i+1)%3].name << endl;
            i++;
            //把另外两根柱子上可以移动的圆盘移动到新的柱子上
            if (k < max)
            {     //把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆盘
                  if (ta[(i+1)%3].Top() == 0 || ta[(i-1)%3].Top() > 0 && ta[(i+1)%3].Top() > ta[(i-1)%3].Top())
                  {
                        ch =  ta[(i-1)%3].Pop();
                        ta[(i+1)%3].Push(ch);
                        cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i-1)%3].name << " to " << ta[(i+1)%3].name << endl;
                  }
                  else
                  {
                        ch =  ta[(i+1)%3].Pop();
                        ta[(i-1)%3].Push(ch);
                        cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i+1)%3].name << " to " << ta[(i-1)%3].name << endl;
                  }
            }
      }
}