第二章递归与分治策略

悠悠 2022-08-01 00:19 143阅读 0赞

**学习要点**  
理解递归的概念  
掌握设计有效算法的分治策略  
通过下面的范例学习分治策略设计技巧  
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。  
如果原问题可分割成 k 个子问题，1 < k <= n,且这些字问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。

# 2.1 递归的概念 #

直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。  
比如阶乘求解，Fibonacci数列。  
双阶乘函数：当一个函数及它的一个变量是由函数自身定义的时，称这个函数是双递归函数。  
**例题：Ackerman函数**  
A(n,m) 有两个独立的整形变量 m >= 0和 n >= 0,其定义如下：  
A(1,0) = 2  
A(0,m) = 1 m >= 0  
A(n,0) = n+2 n >= 2  
A(n,m) = A(A(n-1,m),m-1) n,m >= 1

#include <stdio.h>
    
    int Ackerman(int n, int m);
    int main()
    {
    	int n = 0;
    	int m = 0;
    
    	while (scanf("%d %d",&n,&m) != EOF)
    	{
    		printf("%d\n",Ackerman(n,m));
    	}
    	return 0;
    }
    
    int Ackerman(int n, int m)
    {
    	if (n == 1 && m == 0)
    		return 2;
    	if (n == 0 && m >= 0)
    		return 1;
    	if (n >= 2 && m == 0)
    		return n+2;
    	if (n >= 1 && m >= 1)
    		return Ackerman(Ackerman(n-1,m),m-1);
    
    	return -1;
    }

**例题：排列问题**  
设 R = \{r1,r2,…,rn\}是要进行排列的 n个元素，Ri = R – \{ri\}.集合 X中元素的全排列记为 Perm(X). (ri)Perm(X)表示在全排列 Perm(X)的每一个排列前加上前缀 ri得到的排列。R的全排列可归纳定义如下：  
当 n = 1 时，Perm(R) = (r),其中 r是集合 R中唯一的元素；  
当 n > 1 时， Perm(R) 由 (r1)Perm(R-r1),…(ri)Perm(R-ri),…,(rn)Perm(R-rn)构成。  
依次递归定义，可以设计产生 Perm(R)的递归算法如下：

