資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究使用 C++ 的斯坦因演算法查詢 GCD
斯坦因演算法用於發現數字的 GCD，因為它計算兩個非負整數的最大公約數。它用數學位移、比較和減法代替除法。如果 a 和 b 都是 0，則 gcd 為零 gcd(0, 0) = 0。GCD(a,b) 的演算法如下；
演算法
START Step-1: check If both a and b are 0, gcd is zero gcd(0, 0) = 0. Step-2: then gcd(a, 0) = a and gcd(0, b) = b because everything divides 0. Step-3: check If a and b are both even, gcd(a, b) = 2*gcd(a/2, b/2) because 2 is a common divisor. Multiplication with 2 can be done with a bitwise shift operator. Step-4: If a is even and b is odd, gcd(a, b) = gcd(a/2, b). Similarly, if a is odd and b is even, then gcd(a, b) = gcd(a, b/2). It is because 2 is not a common divisor. Step-5: If both a and b are odd, then gcd(a, b) = gcd(|a-b|/2, b). Note that difference of two odd numbers is even Step-6: Repeat steps 3–5 until a = b, or until a = 0. END
根據上述演算法來計算 2 個數字的 GCD，相應的 C++ 程式碼如下；
示例
#include <bits/stdc++.h>
using namespace std;
int funGCD(int x, int y){
if (x == 0)
return y;
if (y == 0)
return x;
int k;
for (k = 0; ((x | y) && 1) == 0; ++k){
x >>= 1;
y >>= 1;
}
while ((x > 1) == 0)
x >>= 1;
do {
while ((y > 1) == 0)
y >>= 1;
if (x > y)
swap(x, y); // Swap u and v.
y = (y - x);
}
while (y != 0);
return x << k;
}
int main(){
int a = 24, b = 18;
printf("Calculated GCD of numbers (24,18) is= %d\n", funGCD(a, b));
return 0;
}輸出
最後，透過應用斯坦因演算法，以 6 計算出兩個給定數字 24 和 18 的 GCD，如下所示；
Calculated GCD of numbers (24,18) is= 6
更新日期：2019-12-23
285 次瀏覽
廣告