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
列印頁面
上一頁
下一頁
廣告
© . All rights reserved.