900字范文 > 算法导论—分治策略（C语言）

算法导论—分治策略（C语言）

时间：2022-03-30 02:00:41

相关推荐

算法导论—分治策略（C语言）

在分治策略中，我们递归的求解一个问题，在每层递归中应用以下三个步骤：

1.分解将问题划分为一个个子问题，子问题形式与原问题一致，只是规模更小

2.解决这里的解决是指递归的求解出子问题，或对子问题直接求解（当子问题足够小）

3.合并将子问题的解组合成原问题的解

总的来说，分治策略即分而治之，再合。

递归式

递归式与分治方法是紧密相关的。递归式是通过更小的输入上的函数值来描述一个函数，它可以有很多形式。

下面我们主要介绍三种求解递归式的方法：

1.代入法我们猜测一个界，并用数学归纳法证明这个界是正确的

2.递归树法：将递归式转化为一棵树，并用边界和技术求解递归式

3.主方法

要点一最大子数组问题

方法一暴力求解方法

定义：根据问题的描述和定义直接求解，不使用特殊算法。

暴力求解就是枚举所有可能的解，再进行校验求出正确的解

int search(int*data,int low,int high,int left,int right)//data为数组,low,right为数组边界,left,right存放返回最大子数组的左右边界{int sum=0,i,j,sum_temp;//给sum赋初值为0，方便sum和sum_temp的第一次比较,sum_temp为临时存放数组和的元素for(i=low;i<=high;i++)//用i遍历数组{sum_temp=0;//规定每次i值变化时，sum_temp归零，sum_temp重新加法for(j=i;j<=high;j++)//j从i开始遍历[i,high]{sum_temp+=data[j];//计算[i,j]之和if(sum_temp>sum)//比较上一个最大数组和sum和此时sum_temp{sum=sum_temp;left=i;//存放最大子数组和的左边界right=j;//存放最大子数组和的右边界}}}return sum;//返回最大子数组的和}

上述代码需要说明的是，我们采用两个for循环，一个确定循环起点，一个确定循环终点

方法二使用分治策略的解决方法

分治方法要求我们尽量将子数组划分为两个规模尽量相等的子数组，即找到子数组的中间位置mid，将子数组划分为[low,mid],[mid,high]，那么我们可知任何连续子数组必定满足以下三种情况之一：

1.完全位于子数组[low,mid]中

2.横跨中点mid，有low<=i<=mid<=j<=high

3.完全位于子数组[mid,high]中

int search(int*data,int low,int mid,int high,int left,int right)//data为数组，low,mid,right三个边界将数组分为两部分，left,right为返回最大子数组的左右边界{int left_sum=0,sum=0,i;//sum为临时子数组之和for(i=mid;i>=low;i--)//i从mid开始向左遍历{sum=sum+data[i];//sum存放[i,mid]之和if(sum>left_sum)//将临时子数组之和与上一个最大子数组之和进行比较{left=i;//left存放最大子数组左边界，右边界暂定为midleft_sum=sum;//left_sum存放左侧最大子数组之和}}int right_sum=0;sum=0;for(i=mid;i<=high;i++)//i从mid开始向右遍历{sum=sum+data[i];//sum存放[mid,i]之和if(sum>right_sum){right_sum=sum;//right_sum存放最大子数组之和right=i;//right存放最大子数组右边界，左边界已确定为left}}return (left_sum + right_sum)//返回中间部分的最大子数组之和=左侧最大子数组之和+右侧最大子数组之和}int subarray(int*data,int low,int high,int*left,int*right){if(low==high)//针对该数组只有一个元素的情况{*left=low;*right=high;return data[low];//data[low]==data[high],返回任意一个即可}else{int mid=(low+high)/2;int*left_low=(int*)malloc(sizeof(int));//void*malloc(size_t size)分配所需的内存空间，并返回一个指向它的指针int*left_high=(int*)malloc(sizeof(int));int left_sum=subarray(data,low,mid,left_low,left_high);//计算左边最大子数组的和int*right_low=(int*)malloc(sizeof(int));int*right_high=(int*)malloc(sizeof(int));int right_sum=subarray(data,low,mid,right_low,right_high);//计算右边最大子数组的和int*cross_low=(int*)malloc(sizeof(int));int*cross_high=(int*)malloc(sizeof(int));int cross_sum=subarray(data,low,mid,cross_low,cross_high);//计算中间最大子数组的和if(left_sum>right_sum&&left_sum>cross_sum)//比较三个最大子数组之和，返回最终求出的最大子数组的和{*left=*left_low;*right=*left_high;return left_sum;}else{if(right_sum>left_sum&&right_sum>cross_sum){*left=*right_low;*right=*right_high;return right_sum;}else{*left=*cross_low;*right=*cross_high;return cross_sum;}}}}//递归寻找最大子数组

