分 治 算 法_分治算法

目录

一、什么是分治（what？）

二、为什么要分治（why? ）

三、怎么使用分治（how？）

四、典型例题分析：

        例题1：猜数字游戏--二分搜索技术 

        例题2：合久必分，分久必合--合并排序 

        例题3：兵贵神速--快速排序

        例题4：效率至上--大整数乘法

---

一、什么是分治（what？）

        分治，即分而治之。这是一种将大规模问题分解为若干个规模较小的相同子问题，进而求得最终结果的一种策略思想。

二、为什么要分治（why? ）

        当一个问题规模较大，且

        （1）原问题可分为若干个规模较小的子问题。

        （2）子问题相互独立。

        （3）子问题的解可以合并为原问题的解。

        这时使用分治算法能更好的解决问题。

三、怎么使用分治（how？）

分治的步骤一般如下：

        （1）分解：将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。

        （2）治理：求解各个子问题。由于各个子问题与原问题形式相同，只是规模小而已，而当子问题划分得足够小时，就可以用较简单的方法解决。

        （3）合并：按原问题的要求，将子问题的解逐层合并成原问题的解。

        就是化整为零，在化零为整的过程。

        在分治中，递归是一把利器。

四、典型例题分析：

        例题1：猜数字游戏--二分搜索技术 

                

  

 问题分析：

        在最坏的情况，需要猜n次才能得出答案，但是由于0~10是一串有序的数，我们没必要一个一个去猜，可以从中间开始向两边搜索，这样可以大大提高寻找效率。所以这里要介绍一种新的查找方法——折半查找。当我们的面对的数据是有序序列时，就可以使用这种策略。

算法设计：

        问题简化：

        给定n个元素，这些元素是有序的（假设为升序），从中查找指定元素x。

        算法思想：

        将有序列分成两部分，将待查元素与中间值进行比较，如果相等，返回中间值；若果小于中间值，那么将原序列的右半部分切掉，将x和左边序列的中间值比较，再重复以上判定。

        算法设计：

        用一维数组s[]存储有序序列，设变量low和high表示查找范围的下界和上界，mid表示查找范围的中间位置，x为特定待查值。

        （1）初始化。令low=0，即指向有序数列的第一个元素，high = n - 1，指有序数列的最后一个元素。mid指向中间值 （high-low）/2+low 或者 ( high+low)/2

        （2）判定关系若low<=high，则判断x和s[mid]的大小关系，如果x>s[mid],low = mid+1,更新中间值mid = (low+high)/2；如果x<s[mid],high=mid-1,更新中间值mid = (low+high)/2。若果x==s[mid],返回mid就是x的位置。

        （3）如果low>high,说明数据错误，待查值不存在。

        图解算法：

            

         伪代码：

        二分搜索：

int BinarySearch(int n,int s[],int x)
{
	int low=0,high=n-1;
	while(low<=high)
	{
		int mid=(high-low)/2+low;
		if(x==s[mid])
		{
			return mid;
		}
		else if(x<s[mid])
		{
			high=mid-1;
		}
		else if(x>s[mid])
		{
			low=mid+1;
		}
	}
	return -1;//返回-1没找到x 
}

实战代码： 

 #include<iostream>
#include<algorithm> 
using namespace std;
 
const int M=10000;
int x,n,i;
int s[M];
 
int BinarySearch(int n,int s[],int x)
{
	int low=0,high=n-1;
	while(low<=high)
	{
		int mid=(high-low)/2+low;
		if(x==s[mid])
		{
			return mid;
		}
		else if(x<s[mid])
		{
			high=mid-1;
		}
		else
		{
			low=mid+1;
		}
	}
	return -1;//返回-1没找到x 
}
 
