分享一些有意思的算法

人民币数字转化成大写

package com.yaolong;

/**
 * @ProjectName: devin
 * @Package: com.yaolong
 * @ClassName: ConvertChinese
 * @Author: liuyaolong
 * @Description: 人民币数字转化成大写
 * @Version: 1.0
 */
public class ConvertChinese {

    public static void main(String[] args) {
        System.out.println(conver(564981));
    }

    private static final char [] data = new char[]{'零','壹','贰','叁','肆','伍','陆','柒','捌','玖'};
    private static final char [] untis = new char[]{'元','拾','佰','仟','万','拾','佰','仟','亿'};

    private static String conver(int money){

        StringBuffer sb = new StringBuffer();
        int unti = 0;
        while (money != 0){
            sb.insert(0,untis[unti++]);
            int number = money%10;
            sb.insert(0,data[number]);
            money/=10;
        }
        return sb.toString();
    }
}

篮球掉落 （记得当时面试别人的时候有用到这道题，手动滑稽）

package com.yaolong;

/**
 * @ProjectName: devin
 * @Package: com.yaolong
 * @ClassName: BasketballBounce
 * @Author: liuyaolong
 * @Description: 篮球反弹
 * @Version: 1.0
 */
public class BasketballBounce {

    /**
     * 一球从100米高度*落下，每次落地后反跳回原高度的一半；再落下，求它在 第10次落地时，
     * 共经过多少米？第10次反弹多高？
     * @param args
     */
    public static void main(String[] args) {

         double h = 100;
         double l = 100;

         for(int i = 1;i <= 10; i++){
             h = h/2;
             l += 2*h;
             System.out.println("第"+i+"次共经过"+l+"米,反弹高度为"+h);
         }
    }
}

生兔子

package com.yaolong;

import java.util.Scanner;

/**
 * @ProjectName: devin
 * @Package: com.yaolong
 * @ClassName: RabbitProcedure
 * @Author: liuyaolong
 * @Description: 经典生兔子算法
 * @Version: 1.0
 */
public class Rabbit {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int month = scanner.nextInt();
        System.out.println(calculate(month));
        scanner.close();;
    }

    /**
     * 古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子对数为多少？
     * 规律：a[n]=a[n-1]+a[n-1]
     * @param n 月份
     * @return
     */
    private static int calculate(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        return calculate(n-1)+calculate(n-2);
    }
}

水仙花数

package com.yaolong;

/**
 * @ProjectName: devin
 * @Package: com.yaolong
 * @ClassName: ArmstrongnNumber
 * @Author: liuyaolong
 * @Description: 水仙花数
 * @Version: 1.0
 */
public class ArmstrongnNumber {

    public static void main(String[] args) {
        for (int i = 100 ; i < 1000; i++){
            if(IsArmstrongnNumber(i)){
                System.out.println(i);
            }
        }
    }

    /**
     * 判断当前数是否为水仙花数
     * @param value
     * @return
     */
    private static boolean IsArmstrongnNumber(int value){

        int unitsDigit = value%10;//个位数
        int tensDigit = value/10%10;//十位数
        int hundredsDigit = value/100;//百位数

        if(value == (unitsDigit*unitsDigit*unitsDigit)+(tensDigit*tensDigit*tensDigit)+(hundredsDigit*hundredsDigit*hundredsDigit)){
            return true;
        }
        return false;
    }
}

区间素数

package com.yaolong;

/**
 * @ProjectName: devin
 * @Package: com.yaolong
 * @ClassName: PrimzahlProcedure
 * @Author: liuyaolong
 * @Description: 素数算法
 * @Version: 1.0
 */
public class Primzahl {

    public static void main(String[] args) {
        //判断1-100之间有多少个素数，并输出所有素数。
        int count = 0;
        for(int i = 1; i < 101; i++){
            if(IsPrimzahl(i)){
                count++;
                System.out.println(i);
            }
        }
        System.out.println("素数的整数"+count);
    }

    /**
     * 判断当前值是否为素数
     * @param value
     * @return
     */
    private static boolean IsPrimzahl(int value){
        for(int i = 2; i <= Math.sqrt(value); i++){
            if(value % i == 0){
                return false;
            }
        }
        return true;
    }
}

递归算法

package com.yaolong;

public class Recursion{
    
    //基本思想：当过程或函数的定义中，其内部操作又直接或间接地出现对自身程序的引用，则称这样的程序嵌套定义为递归定义
    public static void main(String[] args) {
        System.out.println(Recursion.duckSale(2, 7));
    }

    /**
     * 递归求和 1+2+3....输入值得和
     */
    public static int recursionSum(int n) {
        if (n > 0) {
            return n + Recursion.recursionSum(n - 1);
        } else {
            return 0;
        }
    }

    /**
     * 递归阶乘 n*(n-1)*(n-2)*(n-3)*...*1
     */
    public static int recursionFactorial(int n) {

        if (n == 1)
            return 1;
        return n * Recursion.recursionFactorial(n - 1);
    }

    /**
     * 题意：一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。
     * 这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
     * @Description: 卖鸭子递归算法
     * @param num 每天所剩鸭子的数量
     * @param count 村庄的个数
     * @return
     * @return int 返回类型
     * @throws
     */
    public static int duckSale(int num, int count) {
        num= (num + 1) * 2;
        System.out.println("第" + count + "个村庄卖出鸭子的数量是：" + num);
        count--;
        if (count > 0) {
            Recursion.duckSale(num, count);
        }
        return num;
    }

}

二分查找法（递归和非递归）

package com.yaolong;

public class Dichotomy{

    //基本思想：基于有序，从数列中间开始查找，如果是该元素正好是目标元素则结束，如小于/大于中间元素则在对应区域重新查找
    public static void main(String[] args) {
        final int[] arr= { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
        System.out.println(Dichotomy.search(arr, 10));
        System.out.println(Dichotomy.search(arr, 12));
       System.out.println(Dichotomy.searchRecursion(arr, 0, arr.length - 1, 6));
    }

    /**
     * 二分查找法（非递归）
     */
    public static int search(int[] arr, int value) {

        int start= 0;
        int end= arr.length - 1;

        while (start <= end) {
            final int middle= (start + end) / 2;
            if (value > arr[middle]) {
                start= middle + 1;
            } else if (value < arr[middle]) {
                end= middle - 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

    /**
     * 二分查找法（递归）
     */
    public static int searchRecursion(int[] arr, int start, int end, int value) {

        if (start > end)
            return -1;
        final int middle= (start + end) >> 1;
        if (value > arr[middle]) {
            Dichotomy.searchRecursion(arr, middle + 1, end, value);
        } else if (value < arr[middle]) {
            Dichotomy.searchRecursion(arr, start, middle - 1, value);
        }
        return middle;
    }

}

冒泡算法

package com.yaolong;

public class Bubble{

    //基本思想：每次比较相邻的两个元素，如果顺序错误就交换
    public static void main(String[] args) {

        final int arr[]= { 2, 56, 23, 46, 52, 12, 79, 31, 20, 35 };
        int temp= 0;
        for (int i= 0; i < arr.length - 1; i++) {
            for (int j= arr.length - 1; j > i; j--) {
                if (arr[j - 1] > arr[j]) {
                    temp= arr[j - 1];
                    arr[j - 1]= arr[j];
                    arr[j]= temp;
                }
            }
        }
        for (final int i : arr) {
            System.out.println(i);
        }
    }

}