DSA - 数学算法

更新于 2025/10/16 16:21:06

数学算法是用于解决与数据结构相关的数学问题的明确定义的程序。我们可以在竞技编程、数据科学和其他复杂的数学概念中看到它的应用。这些算法教会我们如何通过逻辑和高效的思考来解决给定的问题。

重要的数学算法

一些重要的数学算法是 −

欧几里得算法
埃拉托斯特尼筛法
二进制幂运算
模运算

这里是 − 的详细解释

欧几里得算法

欧几里得算法，也称为欧几里得算法，是一种用于计算两个给定整数的最大公约数 (GCD) 的方法。术语 GCD 是 最大公约数 的缩写。最大公约数 (GCD) 也称为最高公约数 (HCF)。它被定义为能够整除给定一组数字的最大整数。

假设给定一组整数 A 和 B。欧几里得算法计算它们的 GCD 负值如下：

如果 A 等于 0，且 B 为非零整数，则 GCD(A, B) 等于 B。
两个整数 A 和 B 的最大公约数 (GCD) 在用较大的整数减去较小的整数时保持不变。因此，重复此过程多次即可得出最大公约数 (GCD)。
递归计算 A mod B，当结果为 0 时，我们将得到最大公约数 (GCD)，即 B。

示例

在下面的示例中，我们将说明欧几里得算法的工作原理。

C C++ Java Python

