各种递归算法

斐波那契数列

定义:

  • 斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368........,这个数列从第3项开始,每一项都等于前两项之和。
  • 斐波那契数列又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)。

代码:

import org.junit.jupiter.api.Test;

/**
 * 斐波那契数列
 * @author wydream
 *
 */

public class Algorithm_1 {

	/**
     * 用递归实现斐波那契数列,适用于求解比较小的位置数值
     * 0 1 1 2 3 5 8 13 21...
     * @param n
     * @return
     */
	
	public int getNum(int n) {
		if(n<=2) {
			return 1;
		}else {
			return getNum(n-1)+getNum(n-2);
		}
	}
	
	@Test
	public void test() {
		System.out.println(getNum(6));
	}
	
}

求阶乘

import org.junit.jupiter.api.Test;

public class Algorithm_2 {
	
	public int getSum(int n) {
		//当n=1时,直接返回
		if(n==1) {
			System.out.print(n + "=");
			return n;
		}else {//n>1时,递归调用getSum方法,求出n*n-1的结果
			System.out.print(n + "*");
			return n*getSum(n-1); 
		}
	}
	
	@Test
	public void test() {
		System.out.println(getSum(4));
	}

}

列出某个目录下所有子目录和文件

import java.io.File;

import org.junit.jupiter.api.Test;

/**
 * 列出某个目录下所有子目录和文件
 * @author wydream
 *
 */

public class Algorithm_3 {

	public void getDir(String path) throws Exception{
		File file=new File(path);
		if(file.isDirectory()) {
			System.out.println("Dir --" + file.getPath());
			File[] fileArr=file.listFiles();
			for(File f:fileArr) {
				getDir(f.getPath());
			}
		}else if(file.isFile()) {
			System.out.println("File--"+file.getPath());
		}else {
			throw new Exception(file.getPath());	
		}
	}
	
	@Test
	public void test()throws Exception {
		getDir("D:\\software\\JavaSoft\\eclipse\\eclipse");//这里的目录换成你自己电脑上的目录即可
	}
}

汉诺塔问题

定义:

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

代码:

import org.junit.jupiter.api.Test;

/**
 * 汉诺塔问题
 * @author wydream
 *
 */

public class Algorithm_4 {

	private final static String FROM="柱子A";
	private final static String MID="柱子B";
	private final static String TO="柱子C";
	
	/**
	 * 汉诺塔
     * func:
     * if n!=0 then          ;预定值
     * func(n-1, a, c, b)    ;将n-1个盘子由a移动到b,以c为辅助柱子(注意参数顺序)
     * move a[n] to c        ;将a上的最后一个盘子移动到c
     * func(n-1, b, a, c)    ;将n-1个盘子由b移动到c,以a为辅助柱子
     * endif                 ;完成
	 */
	public void move(int n,String from,String mid,String to) {
		if(n==1) {
			System.out.println("移动盘子 " + n + " 从 " + from + " 到 " + to);
		}else {
			move(n-1,from,to,mid);
			System.out.println("移动盘子 " + n + " 从 " + from + " 到 " + to);
			move(n-1,mid,from,to);
		}
	}
		
	@Test
	public void test() {
		move(3,FROM,MID,TO);
	}
	
}

二分法查找

概念:

二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。 二分法查找的思路如下: (1)首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。 (2)如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤(1)的操作。 (3)如果某一步数组为空,则表示找不到目标元素。

代码:

import org.junit.jupiter.api.Test;

/**
 *  
 * 二分法查找值
 * 一定是有序表,升序降序都可以
 * 原理就是找中间值
 *
 * @author wydream
 *
 */

public class Algorithm_5 {
	
	public int search(int []array,int start,int end ,int searchValue) {
		
		if(array!=null&&array.length>0) {
			int middle=(start+end)/2;
			int middleValue=array[middle];
			if(searchValue==middleValue) {
				return middle;
			}else if(searchValue<middleValue){
				//查询值小于中值,在中值前面再次搜索,缩小范围
				return search(array,start,middle-1,searchValue);
			}else {
				//查询值大于中值,在中值后面再次搜索,缩小范围
				return search(array,middle+1,end,searchValue);
			}
		}else {
			return -1;
		}
		
	}
	
	@Test
	public void test() {
		int[] arr= {2,3,6,9,13,18,20,22,24,29,30,45,67,88};
		System.out.println(search(arr, 0, arr.length-1, 20));
	}

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券