int main()
{
	cout<<"请输入数列中的元素："<<endl;
	while(cin>>n)
	{
		cout<<"请依次输入列表中元素：";
		for(int i=0; i < n; i++)
		{
			cin>>s[i];
		}
		sort(s,s+n);
		cout<<"排列后的数组为：";
		for(int i=0; i < n; i++)
		{
			cout<<s[i]<<' ';
		}
		cout<<endl;
		cout<<"请输入要查元素：";
		cin>>x;
		i = BinarySearch(n,s,x);
		if(i==-1) cout<<"该数列中没有待查值。"<<endl;
		else cout<<"已查到的元素在"<<i<<"位"<<endl;
	}
	return 0;
}
 
 

 算法复杂度分析：

        例题2：合久必分，分久必合--合并排序 

问题分析：

        显然，合并排序采用的策略就是分治。将一个给定的无序数列，分解成两个规模大致相同的子序列，然后将两个子序列进行排序和合并。如果面对的问题不易解决就继续将子序列在分，直到分解成单个元素为一个子序列，这是每一个序列都可以当做是一个排好的子序列，然后在进行合并，得到一个完整的序列。

算法设计：

        合并排序采用分治策略实现对n个元素进行排序的算法，是分治法的一个典型应用和完美体现。他是一种平衡、简单的二分分治策略。过程大致如下：

        （1）分解——将待排序列元素分成大小大致相同的两个子序列。

        （2）治理——对两个子序列进行合并排序。

        （3）合并——将排好序的有序子序列进行合并，得到最终的有序序列。

算法图解：

        

伪代码：

        （1）合并算法：

void Merge(int A[],int low,int mid,int high)
{
	int *B = new int[high-low+1];
	int i = low,j = mid+1,k = 0;
	while(i<=mid&&j<=high)
	{
		if(A[i]<=A[j])
			B[k++]=A[i++];//这里是先对数组赋值，再移动指针
		else
			B[k++]=A[j++];
	}
	//如果前一半剩余
	while(i<=mid)
	{
		B[k++]=A[i++];	
	} 
	//如果后一半有剩余
	while(j<=high)
	{
		B[k++]=A[j++];	
	} 
	//将合并的序列赋值给A数组
	for(i = low,k=0; i <= high; i++)
	{
		A[i] = B[k++];	
	} 
}

               （2）分治算法（递归）

void MergeSort(int A[],int low, int high)
{
	if(low<high)
	{
		int mid = (low+high)/2;
		MergeSort(A,low,mid);//左边拆分
		MergeSort(A,mid+1,high);//右边拆分
		Merge(A,low,mid,high);//分久必合 
	}
}

实战代码：

#include<iostream>
using namespace std; 
void Merge(int A[],int low,int mid,int high)
{
	int *B = new int[high-low+1];
	int i = low,j = mid+1,k = 0;
	while(i<=mid&&j<=high)
	{
		if(A[i]<=A[j])
			B[k++]=A[i++];//这里是先对数组赋值，再移动指针
		else
			B[k++]=A[j++];
	}
	//如果前一半剩余
	while(i<=mid)
	{
		B[k++]=A[i++];	
	} 
	//如果后一半有剩余
	while(j<=high)
	{
		B[k++]=A[j++];	
	} 
	//将合并的序列赋值给A数组
	for(i = low,k=0; i <= high; i++)
	{
		A[i] = B[k++];	
	} 
}
void MergeSort(int A[],int low, int high)
{
	if(low<high)
	{
		int mid = (low+high)/2;
		MergeSort(A,low,mid);//左边拆分
		MergeSort(A,mid+1,high);//右边拆分
		Merge(A,low,mid,high);//分久必合 
	}
}
int main()
{
     int n, A[100]; 
     cout<<"请输入数列中的元素个数n为："<<endl; 
     cin>>n; 
     cout<<"请依次输入数列中的元素："<<endl; 
     for(int i=0; i<n; i++)
          cin>>A[i]; 
     MergeSort(A,0,n-1); 
     cout<<"合并排序结果："<<endl; 
     for(int i=0;i<n;i++)
          cout<<A[i]<<" ";
     cout<<endl; 
     return 0; 
}
 
 
 
 

