递归与分治策略

简介: 递归与分治策略

🥇 前言


对于计算机科学来说,算法的概念至关重要。例如,在一个大型软件系统的开发中,设计出有效的算法将起决定性的作用。通俗地讲,算法是指解决问题的一种方法或一个过程。

算法的种类是多种多样的,算法的代码也很多,我们最主要的是要学习算法的思想,才能更好地应用和拓展。


🥈递归的概念


🥉基本概念:

直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。

在计算机和编程的学习过程中,递归技术是十分有用的。使用递归技术往往使函数的定义和算法描述简捷且易于理解。


🥉算法实例:

【例1】阶乘函数。阶乘函数可递归地定义为

image.png

解析: 递归式的第一式给出了这个函数的初始值,是非递归地定义的。每个递归函数都必须有非递归定义的初始值,否则递归函数无法计算。本例题主要思想就是如果n的阶乘无法计算出来,就算n-1的阶乘,n-1的阶乘无法计算就一直往前推,直到n=0的阶乘为1,直到n=0的阶乘就知道n=1的阶乘,再往回推导,最终求出n的阶乘。


代码实现:

int factorial(int n)
{
if(n==0)
  return 1;
else
  return n*factorial(n-1);
}


【例2】无穷数列1,1,2,3,5,8,13,21,34,55,…称为Fibonacci数列。它可以递归地定义为

image.png

解析: 这是一个递归关系式,当n>1时,这个数列的第n项的值是它前面两项之和。它用两个较小的自变量的函数值来定义一个较大自变量的函数值,所以需要两个初始值F(0)和F(1)。

代码实现:

int fibonacci(int n)
{
if(n>1)
  return 1;
else
  return fibonacci(n-1)+fibonacci(n-2);
}


【例3】排列问题。设R{r1,r2,…rn}是要进行排列的n个元素,Ri=R-{ri}。集合X中元素的全排列记为Perm(X)。(ri)Perm(X)表示在全排列Perm(X)的每个排列前加上前缀ri得到的排列。R的全排列可归纳定义如下:

当n=1时,Perm®={r},其中r是集合R中唯一的元素;

当n>1时,Perm®由(r1)Perm(R1),(r2)Perm(R2),…(rn)Perm(Rn)构成

template <classType>void  Perm (Type list[],int k,int m){   //产生list[k:m]的所有排列
if(k==m){             //只剩下1个元素
  for(int i=0;i<m;i++)cout<<list[i];cout<<endl;}else{for(inti=k;i<=m;i++){              //  还有多个元素待排列,递归产生排列  Swap(list[k],list[i]);
  perm(list,k+1,m);
  Swap(list[k],list[i]);           //回初始位置
  }
  }
}
template<classType>inline void Swap(Type & a,Type & b){
Type temp =a;
a=b;
b=temp;
}


🥈分治法的基本思想


分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。

递归地解这些子问题,然后将各子问题的解合并得到原问题的解。

它的一般算法设计模式如下:

divide-and-conquer(P){
if(|P|<=n0)//|P|是指问题P的规模adhoc(P);dividePintosmallersubinstancesP1,P2,···,Pk;for(i=1;i<=k;i++)yi=divide-and-conquer(Pi);  //递归解决
return merge(y1,y2,···yk);
}


注意点:1.分治法与递归紧密相联

2.因子问题需分别求解,所以子问题应相互独立。


目录
相关文章
|
算法 C++
剑指offer(C++)-JZ41:数据流中的中位数(算法-排序)
剑指offer(C++)-JZ41:数据流中的中位数(算法-排序)
174 0
剑指offer(C++)-JZ41:数据流中的中位数(算法-排序)
|
8月前
|
中间件 关系型数据库 数据库
docker快速部署OS web中间件 数据库 编程应用
通过Docker,可以轻松地部署操作系统、Web中间件、数据库和编程应用。本文详细介绍了使用Docker部署这些组件的基本步骤和命令,展示了如何通过Docker Compose编排多容器应用。希望本文能帮助开发者更高效地使用Docker进行应用部署和管理。
224 19
org.activiti.engine.ActivitiException: Couldn't deserialize object in variable 'application'
org.activiti.engine.ActivitiException: Couldn't deserialize object in variable 'application'
|
11月前
|
运维 监控 Serverless
揭秘云计算中的Serverless架构:优势、挑战与实践
揭秘云计算中的Serverless架构:优势、挑战与实践
363 0
|
Prometheus 监控 Cloud Native
基于prometheus的微服务指标监控
基于prometheus的微服务指标监控
|
传感器 存储 缓存
STM32--MPU6050与I2C外设
STM32--MPU6050与I2C外设
411 1
|
设计模式 C#
36.c#:如何设置MDL窗口
36.c#:如何设置MDL窗口
128 1
|
算法 物联网
CTP协议的组成原理与具体实现(原理篇,含组件解析)_物联网竞赛挑战赛
CTP协议的组成原理与具体实现(原理篇,含组件解析)_物联网竞赛挑战赛
923 0
|
数据挖掘 数据格式
R语言- ComplexHeatmap 绘制复杂热图示例
ComplexHeatmap是R语言中用于绘制复杂热图的一个重要包。它提供了一种灵活、高效、易于定制的方法来绘制热图,并支持多种数据类型和数据格式,支持包括多种热图类型,包括基本热图、聚类热图、分组热图、矩阵热图等。用户可以根据自己的需求选择不同的热图类型,并进行灵活的定制。在生物信息学、医学、生态学等领域得到广泛应用。 本文将通过一个复杂热图的创建示例分享 ComplexHeatmap的语法规则。
1248 0
|
PHP
关于phpstorm php内置函数不提示的问题
关于phpstorm php内置函数不提示的问题
386 0
关于phpstorm php内置函数不提示的问题