基本算法

算法基本使用

最大公约数

最大公约数求取，使用欧几里得算法

若 mod(m,n)!=0 则 g(m,n) = g(n,mod(m,n))

若mod(m,n)=0 则g(m,n) = n

mod(m,n)表示m除n之后的余数

public int maxCommonDisvisor(int m, int n) {
        int temp = 0;
        if (m < n) {
            while (true) {
                if (n % m == 0) {
                    return m;
                }
                temp = n % m;
                n = m;
                m = temp;
            }
        } else {
            while (true) {
                if (m % n == 0) {
                    return n;
                }
                temp = m % n;
                m = n;
                n = temp;
            }
        }
    }

最大公约数还有个简单地方式，就是两个数中较大的数减去较小的数，反复执行，直到两个数相等

最小公倍数是两个数相乘，除以最大公约数

递推

递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。
递推算法分为顺推和逆推两种

如 斐波那契数列

public void fs(int num) {
        int[] fs = new int[num];
        fs[0] = 1;
        fs[1] = 1;
        for (int i = 2; i < num; i++) {
            fs[i] = fs[i - 1] + fs[i - 2];
        }
        Arrays.stream(fs).forEach(System.out :: println);
    }

递归

递归算法是种很常见的算法，可以简化代码编写，提高程序可读性，其通过在程序中不断的反复调用自身来达到求解问题的方法

示例：进行进制转换

public static void main(String[] args) {
        System.out.println(Integer.toBinaryString(10));
        StringBuilder stringBuilder = new StringBuilder();
        tenToTwo(10, stringBuilder);
        System.out.println(stringBuilder.reverse().toString());
    }

    public static int tenToTwo(int ten, StringBuilder sb) {
        if (ten == 0) {
            return 0;
        }
        sb.append(ten % 2);
        return tenToTwo(ten / 2, sb);
    }

分治

分治算法，分而治之，是一种化繁为简的算法，将问题简化逐步得到结果

穷举

穷举是最简单的一种算法，依赖于计算机的强大计算能力，穷尽每一种可能的情况，从而达到求解问题的目的，但是其效率并不高

如鸡兔同笼问题

public static void main(String[] args) {
    System.out.println("鸡兔同笼问题");
    System.out.println("输入头数：");
    Scanner scanner = new Scanner(System.in);
    int head = scanner.nextInt();
    System.out.println("输入脚数：");
    int foot = scanner.nextInt();
    boolean result = qiongju(head, foot);
    if(result){
        System.out.println("鸡"+chicken+"只,兔"+rabbit+"只");
    } else {
        System.out.println("无解");
    }
}

static int chicken,rabbit; // 鸡的数量、兔子的数量

public static boolean qiongju(int head,int foot){

    boolean result = false;

    for(int i = 0; i <= head;i++){
        int j = head - i;
        if(i *2 + j * 4 == foot){
            chicken = i;
            rabbit = j;
            result = true;
            break;
        }
    }

    return result;
}

贪婪算法

贪婪算法不追求最优解，只希望得到较为满意解的方法，一般可以快速得到满意的解，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。通过局部最优选择来达到全局最优解。

找零钱示例

public class Main4 {
    int[] value = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1};

    public static void main(String[] args) {
        // 面值单位为分  100元、50元、20元、10元、5元、2元、1元、5角、2角、1角、5分、2分、1分
        Main4 m = new Main4();

        m.exchange(1748);

    }

    /**
     * 单位为分
     *
     * @param n
     */
    public void exchange(int n) {
        StringBuilder sb = new StringBuilder();
        int m = 0;
        for (int i = 0; i < value.length; i++) {
            if (n < value[i]) {
                continue;
            }
            m = n / value[i];
            n = n - m * value[i];
            if (value[i] > 100) {
                sb.append(m).append("张").append(value[i] / 100).append("元,");
            } else if (value[i] > 10) {
                sb.append(m).append("张").append(value[i] / 10).append("角,");
            } else {
                sb.append(m).append("张").append(value[i]).append("分,");
            }
        }
        if (sb.indexOf(",") > 0 && sb.lastIndexOf(",") == sb.length() - 1) {
            sb.deleteCharAt(sb.length() - 1);
        }
        System.out.println(sb.toString());
    }
}

回溯算法

为了得到问题的解，先选择某一种可能情况进行试探，在试探过程中，一旦发现原本选择的假设情况是错误的，就退回一步选择，继续向另一个方向试探，如此反复，得到结果

八皇后示例