要点二：矩阵乘法的Strassen算法

对于矩阵乘法，设A,B,C为n*n方阵，则我们可以根据以下代码求解矩阵C

方法一：暴力求解方法

根据矩阵的性质，通过三个for循环，即可完成计算。其实，通过前面的分析，我们已经很明显的看出，两个具有相同维数的矩阵相乘，其复杂度为O（n^3）

#include<stdio.h>int main(){int n;scanf("%d",&n);int a[n][n],b[n][n],c[n][n]={0},i,j,k;//定义a,b,c三个矩阵for(i=0;i<n;i++){for(j=0;j<n;j++){scanf("%d",&a[i][j]);//给a矩阵赋值scanf("%d",&b[i][j]);//给b矩阵赋值}}for(i=0;i<n;i++){for(j=0;j<n;j++){for(k=0;k<n;k++)c[i][j]+=a[i][k]*b[k][j];//矩阵计算公式}}for(i=0;i<n;i++){for(j=0;j<n;j++)printf("%d",c[i][j]);//输出矩阵c}return 0;}

方法二：递归分治算法

根据分治策略，我们可以这样求解矩阵：假设存在三个矩阵A,B,C并且三个矩阵均为n*n矩阵，n为2的幂，则我们可以将矩阵n*n划分为4个n/2*n/2的子矩阵（其中n>=2，保证子矩阵规模为整数）

这里我采用和书上一样的定义，假设A,B,C均为2*2矩阵，则我们可以这么求解：

#include<stdio.h>int main(){int recursive(int a,int b);//调用定义的recursive函数int a[2][2],b[2][2],c[2][2],i,j;//规定了矩阵大小2*2for(i=0;i<2;i++){for(j=0;j<2;j++){scanf("%d",&a[i][j]);scanf("%d",&b[i][j]);}}c[1][1]=recursive(a[1][1],b[1][1])+recursive(a[1][2],b[2][1]);c[1][2]=recursive(a[1][1],b[1][2])+recursive(a[1][2],b[2][2]);c[2][1]=recursive(a[2][1],b[1][1])+recursive(a[2][2],b[2][1]);c[2][2]=recursive(a[2][1],b[1][2])+recursive(a[2][2],b[2][2]);for(i=0;i<2;i++){for(j=0;j<2;j++)printf("%d",c[i][j]);//输出矩阵C}}int recursive(int a,int b)//定义函数recursive,作用为求出两数的乘积{int c;c=a*b;return c;}

看得出来，求解的步骤依旧相当繁琐

方法三：Strassen方法

核心思想：令递归树不那么茂盛，即只递归7次而不是8次

假设存在三个矩阵A,B,C，均为n*n矩阵，那么Stranssen求解步骤如下：

1.将矩阵A,B分解为n/2*n/2的子矩阵

2.创建10个n/2*n/2的矩阵，用于保存步骤一中两个子矩阵的和或差

3.根据步骤一和步骤二，递归的计算7个矩阵积P1~P7

4.通过Pi矩阵的不同组合进行加减运算，计算出矩阵C的子矩阵

下面给出一道例题，先来考察一个问题：请用三次实数乘法计算复数a+bi和c+di相乘。

由于：

a×(c+d)=ac+ad=s1 ；

b×(c-d)=bc-bd=s2 ；

