递推算法基本思想
递推算法是通过已知条件,利用特定关系得出中间结论,直至得到最后结果的算法。递推算法按照一定的规律来计算序列中的每一项,通常是通过计算机器前一项(或前几项)的值来推出当前项的值。
示例(斐波那契数列):
public class Fibonacci { | |
public static int fibonacci(int n) { | |
if (n <= 1) { | |
return n; | |
} | |
int a = 0, b = 1, c; | |
for (int i = 2; i <= n; i++) { | |
c = a + b; | |
a = b; | |
b = c; | |
} | |
return b; | |
} | |
public static void main(String[] args) { | |
System.out.println(fibonacci(10)); // 输出第10项斐波那契数列的值 | |
} | |
} |
递归算法思想
递归算法是一种直接或间接地调用自身的算法。它将问题分解为更小的子问题,然后递归地求解子问题,最后将子问题的解组合起来,形成原问题的解。
示例(阶乘函数):
public class Factorial { | |
public static int factorial(int n) { | |
if (n <= 1) { | |
return 1; | |
} | |
return n * factorial(n - 1); // 递归调用自身 | |
} | |
public static void main(String[] args) { | |
System.out.println(factorial(5)); // 输出5的阶乘值 | |
} | |
} |
分治算法思想
分治算法是将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。递归地解决这些子问题,然后将子问题的解合并起来,形成原问题的解。
示例(归并排序):
public class MergeSort { | |
public static void mergeSort(int[] arr, int left, int right) { | |
if (left < right) { | |
int mid = (left + right) / 2; | |
mergeSort(arr, left, mid); // 递归解决左半部分 | |
mergeSort(arr, mid + 1, right); // 递归解决右半部分 | |
merge(arr, left, mid, right); // 合并左右两部分 | |
} | |
} | |
// 合并两个有序数组 | |
private static void merge(int[] arr, int left, int mid, int right) { | |
int[] temp = new int[right - left + 1]; | |
int i = left, j = mid + 1, k = 0; | |
while (i <= mid && j <= right) { | |
if (arr[i] <= arr[j]) { | |
temp[k++] = arr[i++]; | |
} else { | |
temp[k++] = arr[j++]; | |
} | |
} | |
while (i <= mid) { | |
temp[k++] = arr[i++]; | |
} | |
while (j <= right) { | |
temp[k++] = arr[j++]; | |
} | |
// 将temp中的元素复制回arr中 | |
for (i = left, k = 0; i <= right; i++, k++) { | |
arr[i] = temp[k]; | |
} | |
} | |
public static void main(String[] args) { | |
int[] arr = {38, 27, 43, 3, 9, 82, 10}; | |
mergeSort(arr, 0, arr.length - 1); | |
for (int i : arr) { | |
System.out.print(i + " "); | |
} | |
} | |
} |
概率算法思想
概率算法是基于一定的概率性结论来求解问题的算法。这种算法并不总是给出确定的答案,而是给出一个答案的概率或期望。
示例(模拟随机漫步)
import java.util.HashMap; | |
import java.util.Map; | |
import java.util.Random; | |
public class RandomWalk { | |
// 模拟随机漫步的函数 | |
public static Map<Integer, Integer> simulateRandomWalk(int steps, double rightStepProbability) { | |
Random rand = new Random(); | |
int position = 0; | |
Map<Integer, Integer> positionCounts = new HashMap<>(); // 存储位置出现的次数 | |
// 初始化位置计数为0 | |
for (int i = -steps; i <= steps; i++) { | |
positionCounts.put(i, 0); | |
} | |
for (int i = 0; i < steps; i++) { | |
if (rand.nextDouble() < rightStepProbability) { | |
position++; // 朝右走一步 | |
} else { | |
position--; // 朝左走一步 | |
} | |
// 更新位置计数 | |
positionCounts.put(position, positionCounts.getOrDefault(position, 0) + 1); | |
} | |
return positionCounts; | |
} | |
// 主函数,模拟并输出结果 | |
public static void main(String[] args) { | |
int steps = 1000; // 设定步数 | |
double rightStepProbability = 0.5; // 设定向右走的概率 | |
Map<Integer, Integer> positionCounts = simulateRandomWalk(steps, rightStepProbability); | |
// 输出结果 | |
for (Map.Entry<Integer, Integer> entry : positionCounts.entrySet()) { | |
System.out.println("Position " + entry.getKey() + " occurred " + entry.getValue() + " times."); | |
} | |
} | |
} |
在这个示例中,simulateRandomWalk
函数模拟了随机漫步过程,并统计了每个位置出现的次数。主函数 main
设定了步数和向右走的概率,并调用了 simulateRandomWalk
函数进行模拟,最后输出了每个位置出现的次数。由于随机性,每次运行程序得到的结果都会有所不同。这个示例展示了概率算法的一个基本思想:通过模拟大量随机事件来估计某个事件发生的概率或期望。