算法复杂度：

        例题3：兵贵神速--快速排序

 问题分析：

 算法设计：

快速排序的基本思想也是分治。

（1）分解：先从数列中选取一个元素作为基准。以基准元素为标准。比基准元素小的值放在基准元素左边，比基准元素大的值放在基准元素右边。

（2）治理：对两个子序列进行快速排序。

（3）合并：将两个排好的序列合在一起，得到原问题的解。

 图解算法：

伪代码：

（1）划分函数

int Partition(int r[],int low,int high)   //划分函数
{
     int i=low,j=high,pivot=r[low];       //基准元素
     while(i<j) 
     {
         while(i<j&&r[j]>pivot) 
             j--;                         //向左扫描
         if(i<j) 
         {
             swap(r[i++],r[j]);           //r[i]和r[j]交换后i右移一位
         }
         while(i<j&&r[i]<=pivot) 
             i++;                         //向右扫描
         if(i<j) 
         {
              swap(r[i],r[j--]);          //r[i]和r[j]交换后j左移一位
         }
     }
     return i;                            //返回最终划分完成后基准元素所在的位置
}

 （2）快速排序递归 

void QuickSort(int R[],int low,int high){ 
     int mid; 
     if(low<high) 
     {
          mid=Partition(R,low,high);      //返回基准元素位置
          QuickSort(R,low,mid-1);         //左区间递归快速排序
          QuickSort(R,mid+1,high);        //右区间递归快速排序
     }
}

 实战代码：

#include <iostream>
using namespace std; 
int Partition(int r[],int low,int high) //划分函数
{
     int i=low,j=high,pivot=r[low];     //基准元素
     while(i<j) 
     {
          while(i<j&&r[j]>pivot) j--;   //向左扫描
          if(i<j) 
          {
               swap(r[i++],r[j]);       //r[i]和r[j]交换后i右移一位
          }
          while(i<j&&r[i]<=pivot) i++;  //向右扫描
          if(i<j) 
          {
               swap(r[i],r[j--]);       //r[i]和r[j]交换后j左移一位
          }
     }
     return i;                          //返回最终划分完成后基准元素所在的位置
}
void QuickSort(int R[],int low,int high)//快速排序递归算法
{
     int mid; 
     if(low<high) 
     {
          mid=Partition(R,low,high);    //基准位置
          QuickSort(R,low,mid-1);       //左区间递归快速排序
          QuickSort(R,mid+1,high);      //右区间递归快速排序
     }
}
int main()
{
     int a[1000]; 
     int i,N; 
     cout<<"请先输入要排序的数据的个数：";
     cin>>N; 
     cout<<"请输入要排序的数据：";
     for(i=0;i<N;i++)
          cin>>a[i]; 
     cout<<endl; 
     QuickSort(a,0,N-1); 
     cout<<"排序后的序列为："<<endl; 
     for(i=0;i<N;i++)
          cout<<a[i]<<" " ; 
     cout<<endl; 
     return 0; 
}

        例题4：效率至上--大整数乘法

问题分析：

算法设计：

 图解算法：

道理都懂，那么具体应该如何操作？

首先将两个大整数以字符串形式输入，

转换成数字后，倒序存储在s[]中，

l 表示数的长度，

c 表示数的次幂。

两个大数的初始次幂是0.

(1)初始化

（2）分解

（3）求解子问题

(4)继续求解子问题

（5）合并

伪代码：

（1）数据结构

        将两个大数以字符串的形式输入，然后定义结构体Node，其中：

        s[]存储大数倒序，l 表示长度，c 表示次幂。两个大数的初始次幂为0.

char sa[10000];//接收大数的字符串 
char sb[10000];//接收大数的字符串
 
typedef struct _Node{
	int s[M];//数组，倒序存储大数 
	int l;//代表数的长度 
	int c;//代表数的次幂 
}Node,*pNode; 

（2）划分函数

        其中，cp（）函数用于将一个n位的数分成两个n/2的数并储存，纪录它的次幂。

