DSA - 数学算法

上一页
下一页

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

重要的数学算法

一些重要的数学算法包括：

  • 欧几里得算法

  • 埃拉托斯特尼筛法

  • 二进制幂运算

  • 模运算

以下是详细解释：

欧几里得算法

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

假设，给定的一组整数为A和B。以下是欧几里得算法如何找到它们的GCD：

  • 如果A等于0且B是非零整数，则GCD(A, B)为B。

  • 两个整数A和B的最大公约数在从较大数中减去较小数时保持不变。因此，重复此过程多次将得到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\n", 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) {
   // initially assuming all values are prime
   bool prm[n+1];
   memset(prm, true, sizeof(prm));
   // Loop over all numbers from 2 to sqrt(n)
   for(int currPrm = 2; currPrm*currPrm <= n; currPrm++) {
      // If current prime is still true, then it is a prime
      if(prm[currPrm] == true) {
         // Update all multiples of current prime
         for(int i = currPrm*currPrm; i <= n; i += currPrm)
            // Marking factor as not prime
            prm[i] = false;  
      }
   }
   // to print the list of prime numbers
   printf("List of first 50 prime numbers: \n");
   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) {
      // initially assuming all values are prime
      vector<bool> prm(n+1, true);
      // Loop over all numbers from 2 to sqrt(n)
      for(int currPrm = 2; currPrm*currPrm <= n; currPrm++) {
         // If current prime is still true, then it is a prime
         if(prm[currPrm] == true) {
            // Update all multiples of current prime
            for(int i = currPrm*currPrm; i <= n; i += currPrm)
               // Marking factor as not prime
               prm[i] = false;  
            }
      }
      // to print the list of prime numbers
      cout << "List of first 50 prime numbers: " << 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) {
      // initially assuming all values are prime
      boolean prm[] = new boolean[n+1];
      for(int i=0; i<=n; i++)
         prm[i] = true;
      // Loop over all numbers from 2 to sqrt(n)
      for(int currPrm = 2; currPrm*currPrm <=n; currPrm++) {
         // If current prime is still true, then it is a prime
         if(prm[currPrm] == true) {
            // Update all multiples of current prime
            for(int i = currPrm*currPrm; i <= n; i += currPrm)
               // Marking factor as not prime
               prm[i] = false;  
         }
      }
      // to print the list of prime numbers
      System.out.println("List of first 50 prime numbers: ");
      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):
    # initially assuming all values are prime
    prm = [True for _ in range(n+1)]
    # Loop over all numbers from 2 to sqrt(n)
    currPrm = 2
    while currPrm * currPrm <= n:
        # If current prime is still true, then it is a prime
        if prm[currPrm] == True:
            # Update all multiples of current prime
            for i in range(currPrm * currPrm, n+1, currPrm):
                # Marking factor as not prime
                prm[i] = False
        currPrm += 1
    
    # to print the list of prime numbers
    print("List of first 50 prime numbers: ")
    for i in range(2, n):
        if prm[i] == True:
            print(i, end=" ")

# test the function
lmt = 50
sieveOfEratos(lmt)

输出

List of first 50 prime numbers: 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

二进制幂运算算法

二进制幂运算算法是一种用于计算给定数字的幂的程序。解决这类问题的朴素方法，即np，是将数字自身乘以p-1次。但是，这是一个耗时的过程，而不是一个高效的过程。

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

  • 当任何给定数字的幂为0时，结果将为1。

  • 如果数字本身是偶数，请使用以下等式：((n2)p/2)，其中n是数字，p是该给定数字的幂。

  • 如果给定数字是奇数，请使用以下等式：(n*(n(p-1)/2)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;
      }
      // Square of base
      bs *= bs; 
      // Divide power by 2
      ex >>= 1; 
   }
   // Return the result stored in output
   return output;
}
int main() {
   int bs = 3;
   int ex = 6;
   // Print the result
   int result = bnryExp(bs, ex);
   printf("The output of %d to the power %d is: %d\n", bs, ex, result);
   return 0;
}

#include <iostream>
using namespace std;
// method to calculate power
int bnryExp(int bs, int ex) {
   // to store output
   int output = 1;
   while (ex > 0) {
      if (ex % 2 == 1) {
         output *= bs;
      }
      // Square of base
      bs *= bs; 
      // Divide power by 2
      ex /= 2; 
   }
   // Return the result stored in output
   return output;
}
int main() {
   int bs = 3;
   int ex = 6;
   int result = bnryExp(bs, ex);
   // Print the result
   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) {
        // to store output
        int output = 1;
        while (ex > 0) {
            if (ex % 2 == 1) {
                output *= bs;
            }
            // Square of base
            bs *= bs;
            // Divide power by 2
            ex /= 2;
        }
        // Return the result stored in output
        return output;
    }
    public static void main(String[] args) {
        int bs = 3;
        int ex = 6;
        // Print the result
        System.out.println("The output of " + bs + " to the power " + ex + " is: " + bnryExp(bs, ex));
    }
}

# method to calculate power
def bnryExp(bs, ex):
   # to store output
   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) {
   // to handle negative values
   if (valOne < 0) {
      valOne = (valOne % mod + mod) % mod;
   }
   if (valTwo < 0) {
      valTwo = (valTwo % mod + mod) % mod;
   }
   // addition
   int sum = (valOne + valTwo) % mod;
   // to ensure output is non-negative
   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\n", valOne, valTwo, mod, output);
   return 0;
}

#include <iostream>
using namespace std;
int modAddition(int valOne, int valTwo, int mod) {
   // to handle negative values
   if (valOne < 0) {
      valOne = (valOne % mod + mod) % mod;
   }
   if (valTwo < 0) {
      valTwo = (valTwo % mod + mod) % mod;
   }
   // addition
   int sum = (valOne + valTwo) % mod;
   // to ensure the result is non-negative
   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) {
        // to handle negative values
        if (valOne < 0) {
            valOne = (valOne % mod + mod) % mod;
        }
        if (valTwo < 0) {
            valTwo = (valTwo % mod + mod) % mod;
        }
        // addition
        int sum = (valOne + valTwo) % mod;
        // to ensure output is non-negative
        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):
  # to handle negative values
  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
  # to ensure output is non-negative
  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
打印页面
上一页
下一页
广告