c语⾔分治法求众数重数_五⼤常见算法策略之——递归与分治
策略
递归与分治策略
递归与分治策略是五⼤常见算法策略之⼀，分治策略的思想就是 分⽽治之 ，即先将⼀个规模较⼤的⼤问题分解成若⼲个规模较⼩的⼩问题，再对这些⼩问题进⾏解决，得到的解，在将其组合起来得到最终的解。⽽分治与递归很多情况下都是⼀起结合使⽤的，能发挥出奇效(1+1>2)，这篇⽂章我们将先从递归说起，再逐渐向分治过渡，主要讲解⽅式是通过9个例题来说明问题的，问题都是根据难度由简到难，由浅⼊深，对递归与分治能有个⼤概的了解雏形，当然最重要还是要做⼤量练习才能掌握。
0.0、Fibonacci数列(易)
递归
我们第⼀次接触递归⼀般都是在初学C语⾔时候的⼀道题⽬——Fibonacci数列中看到的，可能刚开始感觉有点不可思议，函数居然可以调⽤⾃⼰！Amazing！但事实如此，它确实存在，⽽递归也为我们某些算法的设计提供很⼤的便利，⼀般来说递归函数在理解起来并不是很难，甚⾄可以通过数学归纳法给予证明，但⼀直让⼈诟病的⼀点莫过于Debug的时候了，有时候调试⼀个较为复杂的递归函数能把⼈逼疯。
我们在这⾥将会 由易到难 ，⽤⼀些例题先来讲解递归函数。采⽤Fibonacci数列来做这个引例来介绍递归函数。
Fibonacci
第⼀个数是1，第⼆个数也是1，从第三个数开始，后⾯每个数都等于前两个数之和。要求：输⼊⼀个n，输出第n个斐波那契数。
我们先来整理⼀下思路，分下⾯三步来看：
1、明确函数的输⼊和输出(即函数的作⽤)
2、明确递归终⽌条件
3、寻函数的递归关系式
第⼀步，函数输⼊n，输出(也就是返回)第n个斐波那契数：
public static int fibonacci(int n){        }
第⼆步，明确递归终⽌条件：
public static int fibonacci(int n){    if(n == 1) return 1;    else if (n == 2) return 1;}
第三步，寻函数的递归关系：
public static int fibonacci(int n){    if(n == 1) return 1;    else if(n == 2) return 1;    else return fibonacci(n - 1) + fibonacci(n - 2);}
就这样，我们的⼀个斐波那契数列的递归函数就写完了。当然，这只是我们的⼀个开胃⼩菜，下⾯继续是⼊门级别的⼀个题，算阶乘。
阶乘
输⼊⼀个数，输出它的阶乘。我们同样⽤那三步往下⾛。
第⼀步，函数输⼊n，返回n的阶乘
public static int factorial(int n){    }
第⼆步，明确递归终⽌条件：
public static int factorial(int n){                    //0的阶乘等于1        if(n == 0)  return 1;}
第三步，寻函数的递归关系
public static int factorial(int n){                    //0的阶乘等于1        if(n == 0)  return 1;        else return factorial(n - 1) * n;}
做完前两个你肯定会觉得这不是很简单吗，不要急，我们要由易到难，由浅⼊深，这样阶梯式的科学学习。下⾯这个例⼦是⼩青蛙跳台阶问
题，这个问题被⽤于递归和动态规划类问题的例题，我们这⾥先⽤递归解答，后⾯还会⽤动态规划策略来解决这个问题。
⼩青蛙跳台阶
⼀只青蛙⼀次可以跳上1级台阶，也可以跳上2级，求该青蛙跳上⼀个n级的台阶共有多少种跳法。
还是三步⾛，第⼀步，明确函数的输⼊及返回
public static int Jump_Floor1(int n){    }
第⼆步，明确递归终⽌条件
如果n=1，那⼩青蛙只能⼀次跳上第⼀节台阶，所以⼀种跳法，如果n=2，那⼩青蛙可以⼀次跳⼀节跳两次，或者直接⼀次跳两节，所以两
种跳法。
public static int Jump_Floor1(int n){        if(n <= 2){            return n;        }}
第三步，寻函数的递归条件
这⾥可不能简单的return Jump_Floor1(n-1)就完事⼉了，分了两种情况：1、第⼀次跳1级就还有n-1级要跳，2、第⼀次跳2级就还有n-
2级要跳
public static int Jump_Floor1(int n){    if(n <= 2){        return n;    }else{  //这⾥涉及到两种跳法，1、第⼀次跳1级就还有n-1级要跳，2、第⼀次跳2级就还有n-2级要跳
下⾯这个例题是排列问题，就是求出⼀组数的全排列。
全排列问题
我们在全排列问题种需要⽤到⼀个交换函数swap⽤于交换两个数的位置，作如下定义：k数组种元素为待排列元素，k和m为待交换两元素
的下标
private static void swap(int a[], int k, int m){      //交换k和m下标的元素的值        int temp = a[k];        a[k] = a[m];        a[m] = temp;}
接下来继续回到递归函数
第⼀步，明确函数的输⼊以及返回，这⾥我们需要输⼊待排列元素组成的数组，数组的第⼀个元素的下标，以及最后⼀个元素的下标
public static void perm(int a[], int k, int m){}
第⼆步，明确递归终⽌条件，就是当只剩下⼀个元素时
public static void perm(int a[], int k, int m){    if(k == m) {    //只有⼀个元素        for (int i = 0; i <= m; i++) {            System.out.print(a[i]+" ");        }        System.out.pri 第三步，寻递归条件
public static void perm(int a[], int k, int m){    if(k == m) {    //只有⼀个元素        for (int i = 0; i <= m; i++) {            System.out.print(a[i]+" ");        }        System.out.pri
下⾯是递归这块的最后⼀个例题了，整数划分问题。
整数划分
说明⼀下问题，什么是整数划分？
n=m1+m2+...+mi; (其中mi为正整数，并且1 <= mi <= n)，则{m1,m2,...,mi}为n的⼀个划分。
如果{m1,m2,...,mi}中的最⼤值不超过m，即max(m1,m2,...,mi)<=m，则称它属于n的⼀个m划分。这⾥我们记n的m划分的个数为
f(n,m);
举个例⼦，当n=5时我们可以获得以下这⼏种划分(注意，例⼦中m>=5)
5 = 5
= 4 + 1
= 3 + 2
= 3 + 1 + 1
= 2 + 2 + 1
= 2 + 1 + 1 + 1
= 1 + 1 + 1 + 1 + 1
编写程序，输⼊整数n,m，返回n的所有m的划分个数。
算法思路：我们⽤q(n,m)表⽰将n⽤不⼤于m的数字划分的⽅法的个数
1、n = 1时：只有⼀种划分法就是1
2、m = 1时：也只有⼀种划分法就是n个1相加
3、n < m时: 划分的⽅法也就只限于q(n,n)了，毕竟⽐n⼤的数也取不到嘛(不能取负数，要不然⽆限多了)
4、n = m时：就是1+(m-1)这⼀种情况加q(n,m-1)即1+q(n,m-1)。⽐如q(6,6)就是1+q(6,5)
5、n > m时：这种情况下⼜包含两种情况：
5(1)、划分中包含m时：即{m, {x1,x2,...xi}}(它们之和为n), 其中{x1,x2,... xi} 的和为n-m，所以就是n-m的m划分，即q(n-m,m)
5(2)、划分中不包含m时：划分中所有的值都⽐m⼩，即q(n,m-1)
因此第5中情况的划分为q(n-m,m)+1(n,m-1)
对第2中举例⼦详述：q(5,3):
(1)包含3: 1+1+3; 2+3; 既然每种情况都包含了3，那去掉3对其余各数相加为(5-3=)2的划分的个数和其相等，那就是对2(m=3)的
划分了
(2)不包含3： 1+1+1+1+1; 1+1+1+2; 1+2+2;
第⼀步，明确函数输⼊和返回
public static int equationCount(int n, int m){}
第⼆步，明确递归终⽌条件
public static int equationCount(int n, int m){        if (n < 1 || m < 1)            return 0;        if(n == 1 || m == 1)            return 1;}
第三步，寻递归关系
public static int equationCount(int n, int m){        if (n < 1 || m < 1)            return 0;        if(n == 1 || m == 1)            return 1;        if(n < m)            return equat
分治策略
分治策略的基本思想就是将⼀个规模为n的问题分解成k个规模较⼩的⼦问题，这些⼦问题互相独⽴且与原问题相同。递归的解这些⼦问题，
然后将⼦问题的解合并得到原问题的解，和这种说法最贴切的就是我们之前⼀篇⽂章介绍的归并排序法了，这篇⽂章⾥我们还会再引出⼀
遍。
我们将分治策略解决问题的步骤归纳为：将⼤问题分解成⼦问题，分别解决⼦问题，再将⼦问题的解合并成⼤问题的解.
先看第⼀个典型的例⼦——归并排序
归并排序
这⾥我们对归并排序主要注重体现它分治策略的算法逻辑，⽽不过多深究这个排序算法是如何执⾏的，具体的图解归并排序请移步我的另⼀
篇博⽂—— 数据结构之——⼋⼤排序算法 。
归并排序的思想是，先将数组分割成为⼀个个⼩数组，直到每个⼩数组中只含有⼀个元素，那么在这⼀个⼩数组⾥⾯，这⼀个元素⾃然就是
有序的，然后将其合并起来(由merge函数实现)，按从⼩到⼤的顺序，逐层向上，就是将⼩问题的解合并为⼤问题的解。
下⾯是将⼤问题分解成⼩问题的过程
/
** * 只要数组的⼤⼩不为1，就⼀直分割，直到不能分割为⽌(即数组长度为1)， * 不能分割后按照出⼊栈顺序，会将分割的⼩数组分别排序后归并起来 * @param data 下⾯是合并⼩问题的解，归并过程
/** * 这个函数是将数组合并在⼀起的，其实并没有将数组真的分开，只是⽤start和end指⽰不同的元素，来达到分割的⽬的 * @param  p        指⽰⼦数组1的元素 * @p ⼆分查
然后是分治策略的另⼀个经典例⼦———⼆分查，顾名思义，就是在⼀个有序(从⼩到⼤)的数组中查⼀个元素的位置，先从最中间将数
组变为两个⼩数组，然后与中间值进⾏对⽐，如果相等直接返回，不相等⼜分两种情况，如果中间元素⽐待查值⼩，就从后半个数组中继
续⼆分查，反之，从前半个数组中⼆分查。
c语言斐波那契数列public static int Binary_Search(int []data, int x, int n){  //data为待搜索数组(有序)，x为待搜索元素，n为数组⼤⼩    int left = 0, right = n - 1;            //指⽰左右的两个指棋盘覆盖
下⾯我们逐渐加⼤难度，接下来这个问题叫做棋盘覆盖，我们先简单介绍⼀下这个问题。
在⼀个2^k × 2^k (k≥0)个⽅格组成的棋盘中，恰有⼀个⽅格与其他⽅格不同，称该⽅格为特殊⽅格。显然，特殊⽅格在棋盘中可能出现
的位置有4^k种，因⽽有4^k种不同的棋盘，图4.10(a)所⽰是k=3时64种棋盘中的⼀个。棋盘覆盖问题(chess cover problem)要求⽤图
4.10(b)所⽰的4种不同形状的L型⾻牌覆盖给定棋盘上除特殊⽅格以外的所有⽅格，且任何2个L型⾻牌不得重叠覆盖。
图4.10(a)
图4.10(b)
在这⾥为了⽅便讲解，我们采⽤k=2时候的情况来说明这个问题，设初始情况为
第⼀次将其分割成四个⼩块，分成了四个⼦棋盘，以黄线为分割线
然后分别对其进⾏填充
填充完后，⼜可以将其分割

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。