汉诺塔

分治法

#include<bits/stdc++.h>
using namespace std;
int sum = 0, m;
void hanoi(char x,char y,char z,int n){           //三个柱子x、y、z
  if(n==1) {                                     //最小问题
    sum++;
    if (sum == m)  cout<<"#"<<n<<": "<<x<<"->"<<z<<endl;
  }
  else {                                          //分治
    hanoi(x,z,y,n-1);                             //(1)先把x的n-1个小盘移到y，然后把第n个大盘移到z：y和z位置互换
    sum++;
    f (sum == m)  cout<<"#"<<n<<": "<<x<<"->"<<z<<endl;
    hanoi(y,x,z,n-1);                            //(2)把y的n-1个小盘移到z：x和y位置互换
  }
}
int main(){
  int n; cin>>n>>m;
  hanoi('A','B','C',n);
  cout<<sum<<endl;
  return 0;
}

笔记：汉诺塔的解题思路就是先将A柱上的n-1个圆盘放到B柱上，A柱最底下的圆盘放到C柱上，再将B柱上的n-1个圆盘放到A柱上，将B柱下的最后一块圆盘放到C柱上去，然后循环往复