如何设计递归算法
- 确定递归公式
- 确定边界条件
1. Fibonacci
public static int fibonacci(int n) {
if(n == 0 || n == 1) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
2. 快速排序(Quick Sort)
public static int partition(int[] a, int p, int q) {
int pivot = a[q];
int index = 0;
for(int i = p; i < q; i++) {
if(a[i] <= pivot) {
int temp = a[i];
a[i] = a[index];
a[index] = temp;
index++;
}
}
int temp = a[index];
a[index] = pivot;
a[q] = temp;
return index;
}
public static void quickSort(int[]a, int p, int q) {
if(p < q) {// 如果p大于等于r 那么就程序不执行
int mid = partition(a, p, q);
quickSort(a, p, mid-1);
quickSort(a, mid+1, q);
}
}
3. 归并排序(Merge Sort)
public static void merge(int[] a, int left, int mid, int right) {
int m = mid - left + 1;
int n = right - mid;
int[] leftArr = new int[m+1];
int[] rightArr = new int[n+1];
for(int i = 0; i < m; i++) {
leftArr[i] = a[left+i];
}
for(int i = 0; i < n; i++) {
rightArr[i] = a[mid+i+1];
}
leftArr[m] = Integer.MAX_VALUE;
rightArr[n] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
for(int k = left; k <= right; k++) {
if(leftArr[i] <= rightArr[j]) {
a[k] = leftArr[i++];
} else {
a[k] = rightArr[j++];
}
}
}
public static void mergeSort(int[] a, int left, int right) {
if(left < right) { //当left>=right 说明子数组最多只有一个元素,已经排好序了
int mid = (left + right) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid+1, right);
merge(a, left, mid, right);
}
}
4. 二分查找(Binary Search)
public static int binarySearch(int[] arr, int key, int left, int right) {
if(left > right)
return -1;
int mid = (left + right) / 2;
if(arr[mid] == key) {
return mid;
} else if(arr[mid] > key) {
return binarySearch(arr, key, left, mid-1);
} else {
return binarySearch(arr, key, mid+1, right);
}
}
5. 全排列
6. 欧几里得算法(辗转相除法)
/*
* m >= n
*/
public static int gcd(int m, int n) {
if(n == 0) {
return m;
} else {
return gcd(n, m%n);
}
}
7. 1加到n累加
public static int sum(int n) {
if(n == 1)
return 1;
else
return n+sum(n-1);
}
8. 求数组中的最大值
public static int max(int[] a, int n) {
if(n == 0)
return a[0];
else {
if(a[n] > max(a, n-1)) {
return a[n];
} else {
return max(a, n-1);
}
}
}
public static int maximum(int[] a, int low, int high) {
int delt = high - low + 1;
if(delt == 1) {
return a[low];
} else if(delt == 2) {
return a[low] > a[high]? a[low]: a[high];
} else {
int mid = (low + high) / 2;
int left = maximum(a, low, mid);
int right = maximum(a, mid+1, high);
return left > right? left: right;
}
}
9. 八皇后
网友评论