▲依我现在了解比较典型的案例大概有：
求N的阶乘、欧几里德算法(求最大公约数)、斐波那契数列、汉诺塔问题、树的三种递归遍历方式、快速排序、折半查找、图的遍历、归并排序、八皇后问题（回溯、递归）、棋盘覆盖（分治,递归）、Strassen矩阵乘法（分治）、最近点对问题(分治+递归)、循环赛日程表、凸包问题求解
package csdn.panghu.recursion;
/**
* @Description: [递归求N阶乘]
* @Author: [胖虎]
* @CreateDate: [2014-3-31 下午9:36:20]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*/
public class CalNFactorial {
public static int f(int n){
/*递归结束条件*/
if (n == 1){
return 1;
}
/*递归调用*/
return n * f(n-1);
}
public static void main(String[] args) {
System.out.println(f(5));
}
}JAVA实现代码：
package csdn.panghu.recursion;
/**
*
* @Description: [递归求解gcd欧几里德算法]
* @Author: [胖虎]
* @CreateDate: [2014-3-31 下午10:51:47]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*/
public class Gcd {
public static int gcd(int m, int n){
/*递归终结条件*/
if (n == 0){
return m;
}
/*递归调用*/
return gcd(n, m%n);
}
public static void main(String[] args) {
System.out.println(Gcd.gcd(6,4));
}
}在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
即F(0) = 0, F(1) = 1 为递归的终止条件
package csdn.panghu.recursion;
/**
* ps: 只为讲解递归,所以并不是最优的算法，望牛牛们勿喷!
*
* @Description: [递归方式求解斐波那契数列]
* @Author: [胖虎]
* @CreateDate: [2014-3-31 下午11:04:29]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*/
public class FibonacciSequence {
public static int fibonacci(int n){
/*递归结束条件*/
if (n == 0)
return 0;
if (n == 1)
return 1;
/*递归调用*/
return fibonacci(n-1) + fibonacci(n-2);
}
public static void main(String[] args) {
System.out.println(FibonacciSequence.fibonacci(6));
}
}
package csdn.panghu.recursion;
/**
*
* @Description: [递归方式求解汉诺塔问题]
* @Author: [胖虎]
* @CreateDate: [2014-4-1 上午12:16:59]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*/
public class HannoitaProblem {
public static void Hannoita(int n, char A, char B, char C){
/*递归结束条件*/
if (n == 1){
System.out.println("n=" + n + " " + A + "-->" + C);
}else{
/*递归的调用*/
Hannoita(n-1,A,C,B);
System.out.println("n=" + n + " " + A + "-->" + C);
Hannoita(n-1, B, A, C);
}
}
public static void main(String[] args) {
HannoitaProblem.Hannoita(3, ‘A‘, ‘B‘, ‘C‘);
}
}
package csdn.panghu.recursion;
/**
*
* @Description: [递归方式做二叉树的三种遍历]
* @Author: [胖虎]
* @CreateDate: [2014-4-1 上午12:29:35]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*
*
* 输出结果：
* 前序遍历：
0 1 3 7 8 4 2 5 6
中序遍历：
7 3 8 1 4 0 5 2 6
后序遍历：
7 8 3 4 1 5 6 2 0
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class BinaryTreeTraversal {
public static void PreOrderTraversal(TreeNode root){
/*递归结束条件*/
if (root == null)
return ;
System.out.print(root.val + " ");
/*递归调用*/
PreOrderTraversal(root.left);
PreOrderTraversal(root.right);
}
public static void InOrderTraversal(TreeNode root){
/*递归结束条件*/
if (root == null)
return ;
/*递归调用*/
InOrderTraversal(root.left);
System.out.print(root.val + " ");
InOrderTraversal(root.right);
}
public static void PostOrderTraversal(TreeNode root){
/*递归结束条件*/
if (root == null)
return ;
/*递归调用*/
PostOrderTraversal(root.left);
PostOrderTraversal(root.right);
System.out.print(root.val + " ");
}
public static void main(String[] args) {
//初始化一棵二叉树, 不影响递归的思想，可忽略
TreeNode[] nodes = new TreeNode[9];
for (int i=8; i>=0; --i){
nodes[i] = new TreeNode(i);
if (2*i + 1 > 8){
nodes[i].left = null;
nodes[i].right = null;
}else{
nodes[i].left = nodes[2*i+1];
if (2*i + 2 > 8){
nodes[i].right = null;
}else{
nodes[i].right = nodes[2*i+2];
}
}
}
System.out.println("前序遍历：");
PreOrderTraversal(nodes[0]);
System.out.println("\n中序遍历：");
InOrderTraversal(nodes[0]);
System.out.println("\n后序遍历：");
PostOrderTraversal(nodes[0]);
}
}
JAVA实现代码：
package csdn.panghu.recursion;
/**
*
* @Description: [展示快速排序中的递归算法 + 分治思想]
* @Author: [胖虎]
* @CreateDate: [2014-4-1 上午12:46:14]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*
* 待排序列：{7,-1,10,2,0,9,11,3,4}
* 输出排序结果：{-1,0,2,3,4,7,9,10,11}
*
*/
public class QuickSortProblem {
public static int Partion(int[] arrays, int left, int right){
if (right==left)
return left;
int key = arrays[left];
while (left < right){
//从后往前搜索比key小的元素,填入arrays[i]的位置中，并跳出循环
while (left < right){
if (arrays[right] < key){
arrays[left] = arrays[right];
break;
}
right--;
}
while (left < right){
if (arrays[left] > key){
arrays[right] = arrays[left];
break;
}
left++;
}
}
arrays[left] = key; //最终取出来的这个比较数的位置
//此时middle = left = right
return left;
}
public static void QuickSort(int[] arrays, int left, int right){
if (left >= right)
return ;
int middle = Partion(arrays, left, right);
QuickSort(arrays,left,middle);
QuickSort(arrays,middle+1,right);
}
public static void main(String[] args) {
int[] arrays = new int[]{7,-1,10,2,0,9,11,3,4};
QuickSort(arrays,0,arrays.length-1);
for (int i=0; i<arrays.length; ++i){
System.out.print(arrays[i] + " ");
}
}
}
package csdn.panghu.recursion;
/**
*
* @Description: [折半查找中使用到的递归和分治思想,O(logN)]
* @Author: [胖虎]
* @CreateDate: [2014-4-1 上午1:24:01]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*/
public class BinarySearch {
public static boolean IsExist(int[] arrays, int key, int left, int right){
/*递归结束条件*/
if (left == right){
if (arrays[left] == key){
return true;
}else{
return false;
}
}
/*递归调用*/
int middle = (right + left) / 2;
if (arrays[middle] > key){
return IsExist(arrays, key, left, middle-1);
}else if (arrays[middle] < key){
return IsExist(arrays, key, middle+1, right);
}else{
return true;
}
}
public static void main(String[] args) {
int[] arrays = new int[]{-2,-3,1,2,3,4,5,6,7,10};
System.out.println(BinarySearch.IsExist(arrays, -3, 0, arrays.length-1));
}
}
通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。
package csdn.panghu.recursion;
import java.util.GregorianCalendar;
import java.util.LinkedList;
import java.util.Queue;
/**
*
* @Description: [图遍历算法（主要是DFS）中的递归算法]
* @Author: [胖虎]
* @CreateDate: [2014-4-1 下午5:58:33]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*
*
* 输入： graph为博文中 图三 示例的有向图的邻接矩阵
* 输出：
* 图的深度遍历
A顶点(V0)被访问了！
B顶点(V1)被访问了！
E顶点(V4)被访问了！
D顶点(V3)被访问了！
C顶点(V2)被访问了！
图的广度遍历
A顶点(V0)被访问了！
B顶点(V1)被访问了！
D顶点(V3)被访问了！
E顶点(V4)被访问了！
C顶点(V2)被访问了！
*/
class Graph{
String[] Vexs;
int[][] Edges;
int VexsLen;
public Graph(String[] vexs, int[][] edges) {
super();
Vexs = vexs;
Edges = edges;
VexsLen = vexs.length;
}
}
public class GraphTraversal {
public static void main(String[] args) {
/*图的初始化: 我们选取一个博文中图3中的有向图做例子*/
String[] vexs = new String[5];
for (int i=0; i<5; ++i){
vexs[i] = (char)(‘A‘ + i ) + "顶点(V" + i + ")";
}
int[][] edges = new int[][]{
{0,1,0,1,0},
{1,0,0,0,1},
{0,1,0,1,0},
{1,0,0,0,0},
{0,0,0,1,0}
};
Graph graph = new Graph(vexs, edges);
/*图的深度遍历(递归)*/
System.out.println("图的深度遍历");
DFSTraversal(graph);
/*图的广度遍历(无关递归,但居然涉及到图遍历就也写下)*/
System.out.println("图的广度遍历");
BFSTraversal(graph);
}
public static void DFSTraversal(Graph graph){
/*初始化visited[]数组*/
boolean[] visited = new boolean[graph.VexsLen];
for (int i=0; i<graph.VexsLen; ++i){
visited[i] = false;
}
/*深度遍历*/
for (int i=0; i<graph.VexsLen; ++i){
if (!visited[i]){
DFS(graph, i, visited);
}
}
}
/**
*
* @param graph 图对象
* @param i 要访问的顶点下标i
*/
public static void DFS(Graph graph, int i, boolean[] visited){
/*访问该顶点*/
visitedMethod(graph,i);
/*设置成已访问*/
visited[i] = true;
for (int k=0; k<graph.VexsLen; ++k){
/*寻找还没有被访问过的邻接点*/
if (graph.Edges[i][k] == 1 && !visited[k]){
DFS(graph, k, visited);
}
}
}
public static void BFSTraversal(Graph graph){
/*初始化visited[]数组*/
boolean[] visited = new boolean[graph.VexsLen];
for (int i=0; i<graph.VexsLen; ++i){
visited[i] = false;
}
/*广度遍历,寻找源点*/
for (int i=0; i<graph.VexsLen; ++i){
if (!visited[i]){
BFS(graph,i,visited);
}
}
}
public static void BFS(Graph graph, int i,boolean[] visited){
if (graph.VexsLen < 0)
return ;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(i); //把源点的下标i加入到队列中
while (!queue.isEmpty()){
int index = queue.remove();
visitedMethod(graph, index);
visited[index] = true; //设置下标index的顶点为已访问过
for (int k=0; k<graph.VexsLen; ++k){
/*寻找还没有被访问过的邻接点*/
if (graph.Edges[index][k] == 1 && !visited[k]){
queue.add(k); //该顶点下标加入到队列中
}
}
}
}
public static void visitedMethod(Graph graph, int i){
System.out.println(graph.Vexs[i] + "被访问了！");
}
}package csdn.panghu.recursion;
/**
*
* @Description: [归并排序:体现递归和分治]
* @Author: [胖虎]
* @CreateDate: [2014-4-1 下午9:18:42]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*
* 输入： 归并排序前的序列 {-7,1,0,10,9,-20,100,8,1}
* 输出： 归并排序后的序列 {-20,-7,0,1,1,8,9,10,100}
*/
public class MergeSortProblem {
public static void main(String[] args) {
int[] arrays = new int[]{-7,1,0,10,9,-20,100,8,1};
MergeSort(arrays);
}
public static void MergeSort(int[] arrays){
int len = arrays.length;
if (len < 2)
return ;
int left = 0;
int right = len-1;
Sort(arrays, left, right);
System.out.println("归并排序后的序列");
for (int i : arrays){
System.out.print(i + " ");
}
}
//排序
private static void Sort(int[] arrays, int left, int right) {
/*递归结束条件*/
if(right == left){
return ;
}
int middle = (right + left) / 2; //二分
/*递归调用(大问题分解成小问题)+分治思想(先左右两边排序)*/
Sort(arrays, left, middle);
Sort(arrays, middle+1, right);
Merge(arrays, left, middle, right);/*结果的合并*/
}
//合并
public static void Merge(int[] arrays, int left, int middle, int right){
int len = right - left + 1;
int[] temp = new int[len];
int k = 0;
int i = left;
int j = middle+1;
while (i <= middle && j <= right){
if (arrays[i] < arrays[j]){
temp[k++] = arrays[i];
i++;
continue;
}else{
temp[k++] = arrays[j];
j++;
continue;
}
}
while (i <= middle){
temp[k++] = arrays[i];
i++;
}
while (j <= right){
temp[k++] = arrays[j];
j++;
}
k = k - 1;
for (int m=right; m>=left; --m){
arrays[m] = temp[k--];
}
}
}
package csdn.panghu.recursion;
/**
*
* @Description: [详细讲解N皇后问题（超详细注释）]
* @Author: [胖虎]
* @CreateDate: [2014-4-2 上午12:40:49]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*/
public class NQueenProblem {
private final int SAFE_POSITION = 0;//表示当前位置为安全位置
private int QueenCount; //皇后的个数
private int result = 0; //解法的个数
/**
* 表示棋盘的位置，数组里的值表示为“冲突的皇后数”
* 如：Position[i][j] = 2 表示 i 行, j列这个位置有两个皇后和它冲突
* 所以你放在这个位置，就会有两个皇后和你冲突！！即不满足条件
*
* Position[i][j] = SAFE_POSITION = 0; 这样表示0个皇后和它冲突
* 所以你可以把皇后放在这个位置！
*/
private int[][] Position; //表示棋盘的数组
/*
* 数组下标代表棋盘的row向量，
* 而数组的值为棋盘的col向量。
* 如：皇后(row, col) 可表示为(SafeQueens[row] = col)
* */
private int[] SafeQueens; //表示已经找到安全位置的皇后(为了输出解)
private long time; //用来计算算法所用时间
public NQueenProblem(int n) {
this.QueenCount = n; //皇后的个数
this.Position = new int[n][n]; //n*n棋盘
this.SafeQueens = new int[n];
}
public void Solve() {
if (QueenCount <= 0)
return ;
time = System.currentTimeMillis();
FindSafeQueen(0);
}
/**
* 这个是要递归的函数
* @param row 表示要找的是第row行的皇后（row: 0 ~ N-1）
*/
public void FindSafeQueen(int row){
for (int col=0; col<QueenCount; ++col){
/*如果此位置现在是安全的位置*/
if (Position[row][col] == SAFE_POSITION){
SafeQueens[row] = col;//设置row行的皇后位置
/*为棋盘添加冲突数： (以下注释较多，方便理解，也自己可以去除掉！！)*/
/* 下面要做处理：把跟这个row行皇后处于
* “竖直方向”，“斜线方向”，“反斜线方向”
* 的位置标记一下
* 我们只处理row+1行 ~ N-1行所不能放皇后的位置
* 而不考虑小于等于row行的那些情况，因为我们取皇后的时候是一行行往下的
* */
for (int dealRow=row+1; dealRow<QueenCount; ++dealRow){
/* "|" （竖直方向）所波及到的位置,冲突皇后数+1个*/
Position[dealRow][col]++;
/* "/"（斜杠方向）所波及到的位置, 由于我们只考虑大于 row + 1 ~ 第N行，
* 只需要考虑斜线的左下方的那些位置（这样才能保证大于row行）
* 即条件：列 (col - (dealRow - row)) >= 0
* "列"不要越过下边界 0
* */
if ((col - (dealRow - row)) >= 0){
/* "/"（斜杠方向）所波及到的位置,冲突皇后数+1个*/
Position[dealRow][(col - (dealRow - row))]++;
}
/* "\"（反斜杠方向）所波及到的位置, 由于我们只考虑大于 row + 1 ~ 第N(即QueenCount)行
* 我们只需要考虑反斜线的右下方的那些位置（这样才能保证大于row行）
* 即条件：(col + (dealRow - row)) < QueenCount
* "列"不要越过上边界 N(即QueenCount)
* */
if ((col + (dealRow - row)) < QueenCount){
/* "/"（斜杠方向）所波及到的位置,冲突皇后数+1个*/
Position[dealRow][(col + (dealRow - row))]++;
}
}
/*最后一行*/
if (row == QueenCount-1){
printOneResult(++result);
}else{
//递归调用,去求row+1行的N皇后位置
FindSafeQueen(row+1);
}
/*为棋盘减少冲突数（跟增加冲突数相反）*/
for (int dealRow=row+1; dealRow<QueenCount; ++dealRow){
/* "|" （竖直方向）所波及到的位置,冲突皇后数 -1个*/
Position[dealRow][col]--;
if ((col - (dealRow - row)) >= 0){
/* "/"（斜杠方向）所波及到的位置,冲突皇后数 -1个*/
Position[dealRow][(col - (dealRow - row))]--;
}
if ((col + (dealRow - row)) < QueenCount){
/* "/"（斜杠方向）所波及到的位置,冲突皇后数 -1个*/
Position[dealRow][(col + (dealRow - row))]--;
}
}
}
}
if(row == 0){
System.out.println(QueenCount + "皇后共有 " + result + " 个解\n包括printf,共耗时："
+ (System.currentTimeMillis() - time) + "毫秒");
}
}
private void printOneResult(int result) {
System.out.println(QueenCount + "皇后的第 " + result + " 个解：(皇后: ▲ 其他空位置: - )");
for (int i = 0; i < QueenCount; i++) {
for (int j = 0; j < QueenCount; j++) {
System.out.print(SafeQueens[i] == j ? " ▲ " : " - ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
int N = 8; //定义N皇后问题
NQueenProblem queenProblem = new NQueenProblem(N);
queenProblem.Solve();
}
}
package csdn.panghu.recursion;
/**
*
* @Description: [棋盘覆盖问题：涉及递归]
* @Author: [胖虎]
* @CreateDate: [2014-4-2 上午2:06:51]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*
* 呜呜~~我要睡觉！！！！！！！！
*/
public class ChessBoardProblem {
private int[][] Board; //模拟棋盘
private int specialRow;
private int specialCol;
private int size;
private int type = 0;
public ChessBoardProblem(int specialRow, int specialCol, int size) {
//初始化棋盘 和 特殊方格位置
this.size = (int) Math.pow(2, size);
this.Board = new int[this.size][this.size];
this.specialRow = specialRow;
this.specialCol = specialCol;
}
/**
*
* @param specialRow 特殊方格所在位置的行标
* @param specialCol 特殊方格所在位置的列标
* @param leftRow 要处理的子棋盘的左上方行标
* @param leftCol 要处理的子棋盘的左上方列标
* @param size 要处理的子棋盘的大小(size * size)
*/
private void ChessBoard(int specialRow, int specialCol, int leftRow, int leftCol,int size){
if (size == 1)
return ;
int subSize = size / 2;
type = type % 4 + 1;
int t = type;
/*处理划分四个子棋盘的左上方那个棋盘*/
if (specialRow < leftRow + subSize && specialCol < leftCol + subSize){
//表示特殊方格存在于子棋盘的左上角
ChessBoard(specialRow,specialCol,leftRow,leftCol,subSize); //本来就有特殊方格，递归调用咯!
}else{
//如果特殊方格不在子棋盘的左上角，那么必定被划分之后要补充的特殊方格在左上角区域中的右下方那个方格
Board[leftRow + subSize-1][leftCol + subSize-1] = t; //设置为type类型的骨牌(即这个子棋盘也有了特殊方格)
ChessBoard(leftRow + subSize-1,leftCol + subSize-1,leftRow,leftCol,subSize); //有了这个特殊方格之后，
递归调用咯!
}
/*处理划分四个子棋盘的右上方那个棋盘*/
if (specialRow < leftRow + subSize && specialCol >= leftCol + subSize){
//表示特殊方格存在于子棋盘的右上角
ChessBoard(specialRow,specialCol,leftRow,leftCol + subSize,subSize); //本来就有特殊方格，递归调用咯!
}else{
//如果特殊方格不在子棋盘的右上角，那么必定被划分之后要补充的特殊方格在右上角区域中的左下方那个方格
Board[leftRow + subSize-1][leftCol + subSize] = t; //设置为type类型的骨牌(即这个子棋盘也有了特殊方格)
ChessBoard(leftRow + subSize-1,leftCol + subSize,leftRow,leftCol + subSize,subSize); //有了这个特殊方
格之后，递归调用咯!
}
/*处理划分四个子棋盘的左下方那个棋盘*/
if (specialRow >= leftRow + subSize && specialCol < leftCol + subSize){
//表示特殊方格存在于子棋盘的左下角
ChessBoard(specialRow,specialCol,leftRow + subSize,leftCol,subSize); //本来就有特殊方格，递归调用咯!
}else{
//如果特殊方格不在子棋盘的左下角，那么必定被划分之后要补充的特殊方格在左下角区域中的右上方那个方格
Board[leftRow + subSize][leftCol + subSize-1] = t; //设置为type类型的骨牌(即这个子棋盘也有了特殊方格)
ChessBoard(leftRow + subSize,leftCol + subSize-1,leftRow+subSize,leftCol,subSize); //有了这个特殊方
格之后，递归调用咯!
}
/*处理划分四个子棋盘的右下方那个棋盘*/
if (specialRow >= leftRow + subSize && specialCol >= leftCol + subSize){
//表示特殊方格存在于子棋盘的右下角
ChessBoard(specialRow,specialCol,leftRow+subSize,leftCol+subSize,subSize); //本来就有特殊方格，递归
调用咯!
}else{
//如果特殊方格不在子棋盘的右下角，那么必定被划分之后要补充的特殊方格在右下角区域中的左上方那个方格
Board[leftRow+subSize][leftCol+subSize] = t; //设置为type类型的骨牌(即这个子棋盘也有了特殊方格)
ChessBoard(leftRow+subSize,leftCol+subSize,leftRow+subSize,leftCol+subSize,subSize); //有了这个特殊方
格之后，递归调用咯!
}
}
public void solve(){
ChessBoard(specialRow,specialCol,0,0,size);
printfResult();
}
private void printfResult() {
for (int i=0; i<size; ++i){
for (int j=0; j<size; ++j){
System.out.print(Board[i][j] + " ");
}
System.out.println("");
}
}
public static void main(String[] args) {
int N = 2;
int specialRow = 0;
int specialCol = 1;
ChessBoardProblem chessBoardProblem = new ChessBoardProblem(specialRow, specialCol, N);
chessBoardProblem.solve();
}
}
package csdn.panghu.recursion;
/**
*
* @Description: [Strassen矩阵乘法]
* @Author: [胖虎]
* @CreateDate: [2014-4-2 上午9:13:16]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*
* 输入的矩阵：A
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
输入的矩阵：B
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
输出的矩阵：C
30 60 90 120
60 120 180 240
90 180 270 360
120 240 360 480
*/
public class StrassenProblem {
public void solve(int N, int[][] A, int[][] B, int[][] C){
if (N <= 0)
return ;
strassen(N,A,B,C);
}
/**
*
* @param N 矩阵的规模
* @param A 矩阵A
* @param B 矩阵B
* @param C 结果矩阵C
*/
private void strassen(int N, int[][] A, int[][] B, int[][] C){
//定义一些中间变量
int [][] M1=new int [N][N];
int [][] M2=new int [N][N];
int [][] M3=new int [N][N];
int [][] M4=new int [N][N];
int [][] M5=new int [N][N];
int [][] M6=new int [N][N];
int [][] M7=new int [N][N];
int [][] C11=new int [N][N];
int [][] C12=new int [N][N];
int [][] C21=new int [N][N];
int [][] C22=new int [N][N];
int [][] A11=new int [N][N];
int [][] A12=new int [N][N];
int [][] A21=new int [N][N];
int [][] A22=new int [N][N];
int [][] B11=new int [N][N];
int [][] B12=new int [N][N];
int [][] B21=new int [N][N];
int [][] B22=new int [N][N];
int [][] temp=new int [N][N];
int [][] temp1=new int [N][N];
/*递归结束条件： 如果矩阵为2*2规模的，直接算！*/
if (A.length == 2){
MatrixMul(A,B,C);
}else{
//首先将矩阵A，B 分为4块
for(int i = 0; i < A.length/2; i++) {
for(int j = 0; j < A.length/2; j++) {
A11[i][j]=A[i][j];
A12[i][j]=A[i][j+A.length/2];
A21[i][j]=A[i+A.length/2][j];
A22[i][j]=A[i+A.length/2][j+A.length/2];
B11[i][j]=B[i][j];
B12[i][j]=B[i][j+A.length/2];
B21[i][j]=B[i+A.length/2][j];
B22[i][j]=B[i+A.length/2][j+A.length/2];
}
}
//计算M1
MatrixSub(B12, B22, temp);
MatrixMul(A11, temp, M1);
//计算M2
MatrixAdd(A11, A12, temp);
MatrixMul(temp, B22, M2);
//计算M3
MatrixAdd(A21, A22, temp);
MatrixMul(temp, B11, M3);
//M4
MatrixSub(B21, B11, temp);
MatrixMul(A22, temp, M4);
//M5
MatrixAdd(A11, A22, temp1);
MatrixAdd(B11, B22, temp);
MatrixMul(temp1, temp, M5);
//M6
MatrixSub(A12, A22, temp1);
MatrixAdd(B21, B22, temp);
MatrixMul(temp1, temp, M6);
//M7
MatrixSub(A11, A21, temp1);
MatrixAdd(B11, B12, temp);
MatrixMul(temp1, temp, M7);
//计算C11
MatrixAdd(M5, M4, temp1);
MatrixSub(temp1, M2, temp);
MatrixAdd(temp, M6, C11);
//计算C12
MatrixAdd(M1, M2, C12);
//C21
MatrixAdd(M3, M4, C21);
//C22
MatrixAdd(M5, M1, temp1);
MatrixSub(temp1, M3, temp);
MatrixSub(temp, M7, C22);
//结果送回C中
for(int i = 0; i < C.length/2; i++) {
for(int j = 0; j < C.length/2; j++) {
C[i][j]=C11[i][j];
C[i][j+C.length/2]=C12[i][j];
C[i+C.length/2][j]=C21[i][j];
C[i+C.length/2][j+C.length/2]=C22[i][j];
}
}
}
}
/**
* 矩阵乘法，此处只是定义了2*2矩阵的乘法
* */
public void MatrixMul(int[][] first, int[][] second, int[][] resault){
for(int i = 0; i < 2; ++i) {
for(int j = 0; j < 2; ++j) {
resault[i][j] = 0;
for(int k = 0; k < 2; ++k) {
resault[i][j] += first[i][k] * second[k][j];
}
}
}
}
/**
* 矩阵的加法运算
* */
public void MatrixAdd(int[][] first, int[][] second, int[][] resault){
for(int i = 0; i < first.length; i++) {
for(int j = 0; j < first[i].length; j++) {
resault[i][j] = first[i][j] + second[i][j];
}
}
}
/**
* 矩阵的减法运算
* */
public void MatrixSub(int[][] first, int[][] second, int[][] resault){
for(int i = 0; i < first.length; i++) {
for(int j = 0; j < first[i].length; j++) {
resault[i][j] = first[i][j] - second[i][j];
}
}
}
public static void main(String[] args) {
int N = 4; //矩阵的大小
int[][] A = new int[N][N];
int[][] B = new int[N][N];
int[][] C = new int[N][N];
/*A, B矩阵的初始化,具体值无所谓哈！也可以自己录入*/
for (int i=0; i<N; ++i){
for (int j=0; j<N; ++j){
A[i][j] = (i+1) * (j+1);
B[i][j] = (i+1) * (j+1);
}
}
System.out.println("输入的矩阵：A");
printfMatrix(A);
System.out.println("输入的矩阵：B");
printfMatrix(B);
StrassenProblem strassenProblem = new StrassenProblem();
strassenProblem.solve(N, A, B, C);
System.out.println("输出的矩阵：C");
printfMatrix(C);
}
private static void printfMatrix(int[][] matrix) {
for (int i=0; i<matrix.length; ++i){
for (int j=0; j<matrix.length; ++j){
System.out.print(matrix[i][j] + "\t");
}
System.out.println("");
}
}
}
package csdn.panghu.recursion;
import java.util.Arrays;
import java.util.Comparator;
/**
*
* @Description: [求解最近点对问题]
* @Author: [胖虎]
* @CreateDate: [2014-4-2 上午9:57:22]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*
*/
class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "[x=" + x + ", y=" + y + "]";
}
}
public class PointMinDistanceProblem {
private Point leftPoint = new Point(-1, -1);
private Point rightPoint = new Point(-1, -1);
private static Point[] points = new Point[]{
new Point(1,3),
new Point(5,6),
new Point(-1,10),
new Point(10,6),
new Point(2,5),
new Point(4,9),
new Point(3,2),
new Point(7,7),
};
public static void main(String[] args) {
PointMinDistanceProblem p = new PointMinDistanceProblem();
//1. 蛮力法求解：O(n^2)
// double dis1 = p.getMinDistance1(points,0,points.length-1);
// System.out.println("直接暴力: " + dis1);
//2. 分治法求解
double dis2 = p.getMinDistance2(points);
System.out.println("分治法求解最近点对距离: " + dis2 + " Point1:" + p.leftPoint + " Point2:" + p.rightPoint);
}
/*蛮力法*/
public double getMinDistance1(Point[] points, int left, int right){
double minDistance = Double.MAX_VALUE;
for (int i=left; i<=right; ++i){
for (int j=i+1; j<=right; ++j){
double distance = getDistance(points[i],points[j]);
if (minDistance > distance){
leftPoint = points[i];
rightPoint = points[j];
minDistance = distance;
}
}
}
return minDistance;
}
class xcomparator implements Comparator<Point>{
public int compare(Point p1, Point p2) {
return p1.x > p2.x ? 1 : p1.x == p2.x ? 0 : -1;
}
}
/*分治法*/
public double getMinDistance2(Point[] points){
int len = points.length;
if (len == 1){
return Double.MAX_VALUE;
}
/*根据所有点的x值进行排序*/
Arrays.sort(points,new xcomparator());
return getMinDistance(points, 0, len-1);
}
public double getMin(double leftdis, double rightdis){
return leftdis > rightdis ? rightdis : leftdis;
}
public double getMinDistance(Point[] points, int left, int right){
if (right - left < 3){
return getMinDistance1(points,left,right);
}
//求出中间
int mid = (left + right) / 2;
double leftMin = getMinDistance(points, left, mid);
double rightMin = getMinDistance(points, mid+1, right);
double currentMin = leftMin > rightMin ? rightMin : leftMin;
//求出左边
int leftR = 0;
int rightR = 0;
for (int i=left; i<mid; ++i){
if (points[mid].x - points[i].x < currentMin){
leftR = i;
break;
}
}
for (int i=right; i>mid; --i){
if (points[i].x - points[mid].x < currentMin){
rightR = i;
break;
}
}
double midMin = getMinDistance1(points, leftR, rightR);
return midMin > currentMin ? currentMin : midMin;
}
/*求两点间的距离*/
public double getDistance(Point p1, Point p2){
return Math.sqrt(((p2.y - p1.y)*(p2.y - p1.y)) + ((p2.x - p1.x)*(p2.x - p1.x)));
}
}
package csdn.panghu.recursion;
/* 赛程表安排问题，有2的k次方（n）支球队，在n-1天两两比赛，每支球队每天只进行一场比赛，求安排日程表。
* 可用分治递归的方法求解，由样例图分析可知，可将整个日程表矩阵划分为四个同等大小部分，若左上角填充完毕，
* 则，右上角每个元素为左上角中同行对应元素再加上小矩阵长度，左下角矩阵每个元素为左上角矩阵中同列对应元
* 素再加上矩阵长度，而右下角矩阵和左上角矩阵一致。所以整个问题就在于左上角的填充，左上角的填充依然和原
* 问题一致，可以递归调用，递归结束条件是当矩阵长度为1时，将矩阵第一行第一列元素赋为1*/
/**
*
* @Description: [求解循环赛日程表安排问题（分治+递归）]
* @Author: [胖虎]
* @CreateDate: [2014-4-2 上午10:12:50]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*/
public class Schedule {
public void scheduleTable(int[][]t,int n){
if(n==1){
t[0][0]=1;
}else{
int m=n/2;
scheduleTable(t,m);
//填充右上角矩阵，每个元素为同一行，列下标减m的元素再加m
for(int i=0;i<m;i++){
for(int j=m;j<n;j++){
t[i][j]=t[i][j-m]+m;
}
}
//填充左下角矩阵，每个元素为同一列，行下标减m的元素再加m
for(int i=m;i<n;i++){
for(int j=0;j<m;j++){
t[i][j]=t[i-m][j]+m;
}
}
//填充右下下角矩阵，右下角矩阵与左上角矩阵一致
for(int i=m;i<n;i++){
for(int j=m;j<n;j++){
t[i][j]=t[i-m][j-m];
}
}
}
}
public static void main(String[]args){
int[][]num=new int[8][8];
int n=8;
Schedule s=new Schedule();
s.scheduleTable(num, n);
int c=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
System.out.print(num[i][j]+" ");
c++;
if((c%n)==0){
System.out.println();
}
}
}
}
}
凸包问题求解JAVA实现代码：
package csdn.panghu.recursion;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
* 详细注释,分治解决凸包问题
* @Description: [分治+递归解决凸包问题]
* @Author: [胖虎]
* @CreateDate: [2014-4-2 下午1:59:36]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*/
/*凸包上的点*/
class TuPoint {
double x;
double y;
public TuPoint(double x, double y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "TuPoint [x=" + x + ", y=" + y + "]";
}
}
/*凸包上的两点的连线*/
class TuLine {
TuPoint point1, point2;
public TuLine(TuPoint point1, TuPoint point2) {
this.point1 = point1;
this.point2 = point2;
}
//两点的距离（线的长度）
public double getDistance() {
double dx = point1.x - point2.x;
double dy = point1.y - point2.y;
return Math.sqrt(dx * dx + dy * dy);
}
@Override
public String toString() {
return "TuLine [point1=" + point1 + ", point2=" + point2 + "]";
}
}
public class TuBaoProblem {
//要处理的点集合
private List<TuPoint> pointList = null;
//点集pointList对应的凸包结果。
private List<TuLine> lineList = new ArrayList<TuLine>();
public TuBaoProblem(List<TuPoint> pointList) {
super();
this.pointList = pointList;
}
//求解凸包，并把结果存入到lineList中。
public void solve(){
//初始化：clear
lineList.clear();
if (pointList == null | pointList.isEmpty())
return ;
/*左凸包中的点集合*/
List<TuPoint> leftPointList = new ArrayList<TuPoint>();
/*右凸包中的点集合*/
List<TuPoint> rightPointList = new ArrayList<TuPoint>();
/*根据point的x坐标来排序*/
Collections.sort(pointList, new xcomparator());
/*找到x最小的点，即最左边的点*/
TuPoint leftPoint = pointList.get(0);
/*找到x最大的点，即最右边的点*/
TuPoint rightPoint = pointList.get(pointList.size() - 1);
/*leftPoint ~~ rightPoint的连线把大的凸包问题，分解成两个小的凸包问题*/
/*把总的点集，分成两半,对应放到leftPointList(左凸包点集) 或者 rightPointList(右凸包点集)*/
for (int i = 0; i < pointList.size(); i++) {// 穷举所有的点,
TuPoint tempPoint = pointList.get(i);
//判断点tempPoint所在区域为左凸包还是右凸包
double result = findArea(leftPoint, rightPoint, tempPoint);
if (result > 0) {
//tempPoint属于左边
leftPointList.add(tempPoint);
} else if (result < 0) {
//tempPoint属于右边
rightPointList.add(tempPoint);
}
}
//分别求解左右两个凸包
dealTuBao(leftPoint, rightPoint, leftPointList);
dealTuBao(rightPoint, leftPoint, rightPointList);
}
private void dealTuBao(TuPoint p1, TuPoint p2, List<TuPoint> subPointList){
if (subPointList.isEmpty()){
/*递归结束条件*/
//这两个点所连成的线将是最终结果凸包上的一条!
lineList.add(new TuLine(p1, p2));
return ;
}
//subPointList不为空的话，我们要去找博文中图示上写的 Pmax 点
double maxArea = Double.MIN_VALUE;
TuPoint pMax = null;
for (int i = 0; i < subPointList.size(); i++) {
// 最大面积对应的点就是Pmax
double area = findArea(p1, p2, subPointList.get(i));
if (area > maxArea) {
pMax = subPointList.get(i);
maxArea = area;
}
}
/*下面的处理跟之前solve()函数中的处理一样*/
// 找出位于(p1, pMax)直线左边的点集s1
// 找出位于(pMax, p2)直线右边的点集s2
/*左凸包中的点集合*/
List<TuPoint> leftPointList = new ArrayList<TuPoint>();
/*右凸包中的点集合*/
List<TuPoint> rightPointList = new ArrayList<TuPoint>();
/*把点集subPointList，分成两半,对应放到leftPointList(左凸包点集)
* 或者 rightPointList(右凸包点集)*/
for (int i = 1; i < subPointList.size(); i++) {// 穷举所有的点,
TuPoint tempPoint = subPointList.get(i);
//判断点tempPoint所在区域为左凸包还是右凸包
/*线: p1 ~ pMax*/
double result1 = findArea(p1, pMax, tempPoint);
/*线: p2 ~ pMax*/
double result2 = findArea(pMax, p2, tempPoint);
if (result1 > 0) {
//tempPoint属于左边
leftPointList.add(tempPoint);
} else if (result2 > 0) {
//tempPoint属于右边
rightPointList.add(tempPoint);
}
}
//递归调用咯~~
dealTuBao(p1, pMax, leftPointList);
dealTuBao(pMax, p2, rightPointList);
}
/* 函数的功能: 1. 判断点在子凸包的左边或者右边 2.用来算三角形的面积，来找到Pmax点
* 三角形的面积等于返回值绝对值的二分之一
* 点p3位于直线(p1, p2)左侧时，表达式的结果为正
* 点p3位于直线(p1, p2)右侧时，表达式的结果为负
* */
private double findArea(TuPoint p1, TuPoint p2, TuPoint p3) {
return p1.x * p2.y + p3.x * p1.y + p2.x * p3.y - p3.x * p2.y - p2.x
* p1.y - p1.x * p3.y;
}
public static void main(String[] args) {
List<TuPoint> arrays = new ArrayList<TuPoint>();
arrays.add(new TuPoint(2, 4));
arrays.add(new TuPoint(3, 4));
arrays.add(new TuPoint(3, 3));
arrays.add(new TuPoint(4, 3));
arrays.add(new TuPoint(4, 4));
arrays.add(new TuPoint(5, 4));
arrays.add(new TuPoint(5, 2));
arrays.add(new TuPoint(3.5, 2));
arrays.add(new TuPoint(2, 2));
TuBaoProblem t = new TuBaoProblem(arrays);
t.solve();
t.printResult();
}
/*输出结果*/
public void printResult() {
for (Object i : lineList.toArray()){
System.out.println(i);
}
}
/*x比较器*/
class xcomparator implements Comparator<TuPoint>{
public int compare(TuPoint p1, TuPoint p2) {
return p1.x > p2.x ? 1 : p1.x == p2.x ? 0 : -1;
}
}
}三、笔试题、面试题案例（等待更新）
本文专注于<递归算法和分治思想>[胖虎学习算法系列],布布扣,bubuko.com
原文：http://blog.csdn.net/ljphhj/article/details/22799189