几个经典分治算法-白红宇

几个经典分治算法

阅读量：5940 次

发布时间：2019-06-19

本文共 3737 字，大约阅读时间需要 12 分钟。

1.fibonacci数列：

递归：

1 int fib(int n){2     if(n<=1)    return 1;3     return fib(n-1)+fib(n-2);4 }

View Code

递推：

1 int fib[100];2 void fib(int n){3     fib[0]=1;4     fib[1]=1;5     for(int i=2;i<=n;i++)6         fib[i]=fib[i-1]+fib[i-2];7 }

View Code

2.集合的全排列：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 9 using namespace std;10 11 int list[100],n;12 13 inline void Swap(int &a,int &b);14 void Perm(int list[],int k,int m);15 16 int main(){17 //freopen("D:\\input.in","r",stdin);18 //freopen("D:\\output.out","w",stdout);19 scanf("%d",&n);20 for(int i=1;i<=n;i++) list[i]=i;21 Perm(list,1,n);22 return 0;23 }24 inline void Swap(int &a,int &b){25 int t=a;26 a=b;27 b=t;28 }29 void Perm(int list[],int k,int m){30 if(k==m){31 for(int i=1;i<=m;i++)32 cout<
             
              <<' ';33 cout<

View Code

3.整数划分问题：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 9 using namespace std;10 11 int Split(int n,int m);12 13 int main(){14 //freopen("D:\\input.in","r",stdin);15 //freopen("D:\\output.out","w",stdout);16 int n;17 scanf("%d",&n);18 printf("%d\n",Split(n,n));19 return 0;20 }21 int Split(int n,int m){22 if(n==1||m==1) return 1;23 else if(n

View Code

这里简单解释下题目和思路：参考：http://www.cnblogs.com/dolphin0520/archive/2011/04/04/2005098.html

所谓整数划分，是指把一个正整数n写成如下形式：

n=m1+m2+...+mi; （其中mi为正整数，并且1 <= mi <= n），则{m1,m2,...,mi}为n的一个划分。

如果{m1,m2,...,mi}中的最大值不超过m，即max(m1,m2,...,mi)<=m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);

例如当n=4时，他有5个划分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};

该问题是求出n的所有划分个数，即f(n, n)。下面我们考虑求f(n,m)的方法;

递归法：

根据n和m的关系，考虑以下几种情况：

(1)当n=1时，不论m的值为多少（m>0)，只有一种划分即{1};

(2)当m=1时，不论n的值为多少，只有一种划分即n个1，{1,1,1,...,1};

(3)当n=m时，根据划分中是否包含n，可以分为两种情况：

(a)划分中包含n的情况，只有一个即{n}；

(b)划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。

因此 f(n,n) =1 + f(n,n-1);

(4)当n<m时，由于划分中不可能出现负数，因此就相当于f(n,n);

(5)但n>m时，根据划分中是否包含最大值m，可以分为两种情况：

(a)划分中包含m的情况，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m，因此这情况下

为f(n-m,m)

(b)划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为f(n,m-1);

因此 f(n, m) = f(n-m, m)+f(n,m-1);

综上所述：

f(n, m)= 1; (n=1 or m=1)

f(n,m) = f(n, n); (n<m)

1+ f(n, m-1); (n=m)

f(n-m,m)+f(n,m-1); (n>m)

4.棋盘覆盖问题：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 9 using namespace std;10 11 const int N=101;12 int qp[N][N];13 int cnt;14 void dg(int c1,int r1,int c2,int r2,int size);15 16 int main(){17 //freopen("D:\\input.in","r",stdin);18 //freopen("D:\\output.out","w",stdout);19 int c2,r2,n,n2;//棋盘大小为 2^n * 2^n，特殊方块为(c2,r2);20 while(scanf("%d",&n)!=EOF){21 cnt=1;22 scanf("%d%d",&c2,&r2);23 qp[c2][r2]=0;24 n2=int(pow(2,n));25 dg(1,1,c2,r2,n2);26 for(int i=1;i<=n2;i++){27 for(int j=1;j<=n2;j++)28 printf("%4d",qp[i][j]);29 printf("\n");30 }31 printf("\n");32 }33 return 0;34 }35 void dg(int c1,int r1,int c2,int r2,int size){36 if(size==1)37 return;38 int half_size=size/2;39 int cnt2=cnt++;40 if(c2
             
              
               =r1+half_size)47 dg(c1,r1+half_size,c2,r2,half_size);48 else{49 qp[c1+half_size-1][r1+half_size]=cnt2;50 dg(c1,r1+half_size,c1+half_size-1,r1+half_size,half_size);51 }52 if(c2>=c1+half_size&&r2
               
                =c1+half_size&&r2>=r1+half_size)59 dg(c1+half_size,r1+half_size,c2,r2,half_size);60 else{61 qp[c1+half_size][r1+half_size]=cnt2;62 dg(c1+half_size,r1+half_size,c1+half_size,r1+half_size,half_size);63 }64 }