236-用分治策略解决问题

短命女 2022-11-12 01:40 389阅读 0赞

## 分治策略 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
**问题不变，规模变小！**  
**递归方法有直接递归和间接递归，但是我们最好去编写直接递归（我们自己调用自己。**

## 求解n的阶乘 ##

![在这里插入图片描述][20210321195259964.png_pic_center]  
**阶乘可递归地定义为：**  
![在这里插入图片描述][20210321195316664.png_pic_center]  
**两种方法对比：**  
**下面是循环的方法：**

int fun(int n)
    {
        
    	int sum = 1;
    	for (int i = 1; i <= n; ++i)
    	{
        
    		sum = sum * i;
    	}
    	return sum;
    }// 时间复杂度是O(n) , 空间复杂度是S(1)

**下面是递归的方法：**

int fac(int n)
    {
        
    	if (n<=1)
    		return 1;
    	else 
    		return fac(n - 1) * n;
    }
    //时间复杂度是O(n) ，空间复杂度是S(n)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][2021032120135239.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][2021032120140946.png_pic_center]

**看下面这个代码，能不能一直递归下去？**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]  
**答案：** 是不能的！没有“死递归”，因为我们在递归的过程中不断地申请空间，栈帧的大小在Windows下是1M，在Linux是10M，总有时候会把内存耗尽！

**还有一个问题 ，我们在计算阶乘的时候，很容易就突破整型的范围，该怎么办呢？**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][20210321200311284.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]  
**怎么解决？？？**

int main()
    {
        
    	for (int i = 2; i <= 20; ++i)
    	{
        
    		cout << i << "=> " << fun(i) << endl;
    	}
    	return 0;
    }

**先计算出int类型最大承受的阶乘数**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]  
**我们看到 int类型可以承受的最大阶乘数是15**  
因为显示16的阶乘变小了。  
我们的整型可以看作一个圆环，前半环是整型的范围，超过这个界限点就是负的值，16的阶乘打印比较小的正数，估计是多绕了一圈，变成正的。  
**我们用计算器，精准出正确的整型可以承受的最大阶乘数**  
![在这里插入图片描述][20210321201111863.png_pic_center]

![在这里插入图片描述][20210321201018564.png_pic_center]  
![在这里插入图片描述][20210321201023390.png_pic_center]  
最大阶乘数是12。

**解决方案如下：**  
在递归的过程中，直接判断n的值就可以！！！

## 斐波那契数列 ##

![在这里插入图片描述][20210321201503321.png_pic_center]**非递归方法如下：**

int fun(int n)
    {
        
    	int a = 1, b = 1, c = 1;
    	for (int i = 3; i <= n; ++i)
    	{
        
    		c = a + b;
    		b = a;
    		a = c;
    	}
    	return c;
    }  // 时间复杂度是O(n)  空间复杂度是S(1)

**递归方法如下：**  
![在这里插入图片描述][20210321201651221.png_pic_center]

int fib(int n)
    {
        
    	if (n <= 2)
    		return 1;
    	else
    		return fib(n - 1) + fib(n - 2);
    }//时间复杂度是O(2^n) 空间复杂度是S(n)

**斐波那契数列递归方法的时间复杂度和空间复杂度的计算图解如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]

深度达到n，开辟的n个空间，空间复杂度是O(n)。  
时间复杂度是O(n^2)，需要计算n ^ 2个元素。

**由于这个函数在递归的时候，时间复杂度过大，能不能把这个递归程序改写一下，使得时间复杂度变为O(n)？？？**

解决方案如下： 我们要消除重复求解的过程！！！

int fib1(int n, int a, int b)
    {
        
    	if (n <= 2) return a;
    	else
    		return fib(n - 1, a + b, a);
    }
    int fib(int n)
    {
        
    	int a = 1, b = 1;
    	return fib1(n, a, b);
    }

**对比一下，我们把c变量消除了！**  
在递归方法中，两个a是不一样的。不需要中间的c作为过渡。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]  
![在这里插入图片描述][20210321202700528.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]  
![在这里插入图片描述][20210321202710332.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/890aede5fbc8476c9537e923c3d5bdba.png
[20210321195259964.png_pic_center]: https://img-blog.csdnimg.cn/20210321195259964.png#pic_center
[20210321195316664.png_pic_center]: https://img-blog.csdnimg.cn/20210321195316664.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210321195446505.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[2021032120135239.png_pic_center]: https://img-blog.csdnimg.cn/2021032120135239.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210321201356928.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/2021032120140444.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[2021032120140946.png_pic_center]: https://img-blog.csdnimg.cn/2021032120140946.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20210321195822625.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20210321200306691.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[20210321200311284.png_pic_center]: https://img-blog.csdnimg.cn/20210321200311284.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20210321200344614.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20210321200538535.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[20210321201111863.png_pic_center]: https://img-blog.csdnimg.cn/20210321201111863.png#pic_center
[20210321201018564.png_pic_center]: https://img-blog.csdnimg.cn/20210321201018564.png#pic_center
[20210321201023390.png_pic_center]: https://img-blog.csdnimg.cn/20210321201023390.png#pic_center
[20210321201503321.png_pic_center]: https://img-blog.csdnimg.cn/20210321201503321.png#pic_center
[20210321201651221.png_pic_center]: https://img-blog.csdnimg.cn/20210321201651221.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20210321201838983.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20210321202307130.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20210321202649545.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20210321202655800.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[20210321202700528.png_pic_center]: https://img-blog.csdnimg.cn/20210321202700528.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/20210321202705321.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[20210321202710332.png_pic_center]: https://img-blog.csdnimg.cn/20210321202710332.png#pic_center