递归与分治

作者：Gausst松鼠会 | 2024-06-14 04:34:24

踩

递归与分治

递归的定义：
程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。边界条件与递归方程是递归函数的两个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
看过这样一个笑话，要想理解递归，就要先理解递归。
话不多说，我们来看几个具体的例子慢慢理解它：
1.阶乘函数
一个正整数的阶乘是所有小于及等于该数的正整数的积，并且有0的阶乘为1。自然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表示法。


#include<iostream>
using namespace std;
 
int factorial(int n)
{
    if(n==0) return 1;
    else return n*factorial(n-1); 
}
 
int main()
{
    cout<<factorial(5)<<endl;
}

2.斐波那契数列
斐波那契数列，又称黄金分割数列，因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。


#include<iostream>
using namespace std;
 
int fibonacci(int n)
{
    if(n<=1) return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}
 
int main()
{
    cout<<fibonacci(5)<<endl;
    //数列从第0项开始
}

3.排列问题
设计一个递归算法生成n个元素R={r1,r2,…,rn}的全排列。从n个不同元素中任取m(m≤n)个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。比如，3个元素{1,2,3}的全排列有123,132,213,231,312,321。设Ri=R-{ri}，比如，R2={1,3}。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri得到的排列,，比如，(2)perm({1,3})={213,231}。R的全排列可归纳定义如下：
当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；
当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。
根据这样的递归定义，我们可以设计出产生全排列的递归算法。


#include<iostream>  
#include<algorithm>
using namespace std;  
  
void perm(int list[],int k,int m)  
{  
    //产生list[k:m]的所有排列   
    if(k==m)  
    {  
        for(int i=0;i<=m;i++) cout<<list[i];  
        cout<<endl;  
    }  
    else  
    {  
        for(int i=k;i<=m;i++)  
        {  
            swap(list[k],list[i]);  
            perm(list,k+1,m);  
            swap(list[k],list[i]);  
        }  
    }     
}   
  
int main()  
{  
    int array[4]={1,2,3,4};  
    perm(array,0,3);  
}

在STL中有两个方法next_permutation和prev_permutation生成全排列：


#include<algorithm>
#include<iostream>
using namespace std;
 
int main()
{
    int a[]={3,2,1};
    do
    {
        cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    }while(prev_permutation(a,a+3));
}
#include<algorithm>
#include<iostream>
using namespace std;
 
int main()
{
    int a[]={1,2,3};
    do
    {
        cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    }while(next_permutation(a,a+3));
}

next和prev是按照字典序来的，所以使用next_permutation时数组的初始状态是1,2,3字典序最小，使用prev_permutation时数组的初始状态是3,2,1字典序最大。否则的话无法得到全部的排列。它们的原理是怎样的呢，我们看一个具体例子，一个排列为124653，如何找到它的下一个排列。因为下一个排列一定与124653有尽可能长的前缀，所以，脑洞大开一下，从后面往前看这个序列，如果后面的若干个数字有下一个排列，问题就得到了解决。
第一步：找最后面1个数字的下一个全排列。
显然最后1个数字3不具有下一个全排列。
第二步：找最后面2个数字的下一个全排列。
显然最后2个数字53不具有下一个全排列。
第三步：找最后面3个数字的下一个全排列。
显然最后3个数字653不具有下一个全排列。
到这里相信大家已经看出来，如果一个序列是递减的，那么它不具有下一个排列。
第四步：找最后面4个数字的下一个全排列。
1我们发现显然最后4个数字4653具有下一个全排列。因为它不是递减的，例如6453，5643这些排列都在4653的后面。
现在，我们开始考虑如何找到4653的下个排列。4肯定要和653这3个数字中大于4的数字中的最小的那个进行交换，这里就是4和5交换。因为我们知道4后面的元素是递减的，所以在653中从后面往前查找，找到第一个大于4的数字就是需要和4进行交换的数字。这里我们找到了5，交换之后得到的临时序列为5643，交换后得到的643也是一个递减序列。所以得到的4653的下一个临时序列为5643，但是既然前面数字变大了，后面的自然要变为升序才行，变换5643得到5346。所以124653的下一个序列为125346。
总结一下就是：在当前序列中，从尾端往前寻找两个相邻元素，前一个记为*i，后一个记为*ii，并且满足*i < *ii。然后再从尾端寻找另一个元素*j，如果满足*i < *j，即将第i个元素与第j个元素对调，并将第ii个元素之后（包括ii）的所有元素颠倒排序，即求出下一个序列了。
进一步考虑，如果有重复的元素呢？STL的这两个方法能够处理，而我们的算法就出现问题了。这个时候我们需要一个记录结果的辅助数组，通过确定两个数组中元素出现的次数来确定能不能加入这个元素。if(p[i]!=p[i-1])这句话是为了保证我们枚举的元素不重复。同样，我们默认数组是升序的。


