分治法

整数划分

所谓整数划分，是指把一个正整数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};
注意4=1+3 和 4=3+1被认为是同一个划分。

1.递归算法

根据m，n的关系可以划分为以下四种情况：

1. m=1,n=1 IntDivide(n,m)=1;
2. n<m m的最大约束不起作用 IntDivide(n,m)=IntDivide(n,n);
3. n==m IntDivide(n,m)=IntDIvide(n,m-1)+1
   当该划分中没有m时，剩余划分有IntDivide(n,m-1)种，否则划分为一个{m}
4. n>m>1 如果划分中有m，则有IntDivide(n-m,m) 如果划分中没有m，则有IntDevide(n,m-1)
   所以有IntDevide(n-m.m)+Intdevide(n,m-1)

   (a)划分中包含m的情况，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m，因此这情况下
   为IntDivide(n-m,m)
   (b)划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为IntDivide(n,m-1);

代码实现

    public static int IntDivide(int n,int m){
        if(n==1||m==1) return 1;
        if(n<m) return IntDivide(n,n);
        if(n==m) return IntDivide(n, n-1)+1;
        if(n>m&&m>=1) return IntDivide(n-m,m)+IntDivide(n,m-1);
        return 0;
    }

采取中间存储，避免重复运算

public static int IntDivide(int n,int m){
                if(result[n][m]>0) return result[n][m];
        if(n==1||m==1) return 1;
        if(n<m) {
            result[n][n]=IntDivide(n,n);
            return result[n][n];
        }
        if(n==m){
            result[n][n-1]=IntDivide(n,n-1);
            return result[n][n-1]+1;
        }
        if(n>m&&m>=1) {
            result[n-m][m]=IntDivide(n-m,m);
            result[n][m-1]=IntDivide(n,m-1);
            result[n][m]=result[n-m][m]+result[n][m-1];
            return result[n][m];
        }
        return 0;
    }

最大最小元

对于一个由N个整数组成的数组，需要比较多少次才能把最大值和最小值的数找出来
1.5N-2次

void FindMinMax(int A[],int low,int high,int &min,int &max)  
{  
     int maxL,maxR,minL,minR;  
    if(high-low<=1)  
    {  
        if(A[low]<A[high])  
        {  
            min=A[low];  
            max=A[high];  
            return ;  
        }  
        else  
        {  
               min=A[high];  
        max=A[low];  
        return ;  
        }  
              
    }  
FindMinMax(A,low,low+(high-low)/2,minL,maxL);  
FindMinMax(A,low+(high-low)/2+1,high,minR,maxR);  
  
  
if(maxL>maxR)  
max=maxL;  
else  
max=maxR;  
  
  
if(minL<minR)  
min=minL;  
else  
min=minR;  
}  

推广问题

对于一个由N个整数组成的数组，需要比较多少次才能把最大值和最小值的数找出来

int FindSecondMax(int A[],int size)  
{  
  int i=0;  
  int Max = A[0];  
  int secondMax;  
    
  for(i=1;i<size;i++)  
  {  
   if(Max <= A[i])  
   {  
    secondMax = Max;  
    Max= A[i];  
   }  
   else  
   {  
    if(secondMax <=A[i])  
    {  
     secondMax = A[i];   
    }  
   }  
  }  
  return secondMax;  
}