斐波那契数列
定义：
- 斐波那契数列指的是这样一个数列 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));
}
}