#include<iostream>
using namespace std;
int a[4];
 
void print_permutation(int n,int *p,int *a,int cur)
{
    int i,j;
    if(cur==n)
    {
        for(i=0;i<n;i++) cout<<a[i]<<" ";
        cout<<endl;
    }
    //走到递归的边界 
    else
    {
        for(i=0;i<n;i++)
        { 
            if(p[i]!=p[i-1])
            {
                //枚举的p[i]应该不重不漏 
                int c1=0,c2=0;
                for(j=0;j<cur;j++) if(a[j]==p[i]) c1++;
                //统计A[0]到A[cur-1]中p[i]的出现次数c1 
                for(j=0;j<n;j++) if(p[i]==p[j]) c2++;
                //统计P[0]到P[n-1]中P[i]出现的次数c2 
                if(c1<c2)
                {
                    a[cur]=p[i];
                    print_permutation(n,p,a,cur+1);
                }
            }  
        }
    }
}
 
int main()
{
    int n=4;
    int p[4]={1,1,2,3};   
    print_permutation(n,p,a,0);
    return 0;
}

4.整数划分
正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。整数划分问题便是求正整数n的不同划分个数。
例如正整数6有如下11种不同的划分：
6；
5+1；
4+2，4+1+1；
3+3，3+2+1，3+1+1+1；
2+2+2，2+2+1+1，2+1+1+1+1；
1+1+1+1+1+1。
前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分的数目，则难以找到递归关系。因此考虑增加一个自变量：将n的划分中最大加数不大于m的划分个数记作q(n,m)。
(1)q(n,m)=1,n=1或m=1
(2)q(n,m)=q(n,n), n<m
(3)q(n,n)=1+q(n,n-1),n=m
(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1


#include<iostream>
using namespace std;
 
int q(int n,int m)
{
    if((n<1)||(m<1)) return 0;
    if((n==1)||(m==1)) return 1;
    if(n<m) return q(n,n);
    if(n==m) return 1+q(n,n-1);
    return q(n,m-1)+q(n-m,m);
}
 
int main()
{
    cout<<q(6,6)<<endl;
}

5.汉诺塔
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。
当n>1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。
由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。


#include<iostream>
using namespace std;
int i=1;//记录步数
  
void move(int n,char from,char to) 
//将编号为n的盘子从from移到to  
{
    cout<<"第"<<i<<"步：将"<<n<<"号盘子从"<<from<<"移到"<<to<<endl; 
    i++;
}  
 
void hanoi(int n,char a,char b,char c)
//把n个盘子从a借助b移到c  
{  
    if(n==1) move(1,a,c);
    else  
    {  
      hanoi(n-1,a,c,b);  
      move(n,a,c);              
      hanoi(n-1,b,a,c);
    }  
}  
 
int main()  
{    
     int n;  
     cin>>n;
     char x='A',y='B',z='C';    
     hanoi(n,x,y,z);  
}

总结一下递归：
优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多，容易导致栈的溢出。
在讲解什么是栈的溢出之前，我们需要了解C程序在内存中的组织方式：
BSS段：通常是指用来存放程序中未初始化的全局变量的一块内存区域。BSS是英文Block Started by Symbol的简称。BSS段属于静态内存分配。
数据段：数据段通常是指用来存放程序中已初始化的全局变量的一块内存区域。数据段属于静态内存分配。
代码段：代码段通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读 , 某些架构也允许代码段为可写，即允许修改程序。在代码段中，也有可能包含一些只读的常数变量，例如字符串常量等。程序段为程序代码在内存中的映射。一个程序可以在内存中多有个副本。
堆：堆是用于存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减。当进程调用malloc/free等函数分配内存时，新分配的内存就被动态添加到堆上(堆被扩张)/释放的内存从堆中被剔除。
栈：栈又称堆栈，存放程序的局部变量(但不包括static声明的变量，static 意味着在数据段中存放变量)。除此以外，在函数被调用时，栈用来传递参数和返回值。由于栈的后进先出特点，所以栈特别方便用来保存/恢复调用现场。从这个意义上讲，我们可以把堆栈看成一个寄存交换临时数据的内存区。
堆的增长方向为从低地址到高地址向上增长，而栈的增长方向刚好相反(实际情况与CPU的体系结构有关)。当C程序中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息，每一个调用都被当作是活跃的。栈上的那块存储空间称为活跃记录或者栈帧。栈帧由5个区域组成：输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数，参见下图：

栈维护了每个函数调用的信息直到函数返回后才释放，这需要占用相当大的空间，尤其是在程序中使用了许多的递归调用的情况下。所以递归容易导致栈的溢出。幸运的是我们可以采用一种称为尾递归的特殊递归方式来避免前面提到的这些缺点。如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。还是以阶乘为例：


#include<iostream>
using namespace std;
 
int factorial(int n, int a)
{
    if(n<0) return 0;
    else if(n==0) return 1;
    else if (n==1) return a;
    else return factorial(n-1,n*a);
}
int main()
{
    cout<<factorial(5,1)<<endl;
}

关于递归就简单说到这里。下面我们谈谈分治。分治算法的设计中很多时候用到了递归的技巧。
分治的定义：
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。
话不多说，我们来看几个具体的例子慢慢理解它：
1.二分搜索
相信这个问题大家应该很熟悉了，就不多说了。我给出它的递归算法和非递归算法。关于二分查找更深入的讨论，请看我的这篇文章：你真的会二分查找吗？


#include<iostream>
using namespace std;
 
int BinarySearch(Type a[],const int& x,int l,int r)
{
    while(r>=l)
    { 
        int m=(l+r)/2;
        if(x==a[m]) return m;
        else if(x<a[m]) r=m-1; 
        else l=m+1;
    }
    return -1;
}    
 
int main()
{
    int array[10]={10,20,30,40,50,60,70,80,90,100};
    cout<<BinarySearch(array,30,0,9)<<endl;
}
#include<iostream>    
using namespace std;    
    
int BinarySearch(int a[],const int &x,int l,int r)    
{  
    if(l<=r)   
    {  
        int m=(l+r)/2;  
        if(a[m]==x) return m;             
        else if(a[m]>x) return BinarySearch(a,x,l,m-1);     
        else return BinarySearch(a,x,m+1,r);   
    }  
    else return -1;  
}        
    
int main()    
{    
    int array[10]={10,20,30,40,50,60,70,80,90,100};    
    cout<<BinarySearch(array,90,0,9)<<endl;   
}

2.Strassen矩阵乘法
Volker Strassen是一位出生于1936年的德国数学家。他因为在概率论上的工作而广为人知，但是在计算机科学和算法领域，他却因为矩阵相乘算法而被大部分人认识，这个算法目前仍然是比通用矩阵相乘算法性能好的主要算法之一。Strassen在1969年第一次发表关于这个算法的文章，并证明了复杂度为n^3的算法并不是最优算法。实际上Strassen给出的解决方案只是更好一点点，但是，他的贡献却是巨大的，因为他的工作触发了矩阵相乘领域更多的研究，比如复杂度为O(n^2,3737)的Coppersmith-Winograd算法。一个矩阵可以被分成几个小的矩阵，很容易想到分治的解法(我们假设矩阵的阶数是2的n次方)。

技术分享

这样并没有降低问题的复杂度。为了得到更快的解决方案，我们不得不看一下Strassen在1969年做过的工作。

技术分享

随着n的变大，Strassen算法是如何比通用矩阵相乘算法变得更有效率的。

Strassen算法并不比n^3复杂度的通用矩阵相乘算法快很多。对于一个很小的n(通常n<45)来说，通用矩阵相乘算法在实践中往往是更好的选择。


#include<iostream>
using namespace std;
const int N=4; 
//常量N用来定义矩阵的大小
void STRASSEN(int n,float A[][N],float B[][N],float C[][N]);
void input(int n,float p[][N]);
void output(int n,float C[][N]);
 
int main()
{                    
    float A[N][N],B[N][N],C[N][N];  
    input(N,A);
    input(N,B);                        
    STRASSEN(N,A,B,C);   
    output(N,C);  
}
 
void input(int n,float p[][N])  
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cin>>p[i][j];
        }
    }
}
 
