文章目录

  上周学习了分治与递归的初步,莫名的有种递归恐惧感。自己调自己什么的,高中那会儿学VB学到递归的时候就觉得不正常,后来自己写代码的时候也是能不用递归就不用。

  分治,没学过感觉好高大上啊,结果英文一来divide and conquer,字表其意,翻译也是屌,分而治之。

  上节课主要涉及到了汉诺塔、快排、fibonacci数列什么的,实现一下。

  经典的汉诺塔:

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
import java.util.Scanner;

/**
* 汉诺塔问题的简单实现
* @author jrhu05
*
*/
public class HanoiTower {
public static void main(String[] args) {
System.out.println("input the N:");
Scanner cin=new Scanner(System.in);
int n=cin.nextInt();
hanoi(n, 'A', 'B', 'C');
}
//解决的问题是将i个盘子从A移到C
static void hanoi(int i,char A, char B,char C){
if (i==1) {
move(i, A, C);
}else {
hanoi(i-1, A, C, B);
move(i, A, C);
hanoi(i-1, B, A, C);
}
}
static void move(int i,char x, char y){
System.out.println(i+" from "+x+" to "+y);
}
}

  快速排序:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

import java.util.Arrays;

/**
* 快排的手动实现
* 以及快排的改进(随机化版本)的实现
* @author jrhu05
*
*/
public class QuickSort {
public static void main(String[] args) {
int[] a={2,8,7,1,3,5,6,4};
quickSort(a, 0, a.length-1);
System.out.println(Arrays.toString(a));
}
static void quickSort(int[] A,int p,int r){
if (p<r) {
int q=partition(A, p, r);
quickSort(A, p, q-1);
quickSort(A, q+1, r);
}
}
static int partition(int[] A, int p, int r){
int x=A[r];//把最后一个元素设为主元
int i=p-1;
for(int j=p;j<=r-1;j++){
if (A[j]<=x) {
i++;
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
int temp=A[i+1];
A[i+1]=A[r];
A[r]=temp;
return i+1;
}

static void randomQuickSort(int[] A,int p,int r){
if (p<r) {
int q=randomPartition(A, p, r);
randomQuickSort(A, p, q-1);
randomQuickSort(A, q+1, r);
}
}

static int randomPartition(int[] A, int p, int r){
int randomMain=(int)(Math.random()*r);
int x=A[randomMain];//随机一个元素设为主元
int i=p-1;
for(int j=p;j<=r-1;j++){
if (A[j]<=x) {
i++;
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
int temp=A[i+1];
A[i+1]=A[randomMain];
A[randomMain]=temp;
return i+1;
}
}

   Fibonacci数列的非递归实现(o(n)):

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
import java.util.Scanner;

/**
* 斐波那契数列的自底向上非递归算法
* @author jrhu05
*
*/
public class Fibonacci {
public static void main(String[] args) {
System.out.println("input the N:");
Scanner cin=new Scanner(System.in);
int n=cin.nextInt();
int[] fibonacci=new int[n];
fibonacci[0]=fibonacci[1]=1;
System.out.println(fibonacci(n, fibonacci));
}

static int fibonacci(int index, int[] fibonacci){
if (index==1||index==2) {
return 1;
}else {
for (int i = 2; i < fibonacci.length; i++) {
fibonacci[i]=fibonacci[i-1]+fibonacci[i-2];
}
return fibonacci[index-1];
}

}
}

下节课继续是分治,问题是经典的最近点对问题,下周继续。


如果觉得文章很有趣或对你带来了帮助,欢迎请我喝杯咖啡哦~

文章目录