穷举算法、递推算法、迭代算法(辗转法)、递归算法

# 穷举(枚举、暴力、强力)算法


## 基本思想

在可能的解空间中穷举出每一种可能的解,并对每一个可能解进行判断,从中得到问题的答案。穷举算法效率并不高,但是适应于一些没有明显规律可循的场合。

使用穷举法思想解决实际问题,最关键的步骤是划定问题的解空间,并在该解空间中一一枚举每一个可能的解。

这里有两点需要注意:

  1. 解空间的划定必须保证覆盖问题的全部解
  2. 是解空间集合及问题的解集一定是离散的集合,也就是说集合中的元素是可列的、有限的。

穷举法用时间上的牺牲换来了解的全面性保证,因此穷举法的优势在于确保得到问题的全部解,而瓶颈在于运算效率十分低下。但是穷举法算法思想简单,易于实现,在解决一些规模不是很大的问题,使用穷举法不失为一种很好地选择,而无须太在意是够还有更快的算法。

## 经典运用:

《孙子算经》【鸡兔同笼问题】
今有鸡兔同笼,上有三十五头,下有九十四足,问鸡兔各几何?

# 递推算法


聪明一点的递推算法思想

## 基本思想

递推(recurrence)算法是一种简单的算法,即通过已知条件,利用特定关系得出中间推论,直至得到结果的算法。从已知到未知,从小到大,这种从“起点”重复相同的方法直至到达一定“边界”,犹如单向运动,用 循环可以实现。

  • 顺推法:从已知条件出发,逐步推算出要解决问题的方法
  • 逆推法:从已知结果出发,用迭代表达式逐步推算出问题开始的条件。

执行过程如下:

  1. 根据已知结果和关系,求解中间结果。
  2. 判定是否达到要求,如果没有达到,则继续根据已知结果和关系求解中间结果。如果满足要求,则表示寻找到一个正确的答案。

【注意】递推算法需要用户知道答案和问题之间的逻辑关系。在许多数学问题中,都有明确的计算公式可以遵循,因此可以采用递推算法来实现。

典型代表fibonacci数列递推求法(后一项等于前两项之和)f(n) = f(n-1) + f(n-2)

## 经典运用:

算盘书、斐波那契数列(兔子繁殖)(顺推法)、银行存款(逆推法)

# 迭代算法(辗转法)


## 基本思想

迭代:在计算过程中,不断用变量的旧值 递推出变量的新值。是重复反馈过程的活动,其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”,而每一次迭代得到的结果会作为下一次迭代的初始值

  • 解决问题时总是重复利用一段程序(可以是几行代码,也可以是一个函数)
  • 一直在更新这个变量值,迭代的含义
  • 从一个 初始估计出发寻找 一系列近似解来解决问题的数学过程

可分为:

  • 精确迭代
  • 近似迭代:二分法和牛顿迭代法

## 基本步骤

用迭代算法解决问题时,需要做好3个方面的工作

  1. 确定迭代变量:直接或间接地不断由旧值递推出新值的变量
  2. 建立迭代关系式:新值与旧值的公式或关系。(解决迭代问题的关系)
  3. 对迭代过程进行控制:确定迭代次数和迭代结束条件
    • 所需的迭代次数是个确定值,可以计算出来:可以构建一个固定次数的循环来实现对迭代过程的控制;
    • 所需的迭代次数无法确定:需要进一步分析出用来结束迭代过程的条件。

## 经典运用:

求平方根问题

# 递归算法


充分利用自己的递归算法思想

## 基本思想

  • 递归函数:一个函数在它的函数体内调用它自身的函数调用方式,这种函数也称为递归函数。在递归函数中,主调函数又是被调函数。执行递归函数将反复调用其自身,每调用一次就进入新的一层。
  • 递归函数的两个要素:边界条件、递归方程
  • 递归算法:一种直接或间接地调用原算法本身的一种算法。往往可以简化代码编写,提高程序的可读性。但是,不合适的递归会导致程序的执行效率变低。
    • 递归过程一般通过函数或子过程实现;
    • 递归算法在函数或子过程的内部,直接或间接调用自己的算法
    • 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题,然后再递归调用函数或过程来表示问题的解

递归分为两个阶段:

  1. 递推:把复杂的问题的求解推到比原问题简单一些的问题的求解;
  2. 回归:当获得最简单的情况后, 逐步返回, 依次得到复杂的解.

函数的递归调用分两种情况:直接递归和间接递归。

  • 直接递归:即在函数中调用函数本身。
  • 间接递归:即间接地调用一个函数,如出如func_a调 用 func_b, func_b 又调用func_a。间接递归用得不多。
优点:

代码简洁、可读性好(这一点,对于初学者可能会反对)。实际上递归的代码更清晰,但是从学习的角度要理解递归真正发生的什么,是如何调用的,调用层次和路线,调用堆栈中保存了什么,可能是不容易。但是不可否认递归的代码更简洁。

缺点:

由于递归需要系统堆栈,所以空间消耗要比非递归代码要大很多。而且,如果递归深度太大,可能会造成栈溢出

注意:
  • 必须有一个明确的递归结束条件(递归出口)
  • 如果递归次数过多,容易造成栈溢出。

## 经典运用:

汉诺塔问题、阶乘问题

# 迭代与递归的区别、联系


从理论上说,所有的递归函数都可以转换为迭代函数,反之亦然,然而代价通常都是比较高的。

但从算法结构来说,递归声明的结构并不总能够转换为迭代结构,原因在于结构的引申本身属于递归的概念,用迭代的方法在设计初期根本无法实现,这就像动多态的东西并不总是可以用静多态的方法实现一样。