void output(int n,float C[][N]) 
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cout<<C[i][j]<<"  ";
        }
        cout<<endl;
    }
}
 
void MATRIX_MULTIPLY(float A[][N],float B[][N],float C[][N])  
{
    int i,j,t;
    for(i=0;i<2;i++)
	{                  
        for(j=0;j<2;j++)
        {    
            C[i][j]=0;                
            for(t=0;t<2;t++)
            {
            	C[i][j]=C[i][j]+A[i][t]*B[t][j];
            }
        }
	}
}
 
void MATRIX_ADD(int n,float X[][N],float Y[][N],float Z[][N]) 
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            Z[i][j]=X[i][j]+Y[i][j];
        }
    }
}
 
void MATRIX_SUB(int n,float X[][N],float Y[][N],float Z[][N]) 
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            Z[i][j]=X[i][j]-Y[i][j];
        }
    }
}
 
void STRASSEN(int n,float A[][N],float B[][N],float C[][N])  
{
    float A11[N][N],A12[N][N],A21[N][N],A22[N][N];
    float B11[N][N],B12[N][N],B21[N][N],B22[N][N];
    float C11[N][N],C12[N][N],C21[N][N],C22[N][N];
    float M1[N][N],M2[N][N],M3[N][N],M4[N][N],M5[N][N],M6[N][N],M7[N][N];
    float AA[N][N],BB[N][N],MM1[N][N],MM2[N][N];
    int i,j;
    if (n==2) MATRIX_MULTIPLY(A,B,C);
    else
    {
        for(i=0;i<n/2;i++)   
		{        
            for(j=0;j<n/2;j++)
            {
            	A11[i][j]=A[i][j];
             	A12[i][j]=A[i][j+n/2];
              	A21[i][j]=A[i+n/2][j];
               	A22[i][j]=A[i+n/2][j+n/2];
                B11[i][j]=B[i][j];
                B12[i][j]=B[i][j+n/2];
                B21[i][j]=B[i+n/2][j];
                B22[i][j]=B[i+n/2][j+n/2];
  			}
		}
    	MATRIX_SUB(n/2,B12,B22,BB);          
    	STRASSEN(n/2,A11,BB,M1);
		//M1=A11(B12-B22)
    	MATRIX_ADD(n/2,A11,A12,AA);
    	STRASSEN(n/2,AA,B22,M2);
		//M2=(A11+A12)B22
    	MATRIX_ADD(n/2,A21,A22,AA);
    	STRASSEN(n/2,AA,B11,M3);
		//M3=(A21+A22)B11
    	MATRIX_SUB(n/2,B21,B11,BB);
    	STRASSEN(n/2,A22,BB,M4);
		//M4=A22(B21-B11)
    	MATRIX_ADD(n/2,A11,A22,AA);
    	MATRIX_ADD(n/2,B11,B22,BB);
    	STRASSEN(n/2,AA,BB,M5);
		//M5=(A11+A22)(B11+B22)
    	MATRIX_SUB(n/2,A12,A22,AA);
    	MATRIX_SUB(n/2,B21,B22,BB);
    	STRASSEN(n/2,AA,BB,M6);
		//M6=(A12-A22)(B21+B22)
    	MATRIX_SUB(n/2,A11,A21,AA);
    	MATRIX_SUB(n/2,B11,B12,BB);
    	STRASSEN(n/2,AA,BB,M7);
		//M7=(A11-A21)(B11+B12)
    	MATRIX_ADD(N/2,M5,M4,MM1);                
    	MATRIX_SUB(N/2,M2,M6,MM2);
    	MATRIX_SUB(N/2,MM1,MM2,C11);
		//C11=M5+M4-M2+M6
    	MATRIX_ADD(N/2,M1,M2,C12);
		//C12=M1+M2
    	MATRIX_ADD(N/2,M3,M4,C21);
		//C21=M3+M4
    	MATRIX_ADD(N/2,M5,M1,MM1);
    	MATRIX_ADD(N/2,M3,M7,MM2);
    	MATRIX_SUB(N/2,MM1,MM2,C22);
		//C22=M5+M1-M3-M7
    	for(i=0;i<n/2;i++)
    	{
        	for(j=0;j<n/2;j++)
        	{
            	C[i][j]=C11[i][j];
            	C[i][j+n/2]=C12[i][j];
            	C[i+n/2][j]=C21[i][j];
            	C[i+n/2][j+n/2]=C22[i][j];
        	}                                       
    	}
    }
}