#include <stdio.h>
int findGrtCmFact(int a, int b) {
   if (b == 0) {
      return a;
   } else {
      return findGrtCmFact(b, a % b);
   }
}
int main() {
   int valOne = 52;
   int valTwo = 28;
   printf("The GCD of %d and %d is: %d
", valOne, valTwo, findGrtCmFact(valOne, valTwo));
   return 0;
}

#include <iostream>
using namespace std;
int findGrtCmFact(int a, int b) {
   if (b == 0) {
      return a;
   } else {
      return findGrtCmFact(b, a % b);
   }
}
int main() {
   int valOne = 52;
   int valTwo = 28;
   cout << "The GCD of " << valOne << " and " << valTwo << " is: " << findGrtCmFact(valOne, valTwo) << endl;
   return 0;
}

public class GrtComFactr {
   public static int findGrtCmFact(int a, int b) {
      if (b == 0) {
         return a;
      } else {
         return findGrtCmFact(b, a % b);
      }
   }
   public static void main(String[] args) {
      int valOne = 52;
      int valTwo = 28;
      System.out.println("The GCD of " + valOne + " and " + valTwo + " is: " + findGrtCmFact(valOne, valTwo));
   }
}

def findGrtCmFact(a, b):
   if b == 0:
      return a
   else:
      return findGrtCmFact(b, a % b)

valOne = 52
valTwo = 28
print("The GCD of {} and {} is: {}".format(valOne, valTwo, findGrtCmFact(valOne, valTwo)))

输出

The GCD of 52 and 28 is: 4

埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种用于识别给定范围内素数的方法。查找素数的简单方法是遍历每个数字并检查当前数字是否为素数。然而，这并非最优解。

埃拉托斯特尼筛法的工作原理如下 −

从 2 到 N 的数字列表开始。首先，将所有这些数字视为潜在的素数。
从第一个素数 2 开始。将所有 2 的倍数标记为合数。继续处理列表中下一个未标记的数字 3。现在，将所有 3 的倍数标记为合数。
对 n 以内的所有数字完成此过程后，我们将只剩下未标记的素数。

示例

以下示例说明了埃拉托斯特尼筛法算法的工作原理。

C C++ Java Python

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
// method to find primes
void sieveOfEratos(int n) {
   // 最初假设所有值都是素数
   bool prm[n+1];
   memset(prm, true, sizeof(prm));
   // 循环遍历从 2 到 sqrt(n) 的所有数字
   for(int currPrm = 2; currPrm*currPrm <= n; currPrm++) {
      // 如果当前素数仍然为真，那么它就是素数
      if(prm[currPrm] == true) {
         // 更新当前素数的所有倍数
         for(int i = currPrm*currPrm; i <= n; i += currPrm)
            // 将因子标记为非素数
            prm[i] = false;  
      }
   }
   // 打印素数列表
   printf("前 50 个素数列表：
");
   for(int i = 2; i <= n; i++) {
      if(prm[i] == true)
         printf("%d ", i);  
   }
}
int main() {
   int lmt = 50; 
   sieveOfEratos(lmt);
   return 0;
}

#include <iostream>
#include <vector>
using namespace std;
class SvEratos {
public:
   // method to find primes
   static void sieveOfEratos(int n) {
      // 最初假设所有值都是素数
      vector<bool> prm(n+1, true);
      // 循环遍历从 2 到 sqrt(n) 的所有数字
      for(int currPrm = 2; currPrm*currPrm <= n; currPrm++) {
         // 如果当前素数仍然为真，那么它就是素数
         if(prm[currPrm] == true) {
            // 更新当前素数的所有倍数
            for(int i = currPrm*currPrm; i <= n; i += currPrm)
               // 将因子标记为非素数
               prm[i] = false;  
            }
      }
      // 打印素数列表
      cout << "前 50 个素数列表：" << endl;
      for(int i = 2; i <= n; i++) {
         if(prm[i] == true)
            cout << i << " ";  
      }
      cout << endl;
   }
};
int main() {
   int lmt = 50; 
   SvEratos::sieveOfEratos(lmt);
   return 0;
}

public class SvEratos {
   // method to find primes
   public static void sieveOfEratos(int n) {
      // 最初假设所有值都是素数
      boolean prm[] = new boolean[n+1];
      for(int i=0; i<=n; i++)
         prm[i] = true;
      // 循环遍历从 2 到 sqrt(n) 的所有数字
      for(int currPrm = 2; currPrm*currPrm <=n; currPrm++) {
         // 如果当前素数仍然为真，那么它就是素数
         if(prm[currPrm] == true) {
            // 更新当前素数的所有倍数
            for(int i = currPrm*currPrm; i <= n; i += currPrm)
               // 将因子标记为非素数
               prm[i] = false;  
         }
      }
      // 打印素数列表
      System.out.println("前 50 个素数列表：");
      for(int i = 2; i <= n; i++) {
         if(prm[i] == true)
            System.out.print(i + " ");  
      }
   }
   public static void main(String[] args) {
      int lmt = 50; 
      sieveOfEratos(lmt);
   }
}

def sieveOfEratos(n):
    # 最初假设所有值都是素数
    prm = [True for _ in range(n+1)]
    # 循环遍历从 2 到 sqrt(n) 的所有数字
    currPrm = 2
    while currPrm * currPrm <= n:
        # 如果当前素数仍然为真，那么它就是素数
        if prm[currPrm] == True:
            # 更新当前素数的所有倍数
            for i in range(currPrm * currPrm, n+1, currPrm):
                # 将因子标记为非素数
                prm[i] = False
        currPrm += 1
    
    # 打印素数列表
    print("前 50 个素数列表：")
    for i in range(2, n):
        if prm[i] == True:
            print(i, end=" ")

# 测试函数
lmt = 50
sieveOfEratos(lmt)

输出

前 50 个素数列表：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

二进制幂算法

二进制幂算法是用于计算给定数字幂的过程。解决此类问题（例如 n^p）的简单方法是将该数字与其自身相乘 p-1 次。然而，这是一个耗时且效率低下的过程。

除了上述方法，我们可以使用二进制幂算法，其工作原理如下：−

当任何给定数字的幂为 0 时，结果为 1。
如果数字本身为偶数，则使用以下等式：((n²)^p/2)，其中 n 是数字，p 是该给定数字的幂。
如果给定数字为奇数，则使用以下公式：(n*(n^(p-1)/2)²)。

示例

在此示例中，我们将展示二进制指数算法的工作原理。

C C++ Java Python

#include <stdio.h>
// function to calculate power
int bnryExp(int bs, int ex) {
   int output = 1;
   while (ex > 0) {
      if (ex % 2 == 1) {
         output *= bs;
      }
      // 底面平方
      bs *= bs; 
      // Divide power by 2
      ex >>= 1; 
   }
   // 返回存储在输出中的结果
   return output;
}
int main() {
   int bs = 3;
   int ex = 6;
   // 打印结果
   int result = bnryExp(bs, ex);
   printf("The output of %d to the power %d is: %d
", bs, ex, result);
   return 0;
}

#include <iostream>
using namespace std;
// method to calculate power
int bnryExp(int bs, int ex) {
   // 存储输出
   int output = 1;
   while (ex > 0) {
      if (ex % 2 == 1) {
         output *= bs;
      }
      // 底面平方
      bs *= bs; 
      // Divide power by 2
      ex /= 2; 
   }
   // 返回存储在输出中的结果
   return output;
}
int main() {
   int bs = 3;
   int ex = 6;
   int result = bnryExp(bs, ex);
   // 打印结果
   cout << "The output of " << bs << " to the power " << ex << " is: " << result << endl;
   return 0;
}

public class Exponentiation {
    // method to calculate power
    public static int bnryExp(int bs, int ex) {
        // 存储输出
        int output = 1;
        while (ex > 0) {
            if (ex % 2 == 1) {
                output *= bs;
            }
            // 底面平方
            bs *= bs;
            // Divide power by 2
            ex /= 2;
        }
        // 返回存储在输出中的结果
        return output;
    }
    public static void main(String[] args) {
        int bs = 3;
        int ex = 6;
        // 打印结果
        System.out.println("The output of " + bs + " to the power " + ex + " is: " + bnryExp(bs, ex));
    }
}

# method to calculate power
def bnryExp(bs, ex):
   # 存储输出
   output = 1
   while ex > 0:
      if ex % 2 == 1:
         output *= bs
      bs *= bs  
      ex //= 2  
   return output

bs = 3
ex = 6
result = bnryExp(bs, ex)
print(f"The output of {bs} to the power {ex} is: {result}")

输出

The output of 3 to the power 6 is: 729

模运算

模运算是一组适用于计算模表达式的规则。在竞技编程中处理大数时，这一概念非常重要。模运算的核心思想是求一个数除以另一个数后的余数。

模运算的重要性质如下 −

(m mod n) mod n 等于 m mod n
(m*n) mod m 等于 0
(P / Q) mod m ≠ ((P mod m) / (Q mod m)) mod m
(P + Q) mod m = ((P mod m) + (Q mod m)) mod m
(P – Q) mod m = ((P mod m) – (Q mod m) + m) mod m
(P * Q) mod m = ((P mod m) * (Q mod m)) mod m

示例

以下示例演示了模运算的工作原理。

C C++ Java Python

#include <stdio.h>
// function to perform addition
int modAddition(int valOne, int valTwo, int mod) {
   // 处理负值
   if (valOne < 0) {
      valOne = (valOne % mod + mod) % mod;
   }
   if (valTwo < 0) {
      valTwo = (valTwo % mod + mod) % mod;
   }
   // addition
   int sum = (valOne + valTwo) % mod;
   // 确保输出非负
   return (sum + mod) % mod;
}
int main() {
   int valOne = 22;
   int valTwo = 26;
   int mod = 5;
   int output = modAddition(valOne, valTwo, mod);
   printf("Modular addition of %d and %d modulo %d is: %d
", valOne, valTwo, mod, output);
   return 0;
}

#include <iostream>
using namespace std;
int modAddition(int valOne, int valTwo, int mod) {
   // 处理负值
   if (valOne < 0) {
      valOne = (valOne % mod + mod) % mod;
   }
   if (valTwo < 0) {
      valTwo = (valTwo % mod + mod) % mod;
   }
   // addition
   int sum = (valOne + valTwo) % mod;
   // 确保结果非负
   return (sum + mod) % mod;
}
int main() {
   int valOne = 22;
   int valTwo = 26;
   int mod = 5;
   int output = modAddition(valOne, valTwo, mod);
   cout << "Modular addition of " << valOne << " and " << valTwo << " modulo " << mod << " is: " << output << endl;
  return 0;
}

public class ModAdd {
    public static int modAddition(int valOne, int valTwo, int mod) {
        // 处理负值
        if (valOne < 0) {
            valOne = (valOne % mod + mod) % mod;
        }
        if (valTwo < 0) {
            valTwo = (valTwo % mod + mod) % mod;
        }
        // addition
        int sum = (valOne + valTwo) % mod;
        // 确保输出非负
        return (sum + mod) % mod;
    }
    public static void main(String[] args) {
        int valOne = 22;
        int valTwo = 26;
        int mod = 5;
        int output = modAddition(valOne, valTwo, mod);
        System.out.println("Modular addition of " + valOne + " and " + valTwo + " modulo " + mod + " is: " + output);
    }
}

def mod_addition(val_one, val_two, mod):
  # 处理负值
  if val_one < 0:
    val_one = (val_one % mod + mod) % mod
  if val_two < 0:
    val_two = (val_two % mod + mod) % mod

  # addition 
  sum = (val_one + val_two) % mod
  # 确保输出非负
  return (sum + mod) % mod

val_one = 22
val_two = 26
mod = 5
output = mod_addition(val_one, val_two, mod)
print(f"Modular addition of {val_one} and {val_two} modulo {mod} is: {output}")

输出

Modular addition of 22 and 26 modulo 5 is: 3

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

DSA - 数学算法

重要的数学算法

欧几里得算法

示例

输出

埃拉托斯特尼筛法

示例

输出

二进制幂算法

示例

输出

模运算

示例

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！