这也是为什么在结构设计时,通常采用递归的方式而不是采用迭代的方式的原因,一个极典型的例子类似于链表,使用递归定义及其简单,但对于内存定义(数组方式),其定义及调用处理说明就变得很晦涩,尤其是在遇到环链、图、网格等问题时,使用迭代方式从描述到实现上都变得不现实。 因而可以从实际上说,所有的迭代可以转换为递归,但递归不一定可以转换为迭代。

采用递归算法需要的前提条件是,当且仅当一个存在预期的收敛(有确定的(或有限的)极限)时,才可采用递归算法,否则,就不能使用递归算法。

递归中一定有迭代、递归不一定能转为迭代举例 —— 链表定义
ElemSN* CreatLink3(int data[], int n) //递归法创建链表
{
    ElemSN *p = NULL;
    if(n==0) return NULL;
    p = (ElemSN *)malloc(sizeof(ElemSN));
    p->data = data[n-1];
    p->next = CreatLink3(data, n-1);
    return P;
}

递归中一定有迭代(递归函数的传入参数每次都会被递归函数处理,并赋予新值)。比如这个递归,虽然不能转换成迭代结构,但其中仍然有迭代,迭代变量为n,每次在迭代过程中被处理,其结果会作为下次迭代的初始值

## 循环

循环是程序控制结构,不是算法,不要混为一谈。
迭代与循环:迭代中,一般是用循环结构来完成迭代次数的计算。
递归与循环:一切递归问题都可以转化为循环求解。不过有些问题中,递归转换为循环实现,需要自己维护堆栈,比如汉诺塔问题

### 递归算法转为循环求解

递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题),递归算法是一种自然且合乎逻辑的解决问题的方式,但是递归算法的执行效率通常比较差。因此,在求解某些问题时,常采用递归算法来分析问题,用非递归算法来求解问题;另外,有些程序设计语言不支持递归,这就需要把递归算法转换为非递归算法。

将递归算法转换为非递归算法有两种情况:

  • 一种是简单递归问题,可以直接求值,不需要回溯。使用一些变量保存中间结果,称为直接转换法;比如尾递归(最后一句话进行递归)、单向递归(函数中只有一个递归调用地方)
  • 另一种是复杂递归问题,不能直接求值,需要回溯。需要使用栈保存中间结果加以实现,称为间接转换法

使用非递归方式实现递归问题的算法程序,不仅可以节省存储空间,而且可以极大地提高算法程序的执行效率。下面分别讨论这两种方法。

1. 直接转换法

直接转换法通常用来消除 尾递归单向递归,将递归结构用循环结构来替代。
尾递归是指在递归算法中,递归调用语句只有一个,而且是处在算法的最后。例如求阶乘的递归算法:

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

当递归调用返回时,是返回到上一层递归调用的下一条语句,而这个返回位置正好是算法的结束处,所以,不必利用栈来保存返回信息。对于尾递归形式的递归算法,可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法:

long fact(int n)
{
  int s=0;
  for(int i=1; i<=n;i++)
  s=s*i; //用s保存中间结果
  return s;
}

单向递归是指递归算法中虽然有多处递归调用语句,但各递归调用语句的参数之间没有关系,并且这些递归调用语句都处在递归算法的最后。显然,尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下:

int f(int n)
{
  if(n == 1 || n ==0) return 1;
  else return f(n-1)+f(n-2);
}

对于单向递归,可以设置一些变量保存中间结构,将递归结构用循环结构来替代。例如求斐波那契数列的算法中用s1和s2保存中间的计算结果,非递归函数如下:

int f(int n)
{
  int i, s;
  int s1=1, s2=1;
  for(i=3; i<=n; ++i){
      s=s1+s2;
      s2=s1;// 保存f(n-2)的值
      s1=s;//保存f(n-1)的值
  }
  return s;
}
2. 间接转换法

该方法使用栈保存中间结果,一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下:

将初始状态s0进栈
while(栈不为空){
  退栈,将栈顶元素赋给s;
  if(s是要找的结果) 返回;
  else{
     寻找到s的相关状态s1;
     将s1进栈
  }
}

间接转换法在数据结构中有较多实例,如二叉树遍历算法的非递归实现(参考数据结构中树的递归、非递归(迭代)遍历)、图的深度优先遍历算法的非递归实现等等。

尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。编译器会自动把尾递归优化为循环

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,552评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,666评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,519评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,180评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,205评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,344评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,781评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,449评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,635评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,467评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,515评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,217评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,775评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,851评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,084评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,637评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,204评论 2 341

推荐阅读更多精彩内容

  • 递归:如何用三行代码找到“最终推荐人” 推荐注册返佣金的这个功能我想你应该不陌生吧?现在很多 App 都有这个功能...
    GhostintheCode阅读 1,239评论 0 6
  • 迭代法 迭代法也被称为辗转法,是一种不断用变量的旧值递推新值的过程,在解决问题时总是重复利用一种方法。与迭代法相对...
    GoFuncChan阅读 8,203评论 0 2
  • 栈与递归 栈还有一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列的调用语句间接的调用自己的函数...
    Mr_Bluyee阅读 3,089评论 0 1
  • 计算机科学的新学生通常难以理解递归程序设计的概念。递归思想之所以困难,原因在于它非常像是循环推理(circular...
    启明_b56f阅读 7,302评论 0 20
  • 稍做休息 文/我心我愿秀 你需要的只是休息,而不是放弃。 我需要调整自己的作息时间。 调整自己的工作进度。
    我心我愿秀阅读 221评论 0 1