首页 > 代码库 > 浅谈递归和分治

浅谈递归和分治

2024-07-15 17:08:24   216人阅读

　

　　今天要谈论的话题主要是递归和分治。为什么要将分治和递归放在一起说？很简单，因为这两兄弟几乎不分家。就我所见过的，任何用到分治思想的算法就没有不用递归的。（如果某位朋友知道例外的，请不吝赐教。）

　　所谓递归，就是自己调用自己。第一步是设置基值条件用于方法的返回，否则方法将不停的自调用，直到程序崩溃。第二部是缩小问题域的范围并调用自己来求解，直到范围缩小到触发基值条件为止。

　　所谓分治，即分而治之。它也分两步：一，把一个大的问题域分解为小的问题域。二，对每个小的问题域按步骤一办理。（单从这句话来说，我们就明显看到递归的影子了。）

　　概念说清楚了，接下来还是拿递归分治最经典的一个算法——递归二叉查找——来举例。

　　先贴代码

 1 public class BinarySearchApp { 2     public static final int SIZE = 10; 3     public static int[] arrays = new int[SIZE]; 4  5     public static int binarySearch(int lower,int upper,int key) { 6          7         if(lower > upper) 8             return -1;//-1表示找不到 9         else {10             int current = (lower+upper)/2;11             if(arrays[current] == key)12                 return current;13             else if(arrays[current] > key)14                 return binarySearch(lower, current-1, key);//从下半截查找15             else16                 return binarySearch(current+1, upper, key);//从上半截查找17         }18     }19     20     public static void main(String[] args) {21         for(int i=0;i<10;i++)22             arrays[i]=i;23         System.out.println(binarySearch(0,SIZE-1,3));//查找3是第几个24         System.out.println(binarySearch(0,SIZE-1,9));//查找3是第几个25         System.out.println(binarySearch(0,SIZE-1,15));//查找3是第几个26     }27 }

 下面是运行结果

这个算法是从一个有序数组中查找一个特定的值并返回它的索引，它很好的体现了递归和分治的思想。首先，找出数组中间位置的值，将这个值与要查找的Key比较，如果相同，返回该位置。如果小于Key，就在数组的上半截查找，如果大于Key，就在数组的下半截查找。重复上面的流程直到找到结果或返回-1。该算法的时间复杂度仅为O(LogN)。当然，在调用该方法前，最好先判断一下Key是否位于数组最小值与最大值之间，在某些情况下可以有效提高效率。

 

 　　好了，今天的随笔差不多就要就结束了。最后给大家分享一个有意思的小算法——汉诺塔问题，为什么说它有意思呢？一般解汉诺塔问题的算法都是求出一共花多少次可以移完圆盘。老实说这个真心无聊，只要高中学过数学归纳法就能很容易算出来，一点体现不出计算机的优势。我这里给出的程序可以打印出整个移动过程的步骤。

 1 import java.io.BufferedReader; 2 import java.io.IOException; 3 import java.io.InputStreamReader; 4 public class Hanoi { 5     public static void main(String[] args) throws IOException { 6         System.out.println("Please input the number of disk:"); 7         int nDisks = getInt(); 8         doTower(nDisks,‘A‘,‘B‘,‘C‘); 9     }10     11     public static String getString() throws IOException {12         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));13         return reader.readLine();14     }15     public static int getInt() throws IOException {16         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));17         String string = reader.readLine();18         return Integer.parseInt(string);19     }20     public static void doTower(int topN,char from,char inter,char to) {21         if(topN == 1)22             System.out.println("Disk "+topN+" from "+from+" to "+to);23         else {24             doTower(topN-1, from, to, inter);//from --> inter25             System.out.println("Disk "+topN+" from "+from+" to "+to);26             doTower(topN-1, inter, from, to);//inter --> to27         }28     }29 }

运行结果贴在下面

 


联系
我们