void cp(pNode*src,pNode*des,int st,int l)
{
	//src表示分解的数结点，des表示分解后得到的数结点
	//st表示从src结点数组中取数的开始位置，1表示取数的长度
	int i,j;
	for(i = st,j=0;i<st+l;i++,j++)
	{
		des->s[j] = src->s[i];	
	}	
	des->l = l;//长度等于取数的长度 
	des->c = st+src->c;//des次幂等于开始取数的位置加上src 
} 

举例：如果有大数43579，我们应该把数放在结点a中

ma = a.l/2;                           //ma表示a长度的一半，此例中a.l=5，ma=2

 这样两次调用cp（）函数，我们就把一个大的整数分解成了两个长度约为原来一半的整数。

（3）乘法运算

定义mul函数用于将两数相乘，不断分解，直到有一个乘数为1时停止，让这两个数相乘，并记录结果回溯。

ma = pa->l/2; //ma表示a长度的一半
mb = pb->l/2; //mb表示b长度的一半
if(!ma || !mb) //如果!ma说明ma=0，即a的长度为1，该乘数为1位数
               //如果!mb说明mb=0，即b的长度为1，该乘数为1位数
{
     if(!ma)   //!ma说明a为1位数，a、b交换，保证a的长度大于等于b的长度
     {
          temp =pa; 
          pa = pb; 
          pb = temp; 
     }         //交换后b的长度为1
     ans->c = pa->c + pb->c;          //结果的次幂等于两乘数次幂之和
     w = pb->s[0];//因为交换后b的长度为1，用变量 w记录即可
     cc= 0;    //初始化进位cc为0
     for(i=0; i <pa->l; i++)          //把a中的数依次取出与w相乘，记录结果和进位
     {
         ans->s[i] = (w*pa->s[i] + cc)%10;//存储相乘结果的个位，十位做进位处理
         cc = (w*pa->s[i] + cc)/10;   //处理进位
     }

（4）合并函数

add（）函数将分解得到的数进行相加合并。

void add(pNode pa, pNode pb, pNode ans) 
{   //程序调用时把 a、b地址传递给pa、pb参数，表示待合并的两个数
    //ans记录它们相加的结果
    int i, cc, k,alen,blen,len; 
    int ta, tb;         //ta、tb分别记录a、b相加时对应位上的数
    pNode temp; 
    if(pa->c <pb->c)    //交换以保证a的次幂大
    {
          temp = pa; 
          pa = b; 
          pb =temp; 
    }
    ans->c = pb->c;  //结果的次幂为两个数中小的次幂
    cc = 0;          //初始化进位cc为0
    k=pa->c - pb->c  //k为a左侧需要补零的个数

        

  alen=pa->l + pa->c;       //a数加上次幂的总长度，上例中alen=6
    blen=pb->l + pb->c;       //b数加上次幂的总长度，上例中alen= 5
    if(alen>blen) 
          len=alen;           //取a、b总长度的最大值
    else
          len=blen; 
    len=len-pb->c;         //结果的长度为a，b之中的最大值减去最低次幂，上例中len= 4
                 //最低次幂是不进行加法运算的位数) 
    for(i=0; i<len; i++) 
    {
         if(i <k)             //k为a左侧需要补零的个数
               ta = 0;        //a左侧补零
         else
               ta =pa->s[i-k];//i=k时，补0结束，从a数组中第0位开始取数字
         if(i <b->l) 
               tb = pb->s[i]; //从b数组中第0位开始取数字
         else
               tb = 0;        //b数字先取完，b右侧补0
         if(i>=pa->l+k)       //a数字先取完，a右侧补0
               ta = 0; 
         ans->s[i] = (ta + tb + cc)%10;  //记录两位之和的个位数，十位做进位处理
         cc = (ta + tb + cc)/10; 
    }

 

实战代码：

//program 3-4
#include <stdlib.h>
#include <cstring>
#include <iostream>
using namespace std;
#define M 100
char sa[1000];
char sb[1000];
typedef struct _Node
{
     int s[M];
     int l;                 //代表字符串的长度
     int c;
} Node,*pNode;
void cp(pNode src, pNode des, int st, int l)
{
     int i, j;
     for(i=st, j=0; i<st+l; i++, j++)
     {
          des->s[j] = src->s[i];
     }
     des->l = l;
     des->c = st + src->c;  //次幂
}
void add(pNode pa, pNode pb, pNode ans)
{
     int i,cc,k,palen,pblen,len;
     int ta, tb;
     pNode temp;
     if((pa->c<pb->c))          //保证Pa的次幂大
     {
          temp = pa;
          pa = pb;
          pb = temp;
     }
     ans->c = pb->c;
     cc = 0;
     palen=pa->l + pa->c;
     pblen=pb->l + pb->c;
     if(palen>pblen)
          len=palen;
     else
          len=pblen;
     k=pa->c - pb->c;
     for(i=0; i<len-ans->c; i++) //结果的长度最长为pa，pb之中的最大长度减去最低次幂
     {
          if(i<k)
               ta = 0;
          else
               ta = pa->s[i-k];        //次幂高的补0，大于低的长度后与0进行计算
          if(i<pb->l)
               tb = pb->s[i];
          else
               tb = 0;
          if(i>=pa->l+k)
               ta = 0;
          ans->s[i] = (ta + tb + cc)%10;
          cc = (ta + tb + cc)/10;
     }
     if(cc)
          ans->s[i++] = cc;
     ans->l = i;
}
 
void mul(pNode pa, pNode pb, pNode ans)
{
     int i, cc, w;
     int ma = pa->l>>1, mb = pb->l>>1; //长度除2
     Node ah, al, bh, bl;
     Node t1, t2, t3, t4, z;
     pNode temp;
     if(!ma || !mb)                    //如果其中个数为1
     {
          if(!ma)  //如果a串的长度为1，pa,pb交换，pa的长度大于等于pb的长度
          {
               temp = pa;
               pa = pb;
               pb = temp;
          }
          ans->c = pa->c + pb->c;
          w = pb->s[0];
          cc = 0;                   //此时的进位为c
          for(i=0; i < pa->l; i++)
          {
               ans->s[i] = (w*pa->s[i] + cc)%10;
               cc= (w*pa->s[i] + cc)/10;
          }
          if(cc)
               ans->s[i++] = cc;   //如果到最后还有进位，则存入结果
          ans->l = i;              //记录结果的长度
          return;
     }
     //分治的核心
     cp(pa, &ah, ma, pa->l-ma);    //先分成4部分al,ah,bl,bh
     cp(pa, &al, 0, ma);
     cp(pb, &bh, mb, pb->l-mb);
     cp(pb, &bl, 0, mb);
 
     mul(&ah, &bh, &t1);           //分成4部分相乘
     mul(&ah, &bl, &t2);
     mul(&al, &bh, &t3);
     mul(&al, &bl, &t4);
 
     add(&t3, &t4, ans);
     add(&t2, ans, &z);
     add(&t1, &z, ans);
}
 
int main()
{
     Node ans,a,b;
     cout << "输入大整数 a："<<endl;
     cin >> sa;
     cout << "输入大整数 b："<<endl;
     cin >> sb;
     a.l=strlen(sa);               //sa,sb以字符串进行处理
     b.l=strlen(sb);
     int z=0,i;
     for(i = a.l-1; i >= 0; i--)
          a.s[z++]=sa[i]-'0';      //倒向存储
     a.c=0;
     z=0;
     for(i = b.l-1; i >= 0; i--)
          b.s[z++] = sb[i]-'0';
     b.c = 0;
     mul(&a, &b, &ans);
     cout << "最终结果为：";
     for(i = ans.l-1; i >= 0; i--)
          cout << ans.s[i];        //ans用来存储结果，倒向存储
     cout << endl;
     return 0;
}