d×(a+b)=ad+bd=s3 ；

故有实部：s1 -s3 =ac-bd,

虚部：s2+ s3 =ad+bc。

这样，四次的乘法就变成三次乘法。

现在，我们来看一下Strassen算法的原理。

仍然把每个矩阵分割为4份，然后创建如下10个中间矩阵：

S1 = B12 - B22

S2 = A11 + A12

S3 = A21 + A22

S4 = B21 - B11

S5 = A11 + A22

S6 = B11 + B22

S7 = A12 - A22

S8 = B21 + B22

S9 = A11 - A21

S10 = B11 + B12

接着，计算7次矩阵乘法：

P1 = A11 • S1

P2 = S2 • B22

P3 = S3 • B11

P4 = A22 • S4

P5 = S5 • S6

P6 = S7 • S8

P7 = S9 • S10

最后，根据这7个结果就可以计算出C矩阵：

C11 = P5 + P4 - P2 + P6

C12 = P1 + P2

C21 = P3 + P4

C22 = P5 + P1 - P3 - P7

我们可以把P矩阵和S矩阵展开，并带入最后的式子计算，会发现恰好是公式3中的四个式子。这是个非常神奇的操作，我现在也没想明白究竟是怎么得出的。

下面我将用代码来解释Strassen算法