3.棋盘覆盖
在一个nxn(n=2^k)个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

当k>0时将2棋盘分割为4个子棋盘。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格，即4个子问题出现差异。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模、完全相同的棋盘覆盖子问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。


#include<iostream>
using namespace std;
int nCount=0,row,col;
int matrix[100][100];
void chessBoard(int tr,int tc,int dr,int dc,int size);
 
int main()
{
    int size;
    memset(matrix,0,sizeof(matrix));
    cin>>size>>row>>col;
    chessBoard(0,0,row,col,size);
    for(int i=0;i<size;i++)
    {
        for(int j=0;j<size;j++)
        {
            cout<<matrix[i][j]<<" "; 
        }
        cout<<endl;
    }
    return 0;
}
 
void chessBoard(int tr,int tc,int dr,int dc,int size)
{
//五个参数分别是方格左上角点的坐标,特殊点的坐标和方格的大小 
    int s,t;
    if(1==size) return;
    s=size/2;
    t=++nCount;
    //判断特殊方格是否在左上方 
    if(dr<tr+s&&dc<tc+s)
    {
        chessBoard(tr,tc,dr,dc,s);
    }
    else
    {
        matrix[tr+s-1][tc+s-1]=t;
        chessBoard(tr,tc,tr+s-1,tc+s-1,s);
    }
    //判断特殊方格是否在右上方
    if(dr<tr+s&&dc>=tc+s)
    {
        chessBoard(tr,tc+s,dr,dc,s);
    }
    else
    {
        matrix[tr+s-1][tc+s]=t;
        chessBoard(tr,tc+s,tr+s-1,tc+s,s);
    }
    //判断特殊方格是否在左下方 
    if(dr>=tr+s&&dc<tc+s)
    {
        chessBoard(tr+s,tc,dr,dc,s);
    } 
    else
    {
        matrix[tr+s][tc+s-1] = t;
        chessBoard(tr+s,tc,tr+s,tc+s-1,s);
    }
    ///判断特殊方格是否在右下方 
    if(dr>=tr+s&&dc>=tc+s)
    {
        chessBoard(tr+s,tc+s,dr,dc,s);
    } 
    else
    {
        matrix[tr+s][tc+s]=t;
        chessBoard(tr+s,tc+s,tr+s,tc+s,s);
    }
}

