0%

基本算法

算法基本使用

最大公约数

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

若 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之后的余数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}
}
}

递推

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

如 斐波那契数列

1
2
3
4
5
6
7
8
9
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);
}

递归

进行进制转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);
}

分治

分而治之,把一个复杂的问题分解成很多规模较小的子问题,然后解决这些子问题,把解决的子问题合并起来,大问题就解决了

穷举

把所有情况都列举出来

贪婪算法

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

找零钱示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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());
}
}

回溯算法

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

八皇后示例