<strong>#include <stdio.h>
    
    int array[] = {1,2,3,4,5};
    
    void swap(int *a, int *b);
    void perm(int cur, int size);
    int main()
    {
    	perm(0,5);
    	return 0;
    }
    
    void perm(int cur,int size)
    {
    	int i = 0;
    
    	// 产生 list[cur:size]的所有排列
    	if (cur == size)
    	{
    		for (i = 0; i < size; i++)
    		{
    			printf("%d ",array[i]);
    		}
    
    		printf("\n");
    	}
    	else
    	{
    		// 还有多个元素待排列，递归产生排列
    		for (i = cur; i < size; i++)
    		{
    			swap(&(array[i]),&(array[cur]));
    			perm(cur+1,size);
    			swap(&(array[cur]),&(array[i]));
    		}
    	}
    }
    
    void swap(int *a, int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    </strong><strong>
    </strong>

算法 Perm(cur,size)递归地产生所有前缀是 list\[0,cur-1\],且后缀是 list\[cur,size\]的全排列。函数调用 Perm\[0,n-1\] 则产生 list\[0,n-1\]的全排列。  
 在一般情况下，k < m.算法将 list\[k:m\]中的每一个元素分别与 list\[k\]中的元素交换。然后递归地计算 list\[k+1,m\]的全排列，并将计算结果作为 list\[0,k\]的后缀。  
  
**例题：整数划分问题**  
将正整数 n 表示成一系列正整数之和：  
 n = n1+n2+,…,+nk (其中，n1 >= n2 >= …>= nk >= 1, k >= 1)  
正整数 n 的这种表示称为正整数 n的划分。正整数 n的不同的划分个数称为正整数 n的划分数，记作 p(n)。  
例如，正整数 6 有如下 11 种不同的划分，所以 p(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.  
在正整数 n 的所有不同的划分中，将最大加数 n1不大于 m的划分个数记作 q(n,m)。可以建立 q(n,m)的递归关系。  
(1) q(n,1) = 1, n >= 1  
(2) q(n,m) = q(n,n), m >= n;  
(3) q(n,n) = q(n,n-1)+1  
(4) q(n,m) = q(n-m,m)+q(n,m-1), n > m  
正整数 n 的最大加数 n1 不大于 m的划分由 n1 = m的划分和 n1 <= m-1的划分组成。

#include <stdio.h>
    
    int q(int n,int m);
    
    int main()
    {
    	int n = 0;
    	scanf("%d",&n);
    
    	// 划分数字 n 最大加数 m 的最大划分数
    	printf("%d",q(n,n));
    	return 0;
    }
    
    int q(int n,int m)
    {
    	if (n < 1 || m < 1)
    		return 0;
    	if (n == 1)
    		return 1;
    	if (n <= m)
    		return q(n,n-1)+1;
    	if (n > m)
    		return q(n,m-1)+q(n-m,m);
    
    	return -1;
    }

# 2.2 分治法的基本思想 #

分治法的基本思想是讲一个规模为 n的问题分解为 k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。  
**1.互相独立**  
**2.与原问题相同**  
它的一般的算法设计如下：

divide-and-conquer(P)
    
    {
    
           if (|P| <= n0) adhoc(P)
    
           divide P into smaller subinestances P1,P2,…,Pk;
    
           
    
           for (i = 1; i <= k; i++)
    
    {
    
           yi = divide-and-conquer(Pi);
    
    }
    
     
    
    Return merge(y1,y2,…,yk);
    
    }

其中，|P|表示问题P的规模，n0为一阈值，表示当问题P的规模不超过n0时，问题已容易解出，不必再继续分解。adhoc(P)是该分治中的基本子算法，用于直接解小规模的问题P。当P的规模不超过 n0时，直接用算法adhoc(P)求解。算法merge(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1,P2,…,Pk的解 y1,y2,…,yk 合并为 P的解。  
如果用 T(n) 表示该分治法解规模为 |P| = n 的问题所需的计算时间，则有  
 O(1) n = n0  
T(n) =  
 kT(n/m) + f(n) n > n0  
分治法适用条件：  
(1) 该问题的规模缩小到一定程度就可以很容易地解决；  
(2) 该问题可以分割成若干个规模较小的相同问题，即该问题具有最优子结构性质；  
(3) 利用该问题分解出的子问题可以合并为该问题的解；  
(4) 该问题所分解出来的各个子问题是互相独立的，即子问题之间不包含公共子问题。

# 2.3 二分搜索技术 #

给定已经排好序的 n 个元素 a\[0:n-1\]，现要在这 n个元素中找出一特定元素 x.  
方法1：顺序搜索法，最坏时候时间复杂度 O(n);  
方法2：二分搜索法，最坏时候时间复杂度 O(logn) (log以2为底 n的对数);

#include <stdio.h>
    
    const int array[] = {1,5,12,23,43,51,57,68,70,82};
    
    //int BinarySearch(int num,int size);
    int BinarySearch(int num,int left,int right);
    int main()
    {
    	int num;
    	scanf("%d",&num);
    	//	printf("%d\n",BinarySearch(num,10));
    	printf("%d\n",BinarySearch(num,0,9));
    	return 0;
    }
    
    int BinarySearch(int num,int left,int right)
    {
    	int result = 0;
    	int middle = (left+right)/2;
    
    	if (num == array[middle])
    	{
    		result = middle;
    	}
    	else if (num > array[middle])
    	{
    		result = BinarySearch(num,middle+1,right);
    	}
    	else
    	{
    		result = BinarySearch(num,left,middle-1);
    	}
    
    	return result;
    }
    
    /*int BinarySearch(int num,int size)
    {
    	int left = 0;
    	int right = size-1;
    
    	while (left <= right)
    	{
    		int middle = (left+right)/2;
    
    		if (array[middle] == num)
    		{
    			return middle;
    		}
    		else if (array[middle] > num)
    		{
    			right = middle-1;
    		}
    		else
    		{
    			left = middle+1;
    		}
    	}
    
    	return 0;
    }*/