4.归并排序
将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
综上可知：
归并排序其实要做两件事：
分解——将序列每次折半划分。
合并——将划分后的序列段两两合并后排序。
很容易写出递归的代码：


void MergeSort(Type a[], int left, int right)
{
    if(left<right) 
    {                  
        int i=(left+right)/2;           
        MergeSort(a,left,i);        //左子问题求解       
        MergeSort(a,i+1,right);     //右子问题求解
        merge(a,b,left,i,right);    //合并到数组b
        copy(a,b,left,right);       //复制回数组a
    }
}
从分治策略的机制入手，可以消除算法中的递归。
#include<iostream>
using namespace std;
 
template<class Type> 
void MergeSort(Type a[],int n)
{
    Type *b=new Type[n];
    int s=1;
    while(s<n)
    {
        MergePass(a,b,s,n);
        //合并到数组b
        s+=s;
        MergePass(b,a,s,n);
        //合并到数组a
        s+=s; 
    } 
}
 
template<class Type>
void MergePass(Type x[],Type y[],int s,int n)
{
    int i=0;
    while(i<n-2*s)
    //合并大小为s的相邻2段子数组 
    {
        Merge(x,y,i,i+s-1,i+2*s-1);
        i=i+2*s; 
    }
    if(i+s<n) Merge(x,y,i,i+s-1,n-1);
    else for(int j=i;j<=n-1;j++) y[j]=x[j];
}
 
