分治法3思维导图

分析样例可知，这两个边长存在两种情况1.能够整除2.不能够整除。所以我们在递归函数里就分两种这两种情况来做

long long dg(long long x,long long y){ if(x%y==0) return x/y; return dg(y,x%y)+x/y; }

这题比较水，稍加推理可知就是从1加到n-1，所以直接输出就行了

又是一道水题，模拟一下就可以发现与单色汉诺塔并没有区别，把输出方法改一下就行了

核心代码

在经过思考后，可以发现当前节点a[i]只会有两种可能性，一种是自己独自占一个集合，另一种是凑进已有的盒子中，但这里要注意一个点，就是当前已经有k个盒子，所以结果还要乘k。然后再来考虑边界：当节点数=盒子数或盒子只剩下一个时，这只会存在一种可能性；当盒子或节点数为0或当节点数小于盒子数时（因为不能存在盒子数），结果为0

long long dg(int n,int k){ if(n==k||k==1) return 1; if(k==0||n==0||n<k) return 0; return dg(n-1,k-1)+dg(n-1,k)*k; }

在经过分析样例后，可以得知每一个大部分都由五个小部分组成，找出每个小部分的起始点就可以递归分别便利，当分解到最小的部分，也就是为1时，直接赋值

#include<bits/stdc++.h> using namespace std; char a[730][730]; void dg(int n,int x,int y){ if(n==1){ a[x][y]='X'; return ; } int l=pow(3,n-2); dg(n-1,x,y); dg(n-1,x+2*l,y); dg(n-1,x+2*l,y+2*l); dg(n-1,x+l,y+l); dg(n-1,x,y+2*l); } int main(){ int x; while(1){ cin>>x; if(x==-1) break; dg(x,1,1); for(int i=1;i<=pow(3,x-1);i++){ for(int j=1;j<=pow(3,x-1);j++){ if(a[i][j]!='X') cout<<' '; else cout<<a[i][j]; } cout<<endl; } cout<<'_'<<endl; } return 0; }