大佬教程收集整理的这篇文章主要介绍了一、递归与分治策略，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

一、概述

1.设计思想

@H_801_10@递归：直接或间接地调用自身 

@H_801_10@分治法：将一个规模为n的难以解决的大问题划分成k个规模较小的子问题，这些子问题相互独立且与原问题性质和解法类似，递归求解这些子问题，再合并子问题的解得到原问题的解

2.求解过程

@H_801_10@（1）划分（平衡子问题、独立子问题）

@H_801_10@（2）求解子问题（递归、循环）

@H_801_10@（3）合并（对算法效率影响较大）

二、例题总结

（前面5个问题运用递归策略，后面运用分治策略）

1.阶乘函数

@H_801_10@递归定义式：

@H_801_10@递归实现：

@H_801_10@

@H_801_10@ 

@H_801_10@ 

@H_801_10@ 

@H_801_10@ 

@H_801_10@ 

2.Fibonacci数列

@H_801_10@递归定义式：

@H_801_10@

@H_801_10@递归实现：

@H_801_10@

@H_801_10@算法改进：避免重复计算，自下而上计算，由f(0)和f(1)算出f(2)...

@H_801_10@

3.排列生成问题

@H_801_10@

@H_801_10@递归关系：

@H_801_10@（1）将n个元素看成由两部分组成：第一部分是第一个元素，第二部分是后面所有元素；

@H_801_10@（2）将生成排列过程看作两步：第一步求所有可能出现在第一个位置的元素，即把第一个元素与后面所有元素交换； 第二步固定第一个元素，求后面所有元素的排列。

@H_801_10@Perm(R)的递归算法实现：

@H_801_10@

 

@H_801_10@

4.整数划分问题

@H_801_10@将正整数n表示成一系列正整数之和，称这种表示为正整数n的划分，称n的不同划分个数为正整数n的划分数，记作p(n)

@H_801_10@

5.Hanoi塔问题

@H_801_10@

6.折半查找

@H_801_10@

@H_801_10@

 7.大整数乘法（算法思想>代码）

@H_801_10@ 

@H_801_10@

@H_801_10@

8.Strassen矩阵乘法

@H_801_10@

@H_801_10@ 

@H_801_10@ 

@H_801_10@ 

 9.棋盘覆盖

@H_801_10@棋盘覆盖问题(board cover problem)要求用4中不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何两个L型骨牌不得重复覆盖。

@H_801_10@分治策略：将棋盘划分为大小相等的子棋盘，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的子问题。具体步骤如下：将2^k*2^k棋盘划分为4个2^k-1*2^k-1子棋盘，特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘无特殊方格，用一个L型骨牌覆盖这3个较小棋盘的汇合处，又得到3个具有特殊方格的子棋盘，从而将原问题转换为4个较小规模的棋盘覆盖问题。递归使用这种分割，直至棋盘简化为1*1棋盘。

@H_801_10@算法实现：

@H_801_10@ 

@H_801_10@ 算法分析：

@H_801_10@

10.归并排序

@H_801_10@按记录在序列中的位置对序列进行划分，稳定的算法

@H_801_10@算法思想：

@H_801_10@将待排序序列划分为长度大致相等的两个子序列，若子序列长度为1，则划分结束，否则继续执行划分，最后得到n个长度为1的有序子序列；

@H_801_10@不断进行两两合并，用归并算法将它们排序；

@H_801_10@如此继续下去，直至得到一个长度为n的有序序列。

@H_801_10@算法实现：设将两个相邻有序子序列r[s]~r[m]和r[m+1]~r[t]合并为一个有序序列r1[s]~r1[t]，函数Merge实现合并操作。

@H_801_10@

 

@H_801_10@ 算法分析：

@H_801_10@

 11.快速排序

@H_801_10@ 按照记录的值对序列进行划分，不稳定的算法

@H_801_10@算法思想：

@H_801_10@

@H_801_10@ 算法实现：

@H_801_10@

@H_801_10@算法分析：

@H_801_10@

 12.最近点对问题

@H_801_10@给定平面上n个点，找其中的一对点，使得在N个点组成的所有点对中，该点对间的距离最小。(只找其中一对最近点即可)

@H_801_10@算法思想：

@H_801_10@（1）划分：将集合S划分为两个子集S1和S2，根据平衡子问题原则，每个子集大约包含n/2个点，设最近点对为Pi和Pj，有以下三种情况：

@H_801_10@           ①Pi和Pj均在S1中；

@H_801_10@           ②Pi和Pj均在S2中；

@H_801_10@           ③Pi在S1中，Pj在S2中。

@H_801_10@（2）求解子问题：情况①②可递归求解：l为S中各点x坐标的中位数，垂线x=l将S划分为S1和S2，递归地在S1和S2中求解最近点对问题，得到最近距离d=min{d1,d2}；         

@H_801_10@                               情况③：设P1是S1中距离垂线l在长度d之内的所有点集，P2是S2中距离垂线l在长度d之内的所有点集；

@H_801_10@                                              将P1和P2中的点依其y坐标值排序，设p(x,y)是y坐标最小的点(P1和P2都有可能)；

@H_801_10@                                              依次处理P1，P2中的点，在y坐标区间[y,y+d]内最多选出8个候选点，计算它们和点p之间的距离，最后得到最近距离d3；

@H_801_10@（3）合并：比较d1、d2和d3，选取最小距离作为原问题的解。

@H_801_10@ 算法实现：

@H_801_10@

@H_801_10@

@H_801_10@算法分析：

@H_801_10@

 13.循环赛日程表

@H_801_10@

@H_801_10@ 

@H_801_10@ 算法思想：

@H_801_10@

@H_801_10@ 算法实现：

@H_801_10@

@H_801_10@ 

大佬总结

以上是大佬教程为你收集整理的一、递归与分治策略全部内容，希望文章能够帮你解决一、递归与分治策略所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。