五大常见算法策略之——递归与分治策略

递归与分治策略

递归与分治策略是五大常见算法策略之一,分治策略的思想就是分而治之,即先将一个规模较大的大问题分解成若干个规模较小的小问题,再对这些小问题进行解决,得到的解,在将其组合起来得到最终的解。而分治与递归很多情况下都是一起结合使用的,能发挥出奇效(1+1>2),这篇文章我们将先从递归说起,再逐渐向分治过渡,主要讲解方式是通过9个例题来说明问题的,问题都是根据难度由简到难,由浅入深,对递归与分治能有个大概的了解雏形,当然最重要还是要做大量练习才能掌握。


  
  
  
  
  

  
  
  
  

递归

我们第一次接触递归一般都是在初学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级要跳 return Jump_Floor1(n-1)+Jump_Floor1(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){ }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpzxzp.html