template<class Type>
void Merge(Type c[],Type d[],int l,int m,int r)
//合并c[l:m]和c[m+1:r]到d[l:r] 
{
    int i=l,j=m+1,k=l;
    while((i<=m)&&(j<=r))
    {
        if(c[i]<=c[j]) d[k++]=c[i++];
        else d[k++]=c[j++];
    }
    if(i>m) for(int q=j;q<=r;q++) d[k++]=c[q];
    else for(int q=i;q<=m;q++) d[k++]=c[q];
}
 
int main()
{
    int array[10]={2,3,1,5,8,9,4,6,7,0};
    MergeSort(array,10);
    for(int i=0;i<10;i++)
    {
        cout<<array[i]<<" ";
    }
    cout<<endl;
}

5.快速排序
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。


#include<iostream>
using namespace std;
 
template<class Type>
int Partition(Type a[],int p,int r)
{
    int i=p,j=r+1; 
    Type x=a[p];
    //将小于x的元素交换到左边区域
    //将大于x的元素交换到右边区域
    while(true) 
    {
        while(a[++i]<x);
          while(a[--j]>x);
        if(i>=j) break; 
        swap(a[i],a[j]);
      }
    a[p]=a[j];
    a[j]=x;
    return j;
}
 
template<class Type>
void QuickSort(Type a[],int p,int r)
{
    if(p<r) 
    {
        int q=Partition(a,p,r);
        QuickSort(a,p,q-1); //对左半段排序
        QuickSort(a,q+1,r); //对右半段排序
      }
}
 
int main()
{
    int array[10]={1,2,6,7,5,4,8,9,0,3};
    QuickSort(array,0,9);
    for(int i=0;i<=9;i++)
    {
        cout<<array[i]<<" ";
    }
    cout<<endl;
}

快速排序有一些常见的优化方法。例如选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴或者随机选取元素作为中轴。这一改进对于原来的快速排序算法来说，最坏情况发生的几率减小了。
6.线性时间选择
给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。当 k=1时相当于求最小元素；当k=n时相当于求最大元素；当k=(n+1)/2时相当于求中位数。我们可以模仿递归划分排序算法，对输入数据进行划分排序。


#include<iostream>
#include<cstdlib> 
using namespace std;
 
int Partition(int a[],int p,int r)
{
    int i=p,j=r+1; 
    int x=a[p];
    //将小于x的元素交换到左边区域
    //将大于x的元素交换到右边区域
    while(true) 
    {
        while(a[++i]<x);
          while(a[--j]>x);
        if(i>=j) break; 
        swap(a[i],a[j]);
      }
    a[p]=a[j];
    a[j]=x;
    return j;
}
 
int RandomizedPartition(int a[],int p,int r)
{
          int i=((double)rand()/RAND_MAX)*(r-p)+p;
          //生成p到r的随机数 
        swap(a[i],a[p]);
        return Partition(a,p,r);
}
 
int RandomizedSelect(int a[],int p,int r,int k)
//在p到r中找第k小的元素 
{
      if(p==r) return a[p];
      int i=RandomizedPartition(a,p,r);        
      //划分为2部分
      int j=i-p+1;   
      if(k<=j) return RandomizedSelect(a,p,i,k); //在左半部分查找
      else return RandomizedSelect(a,i+1,r,k-j); //在右半部分查找
}
 