int Strassen(int **A, int **B, int **Result, int Size){if (Size == 1){//直接计算C11Result[0][0] = A[0][0] * B[0][0];return 0;}int NewSize = Size / 2;/*分块矩阵*/int **A11, **A12, **A21, **A22;int **B11, **B12, **B21, **B22;int **C11, **C12, **C21, **C22;int **P1, **P2, **P3, **P4, **P5, **P6, **P7;/*存放数组A、B（i、j）的临时变量*/int **AResult, **BResult;A11 = new int*[NewSize];A12 = new int*[NewSize];A21 = new int*[NewSize];A22 = new int*[NewSize];B11 = new int*[NewSize];B12 = new int*[NewSize];B21 = new int*[NewSize];B22 = new int*[NewSize];C11 = new int*[NewSize];C12 = new int*[NewSize];C21 = new int*[NewSize];C22 = new int*[NewSize];P1 = new int*[NewSize];P2 = new int*[NewSize];P3 = new int*[NewSize];P4 = new int*[NewSize];P5 = new int*[NewSize];P6 = new int*[NewSize];P7 = new int*[NewSize];AResult = new int*[NewSize];BResult = new int*[NewSize];for (int i = 0; i < NewSize; i++){A11[i] = new int[NewSize];A12[i] = new int[NewSize];A21[i] = new int[NewSize];A22[i] = new int[NewSize];B11[i] = new int[NewSize];B12[i] = new int[NewSize];B21[i] = new int[NewSize];B22[i] = new int[NewSize];C11[i] = new int[NewSize];C12[i] = new int[NewSize];C21[i] = new int[NewSize];C22[i] = new int[NewSize];P1[i] = new int[NewSize];P2[i] = new int[NewSize];P3[i] = new int[NewSize];P4[i] = new int[NewSize];P5[i] = new int[NewSize];P6[i] = new int[NewSize];P7[i] = new int[NewSize];AResult[i] = new int[NewSize];BResult[i] = new int[NewSize];}//对分块矩阵赋值for (int i = 0; i < NewSize; i++){for (int j = 0; j < NewSize; j++){A11[i][j] = A[i][j];A12[i][j] = A[i][j + NewSize];A21[i][j] = A[i + NewSize][j];A22[i][j] = A[i + NewSize][j + NewSize];B11[i][j] = B[i][j];B12[i][j] = B[i][j + NewSize];B21[i][j] = B[i + NewSize][j];B22[i][j] = B[i + NewSize][j + NewSize];}}//计算P1 = A11*(B12-B22)Sub(B12, B22, BResult, NewSize);Strassen(A11, BResult, P1, NewSize);//计算P2 = (A11+A12)*B22Add(A11, A12, AResult, NewSize);Strassen(AResult, B22, P2, NewSize);//计算P3 = (A21+A22)*B11Add(A21, A22, AResult, NewSize);Strassen(AResult, B11, P3, NewSize);//计算P4 = A22*(B21-B11)Sub(B21, B11, BResult, NewSize);Strassen(A22, BResult, P4, NewSize);//计算P5 = (A11+A22)*(B11+B22)Add(A11, A22, AResult, NewSize);Add(B11, B22, BResult, NewSize);Strassen(AResult, BResult, P5, NewSize);//计算P6 = (A12-A22)*(B21+B22)Sub(A12, A22, AResult, NewSize);Add(B21, B22, BResult, NewSize);Strassen(AResult, BResult, P6, NewSize);//计算P7 = (A11-A21)*(B11+B12)Sub(A11, A21, AResult, NewSize);Add(B11, B12, BResult, NewSize);Strassen(AResult, BResult, P7, NewSize);//计算C11，C12，C21，C22//C11 = P5 + P4 - P2 + P6;Add(P5, P4, AResult, NewSize);Sub(AResult, P2, BResult, NewSize);Add(BResult, P6, C11, NewSize);//C12=P1+P2Add(P1, P2, C12, NewSize);//C21=P3+P4Add(P3, P4, C21, NewSize);//C22=P5+P1-P3-P7Add(P5, P1, C22, NewSize);Sub(C22, P3, C22, NewSize);Sub(C22, P7, C22, NewSize);//合并C11，C12，C21，C22for (int i = 0; i < NewSize; i++){for (int j = 0; j < NewSize; j++){Result[i][j] = C11[i][j];Result[i][j + NewSize] = C12[i][j];Result[i + NewSize][j] = C21[i][j];Result[i + NewSize][j + NewSize] = C22[i][j];}}//删除数组，回收资源for (int i = 0; i < NewSize; i++){delete[] A11[i]; delete[] A12[i]; delete[] A21[i]; delete[] A22[i];delete[] B11[i]; delete[] B12[i]; delete[] B21[i]; delete[] B22[i];delete[] C11[i]; delete[] C12[i]; delete[] C21[i]; delete[] C22[i];delete[] P1[i]; delete[] P2[i]; delete[] P3[i]; delete[] P4[i]; delete[] P5[i]; delete[] P6[i]; delete[] P7[i];delete[] AResult[i]; delete[] BResult[i];}delete[] A11; delete[] A12; delete[] A21; delete[] A22;delete[] B11; delete[] B12; delete[] B21; delete[] B22;delete[] C11; delete[] C12; delete[] C21; delete[] C22;delete[] P1; delete[] P2; delete[] P3; delete[] P4; delete[] P5; delete[] P6; delete[] P7;delete[] AResult; delete[] BResult;return 0;}//矩阵相加void Add(int **A, int **B, int **Q, int Size){for (int i = 0; i < Size; i++){for (int j = 0; j < Size; j++){Q[i][j] = A[i][j] + B[i][j];}}}//矩阵相减void Sub(int**A, int**B, int **Q, int Size){for (int i = 0; i < Size; i++){for (int j = 0; j < Size; j++){Q[i][j] = A[i][j] - B[i][j];}}}

要点三：代入法

代入法基本步骤：

1.猜测解的形式

2.用数学归纳法求解出解中的常数，并证明解是正确的

代入法需要我们做出好的猜测，这需要靠经验和方法，灵活采用方法，将陌生的递归式转化为你熟悉的递归式也是一个非常好的方法。

要点四：递归树方法

递归树是设计好的猜测的简单且直接的方法。利用递归树生成好的猜测，再结合代入法来验证猜测是否正确。

要点五：主方法

主方法的表现形式：

T [n] = aT[n/b] + f (n)（直接记为T [n] = aT[n/b] + O (N^d)）

其中 a >= 1 and b > 1 是常量，其表示的意义是n表示问题的规模，a表示递归的次数也就是生成的子问题数，b表示每次递归是原来的1/b之一个规模，f（n）表示分解和合并所要花费的时间之和。

解法：