汉诺塔和斐波那契数量实现源码

shinezejian · shinezejian · commit ef3fb9888ae2 · 2016-12-12T11:54:18.000+08:00
diff --git a/src/com/zejian/structures/recursion/Fibonacci.java b/src/com/zejian/structures/recursion/Fibonacci.java
@@ -0,0 +1,92 @@
+package com.zejian.structures.recursion;
+
+import java.math.BigInteger;
+
+/**
+ * Created by zejian on 2016/12/11.
+ * Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
+ * 斐波那契数列的实现
+ */
+public class Fibonacci  {
+
+    /**
+     * 斐波那契数列的实现
+     * 0,1,1,2,3,5,8,13,21......
+     * @param day
+     */
+    public long fibonacci(int day){
+
+        if(day==0){ //F(0)=0
+            return 0;
+        }else if (day==1||day==2){//F(1)=1
+            return 1;
+        }else {
+           return fibonacci(day-1)+fibonacci(day-2); //F(n)=F(n-1)+F(n-2)
+        }
+    }
+
+    /**
+     * 更为简洁的写法
+     * @param day
+     * @return
+     */
+    public long fib(int day) {
+        return day== 0 ? 0 : (day== 1 || day==2 ? 1 : fib(day - 1) + fib(day - 2));
+    }
+
+//    //1,2,3,5,8,13,21......
+//    BigInteger fib_i(int a, int b , int n)
+//    {
+//        if (n==3){
+//            return BigInteger.valueOf(a).add(BigInteger.valueOf(b));
+//        }else {
+//            return fib_i(b ,a+b, n-1);
+//        }
+//    }
+
+    //BigInteger可以防止数据异常
+//BigInteger 任意大的整数，原则上是，只要你的计算机的内存足够大，可以有无限位的
+// 递推实现方式（迭代的方式效率高，时间复杂度O(n)）
+    public  BigInteger fibonacciN(int n){
+        if (n == 1) {
+            return new BigInteger("0");
+        }
+        //f(0)=0;
+        BigInteger n1 = new BigInteger("0");
+        //f(1)=1;
+        BigInteger n2 = new BigInteger("1");
+        //记录最终值f(n)
+        BigInteger sn = new BigInteger("0");
+        for (int i = 0; i < n - 1; i++) {
+            sn = n1.add(n2);//相加
+            n1 = n2;
+            n2 = sn;
+        }
+        return sn;
+    }
+
+    // 与上述相同的递推实现方式 ，使用long返回值，当n过大会造成数据溢出，计算结果可能是一个未知的负数，因此建议使用BigInteger
+    public static long fibonacciNormal(int n){
+        if(n <= 2){
+            return 1;
+        }
+        long n1 = 1, n2 = 1, sn = 0;
+        for(int i = 0; i < n - 2; i ++){
+            sn = n1 + n2;
+            n1 = n2;
+            n2 = sn;
+        }
+        return sn;
+    }
+
+    //测试
+    public static void main(String[] args){
+        Fibonacci fibonacci=new Fibonacci();
+        long now =System.currentTimeMillis();
+//        System.out.println("第11天动物数量为:"+ fibonacci.fib_i(1,1,50));
+//        System.out.println("第11天动物数量为:"+ fibonacci.fib(50));//12586269025
+        System.out.println("第11天动物数量为:"+ fibonacci.fibonacciNormal(100));//12586269025
+//        System.out.println("第11天动物数量为:"+ fibonacci.fibonacci(10));
+        System.out.println("执行第500天的时间为:"+(System.currentTimeMillis()-now));
+    }
+}
diff --git a/src/com/zejian/structures/recursion/HanoiRecursion.java b/src/com/zejian/structures/recursion/HanoiRecursion.java
@@ -0,0 +1,71 @@
+package com.zejian.structures.recursion;
+
+/**
+ * Created by zejian on 2016/12/11.
+ * Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
+ * 汉诺塔的递归算法实现
+ */
+public class HanoiRecursion {
+
+    /**
+     * @param n 汉诺塔的层数
+     * @param x x柱 起点柱(A)
+     * @param y y柱 目标柱(B)
+     * @param z z柱 中转柱(C)
+     * 其中 A B C 只是作为辅助思考
+     */
+    public void hanoi(int n, char x ,char y ,char z){
+
+        //H(0)=0
+        if (n==0){
+            //什么也不做
+        }else {
+            //H(n)=H(n-1) + 1 H(n-1)
+            //将n-1个圆盘从x移动到z,y为中转柱
+            hanoi(n-1,x,z,y); //----------------------->解出n-1层汉诺塔:H(n-1)
+
+            //移动最大圆盘到目的柱
+            System.out.println(x+"->"+y);//------------> 1
+
+            //将n-1个圆盘从z移动到y,x为中转柱
+            hanoi(n-1,z,y,x);//------------------------>解出n-1层汉诺塔:H(n-1)
+        }
+
+    }
+
+    /**
+     * @param n 汉诺塔的层数
+     * @param x x柱 起点柱(A)
+     * @param y y柱 目标柱(B)
+     * @param z z柱 中转柱(C)
+     * 其中 A B C 只是作为辅助思考
+     */
+    public int hanoiCount(int n, char x ,char y ,char z){
+        int moveCount=0;
+        //H(0)=0
+        if (n==0){
+            //什么也不做
+            return 0;
+        }else {
+            //H(n)=H(n-1) + 1 H(n-1)
+            //将n-1个圆盘从x移动到z,y为中转柱
+            moveCount += hanoiCount(n-1,x,z,y); //------------->解出n-1层汉诺塔:H(n-1)
+
+            //移动最大圆盘到目的柱
+            moveCount += 1; //---------------------------------> 1
+
+            //将n-1个圆盘从z移动到y,x为中转柱
+            moveCount +=hanoiCount(n-1,z,y,x);//--------------->解出n-1层汉诺塔:H(n-1)
+        }
+
+        return moveCount;
+    }
+    //测试
+    public static void main(String[] args){
+        HanoiRecursion hanoi=new HanoiRecursion();
+        System.out.println("moveCount="+hanoi.hanoiCount(6,'A','B','C'));
+
+        hanoi.hanoi(3,'A','B','C');
+    }
+
+}