int main()
{
    int array[10]={11,27,84,32,99,61,46,50,2,100};
    for(int i=1;i<=10;i++)
    {
        cout<<RandomizedSelect(array,0,9,i)<<endl;
    }
}

用于寻找中位数时，如果能在线性时间内找到一个划分基准使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1)，那么就可以在最坏情况下用O(n)时间完成选择任务。例如，当ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递推式T(n)<=T(9n/10)+O(n)。由此可得T(n)=O(n)。标准做法是这样的：
(1)将n个输入元素划分成[n/5]个组，每组5个元素，只可能有一个组不是5个元素；
(2)用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数；
(3)递归找出这[n/5]个元素的中位数，如果[n/5]是偶数，就找它的2个中位数中较大的一个，以这个元素作为划分基准。将全部的数划分为两个部分，小于基准的在左边，大于等于基准的放右边。


#include<cstdio>
#include<iostream>  
#include<algorithm> 
using namespace std;   
static int a[10000010]; 
long long int N;
 
void BubbleSort(int a[],int p,int r)  
{       
     for(int i=p;i<=r;i++)    
     {    
        for(int j=r;j>i;j--)    
        {    
            if(a[j]<a[j-1])    
            {    
                swap(a[j],a[j-1]);     
            }     
        }               
     }  
}  
  
int Partition(int a[],int p,int r,int x)
{
    int i=p,j=r+1; 
     while(true)
    {
        while(a[++i]<x&&i<r);
        while(a[--j]>x);
        if(i>=j) break; 
        swap(a[i],a[j]);
    }
      return j;
}
 
int Select(int a[],int p,int r,int k)  
{  
    if(r-p<20)  
    {  
        BubbleSort(a,p,r);  
        return a[p+k-1];  
    }   
    for(int i=0;i<=(r-p-4)/5;i++)  
    {  
        BubbleSort(a,p+5*i,p+5*i+4);  
        swap(a[p+5*i+2],a[p+i]);  
    }  
    int x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);  
    int i=Partition(a,p,r,x);  
    int j=i-p+1;  
    if(k<=j) return Select(a,p,i,k);  
    else return Select(a,i+1,r,k-j);  
}
 
int main()  
{  
    cin>>N;
    for(int i=0;i<N;i++)  
    {  
        scanf("%d",&a[i]);
    }  
    if(N%2) cout<<Select(a,0,N-1,N/2+1)<<endl;
    else cout<<(Select(a,0,N-1,N/2)+Select(a,0,N-1,(N/2)+1))/2<<endl;
}

7.最近点对
最近点对问题是指，给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。为了使问题变得简单，首先考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数x1，x2，...，xn。最接近点对即为这n个实数中相差最小的两个实数。显然可以先将点排好序，然后线性扫描就可以了。但我们为了便于推广到二维的情形，尝试用分治法解决这个问题。假设我们用m点将S分为S1和S2两个集合，这样一来，对于所有的p(S1中的点)和q(S2中的点)，有p<q。递归地在S1和S2上找出最接近点对{p1,p2}和{q1,q2}，并设d=min{ |p1-p2| , |q1-q2| }，由此易知，S中最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{q3,p3}。
如果最接近点对是{q3,p3}，即|p3-q3|<d，则p3和q3两者与m的距离都不超过d，且在区间(m-d,d]和(d,m+d]各有且仅有一个点。这样，就可以在线性时间内实现合并。在二维情形下，选取一垂直线l:x=m来作为分割直线。其中m为S中在x坐标上第[n/2]小、第([n/2]+1)小的2个点的x坐标的平均值。由此，将平面S分割为子平面S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，根据d构造点集P1、P2。则S中的最接近点对(p,q)有3种情况：位于左边的S1中距离d；位于右边的S2中距离d；某个{p, q}，p∈左边点集合P1且q∈右边点集合P2。考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d。这时满足这个条件的P2中的点一定落在一个对称于过p点的水平线的d×2d的矩形R中。
由d的意义可知，P2中任何2个点的距离都不小于d，由此可以推出矩形R中最多只有6个点。因为如果将矩形R长为2d的边3等分，长为d的边2等分，就可以得到6个(d/2)×(2d/3)的矩形。若矩形R中多于6个点，则至少有一个(d/2)×(2d/3)的小矩形中有2个以上的点，这两个点之间的距离一定小于d，这样就矛盾了。为了知道要检查哪6个点，可以将点p和所有P2中的点投影到垂直线l上。由于能与p构成最接近点对候选者的q一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只需要检查P2中排好序的相继6个点。


