【笔试面试】六大常见算法及经典题目

• 一个函数调用其自身
• 对应的数据结构：栈
• 递归的数学模型其实就是数学归纳法

• 递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。
• 特别地，在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况，这也正是递归的定义所在。格外重要的是，这个解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况。

• 明确递归终止条件；
• 给出递归终止时的处理办法；
• 提取重复的逻辑，缩小问题规模；

• 问题的定义是按递归定义的（Fibonacci函数，阶乘，…）；
• 问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；
• 数据结构是递归的（链表、图、树等的操作，包括树的遍历，树的深度，…）

1.概述：

• 一种简单直接地解决问题的方法，just do it；

• 一般来说蛮力策略常常是最容易实现的；

2.基本思想：

简单说是一种简单直接的算法设计策略，也叫作暴力法，枚举法或者穷举法，蛮力法解决问题常常简单粗暴，常常基于问题的描述和所涉及的概念，定义直接求解，逐一列举并且处理问题所涉及的所有情形，然后得到问题的答案。虽然通常情况下蛮力法效率很低，但可以作为衡量同类问题更高效算法的准绳。

• 在求解问题的过程中往往依据循环结构来实现。

• 蛮力法适应能力强，是唯一一种几乎什么问题都能解决的一般性方法。

• 蛮力法一般容易实现,在问题规模不大的情况下，蛮力法能够快速给出一种可接受速度下的求解方法.

3.求解问题所要依据的步骤：

4.典型问题：

• 百鸡百钱问题；
• 排序问题（选择排序、冒泡排序）
• 查找问题；

三、分治法

1. 基本思想：

• 求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。

• 分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。

• 分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。

2. 分治法解决问题的先决条件：

• 该问题的规模缩小到一定的程度就可以容易地解决；

• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

• 利用该问题分解出的子问题的解可以合并为该问题的解；

• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

• 划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。

• 求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。

• 合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现

divide-and-conquer(P){ 
     if ( | P | <= n0) adhoc(P);   //解决小规模的问题 
  
     divide P into smaller subinstances P1,P2,...,Pk；//分解问题 
  
     for (i=1; i<=k; i++) 
         yi=divide-and-conquer(Pi);  //递归的解各子问题 
  
     return merge(y1,...,yk);  //将各子问题的解合并为原问题的解 
} 

• 分析依据-递推方程

• 两类递推方程：

第二张递推公式经过迭代法可以得到：

• 求解方法：迭代法，递归树，Master定理；

• 大整数乘法；
• 排列问题 ；
• 整数划分问题；
• 二分搜索 ；
• 矩阵乘法；（Strassen乘法）
• 归并排序；
• 快速排序；
• 线性时间选择；
• 最近点对问题；
• 棋盘覆盖问题；

四、动态规划