数学算法
# 数学算法
# 📋 学习目标
- 掌握基础数学概念在编程中的应用
- 理解数论基础知识
- 学会概率与组合数学
- 熟练解决数学相关编程问题
# 🔢 基础数学
# 最大公约数 (GCD)
// 欧几里得算法
public int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 递归版本
public int gcdRecursive(int a, int b) {
if (b == 0) {
return a;
}
return gcdRecursive(b, a % b);
}
# 最小公倍数 (LCM)
public int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
# 质数判断
public boolean isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
# 埃拉托斯特尼筛法
public List<Integer> sieveOfEratosthenes(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.add(i);
}
}
return primes;
}
# 🎲 组合数学
# 阶乘
public long factorial(int n) {
if (n <= 1) return 1;
long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
# 组合数 C(n, k)
public long combination(int n, int k) {
if (k > n - k) {
k = n - k; // 利用对称性
}
long result = 1;
for (int i = 0; i < k; i++) {
result = result * (n - i) / (i + 1);
}
return result;
}
# 帕斯卡三角形
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
row.add(1);
} else {
int val = triangle.get(i - 1).get(j - 1) +
triangle.get(i - 1).get(j);
row.add(val);
}
}
triangle.add(row);
}
return triangle;
}
# ⚡ 快速幂
public long quickPow(long base, long exp, long mod) {
long result = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
# 🔄 矩阵运算
# 矩阵乘法
public int[][] matrixMultiply(int[][] A, int[][] B) {
int m = A.length;
int n = A[0].length;
int p = B[0].length;
int[][] C = new int[m][p];
for (int i = 0; i < m; i++) {
for (int j = 0; j < p; j++) {
for (int k = 0; k < n; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
# 矩阵快速幂
public int[][] matrixPower(int[][] matrix, int n) {
int size = matrix.length;
int[][] result = new int[size][size];
// 初始化为单位矩阵
for (int i = 0; i < size; i++) {
result[i][i] = 1;
}
while (n > 0) {
if (n % 2 == 1) {
result = matrixMultiply(result, matrix);
}
matrix = matrixMultiply(matrix, matrix);
n /= 2;
}
return result;
}
# 🎯 经典问题
# 斐波那契数列
// 矩阵快速幂解法
public int fibonacci(int n) {
if (n <= 1) return n;
int[][] base = {{1, 1}, {1, 0}};
int[][] result = matrixPower(base, n - 1);
return result[0][0];
}
# 约瑟夫问题
public int josephus(int n, int k) {
int result = 0;
for (int i = 2; i <= n; i++) {
result = (result + k) % i;
}
return result;
}
# 卡特兰数
public int catalan(int n) {
if (n <= 1) return 1;
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i - 1 - j];
}
}
return dp[n];
}