#include<cmath>  
#include<algorithm> 
#include<iostream>    
using namespace std;  
const double INF=1e20;  
const int N=100005;  
struct Point  
{  
    double x;  
    double y;  
}point[N];  
int n,tmp[N];  
  
bool cmpxy(const Point& a,const Point& b)  
{  
    if(a.x!=b.x) return a.x<b.x;  
    return a.y<b.y;  
}  
  
bool cmpy(const int& a,const int& b)  
{  
    return point[a].y<point[b].y;  
}  
  
double min(double a,double b)  
{  
    return a<b?a:b;  
}  
  
double dis(int i, int j)  
{  
    return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));  
}  
  
double ClosestPair(int left,int right)  
{  
    double d=INF;  
    if(left==right) return d;  
    if(left+1==right) return dis(left,right);  
    int mid=(left+right)>>1;  
    double d1=ClosestPair(left,mid);  
    double d2=ClosestPair(mid+1,right);  
    d=min(d1,d2);  
    int i,j,k=0;  
    //分离出宽度为2d的区间  
    for(i=left;i<=right;i++)  
    {  
        if(fabs(point[mid].x-point[i].x)<=d) tmp[k++]=i;  
    }  
    sort(tmp,tmp+k,cmpy);   
    for(i=0;i<k;i++)  
    {  
        for(j=i+1;j<k&&point[tmp[j]].y-point[tmp[i]].y<d;j++)  
        {  
            double d3=dis(tmp[i],tmp[j]);  
            if(d>d3) d=d3;  
        }  
    }  
    return d;  
}  
  
int main()  
{  
    cin>>n;
     for(int i=0;i<n;i++) cin>>point[i].x>>point[i].y;  
      sort(point,point+n,cmpxy);  
       cout<<ClosestPair(0,n-1)<<endl;    
}

8.循环赛日程表
设计一个满足以下要求的比赛日程表：对n(n=2^k)个选手，每个选手必须与其他n-1个选手各赛一次；每个选手一天只能赛一次；循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了：左上角块中的数字抄到右下角块对应位置；左下角块中的数字抄到右上角块对应位置。


#include<iostream>      
#include<cmath>
using namespace std;   
  
void Table(int k,int n,int **a);  
 
int main()  
{  
    int k;  
    cin>>k;  
    int n=1;  
    for(int i=1;i<=k;i++)  n*=2;
    int **a=new int *[n+1];  
    for(int i=0;i<=n;i++) a[i]=new int[n+1];  
    Table(k,n,a);  
    for(int i=1;i<=n;i++)  
    {  
        for(int j=1;j<=n;j++)  
        {  
            cout<<a[i][j]<<" ";  
        }  
        cout<<endl;  
    }  
    for(int i=0;i<=n;i++) delete[] a[i];  
    delete[] a;  
}   
  
void Table(int k,int n,int **a)  
{  
    for(int i=1;i<=n;i++) a[1][i]=i;//设置日程表第一行
    int m=1;
    //每次填充时起始填充位置  
    for(int s=1;s<=k;s++)  
    {  
        n/=2;  
        for(int t=1;t<=n;t++)  
        {  
            for(int i=m+1;i<=2*m;i++)  
            {  
                for(int j=m+1;j<=2*m;j++)
                {  
                    a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m];//右下角等于左上角的值  
                    a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2];//左下角等于右上角的值  
                }  
                  
            }  
        }  
        m*=2;  
    }  
}

关于递归与分治的基础知识就简要介绍到这里，希望能作为大家继续深入学习的基础。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/716374