Tổng hợp một số thuật toán cơ bản
23/09/2016 6 minutes read
Share:
Thuật toán kiểm tra một số có phải là số chính phương hay không
Tư tưởng là ta sẽ kiểm tra xem các số m từ 1 đến số a xem nếu m*m = a thì số a là số chính phương. Tuy nhiên ta sẽ sử dụng thuật toán chia đôi để nhanh chóng tìm ra kết quả.
bool IsSquareNumber(int a) | |
{ | |
int left = 1, right = a, m; | |
while(left < right) | |
{ | |
m = (left + right) / 2; | |
if(m*m > a) right = m - 1; | |
else if(m*m < a) left = m + 1; | |
else return true; | |
} | |
return false; | |
} |
Thuật toán kiểm tra xem một số có là số nguyên tố hay không
Thuật toán tạo một mảng đánh dấu các số nguyên tố không lớn hơn n
bool* CreatePrimeArray(int n) | |
{ | |
bool *Prime = new bool[n+1]; | |
for(int i = 0; i <= n; i++) | |
Prime[i] = true; | |
Prime[0] = Prime[1] = false; | |
for(int i = 2; i*i <= n; i++) | |
if(Prime[i] == true) | |
{ | |
int j = 2; | |
while(i*j <= n) | |
{ | |
Prime[i*j] = false; | |
j++; | |
} | |
} | |
return Prime; | |
} |
Thuật toán tìm ước số chung lớn nhất
Ta sẽ tìm ước chung lớn nhất của hai số dựa vào thuật toán Euclid
int GCD(int a, int b) | |
{ | |
if(a == 0 && b == 0) return -1; | |
if(b == 0 || a == 0) return a + b; | |
return GCD(b, a%b); | |
} |
Thuật toán tìm bội số chung nhỏ nhất
Ta sẽ tìm bội số chung nhỏ nhất dựa vào thuật toán tìm ước số chung lớn nhất như trên
int LCM(int a, int b) | |
{ | |
if(a == 0 || b == 0) return -1; | |
return (abs(a * b) / GCD(a, b)); | |
} |
Thuật toán tính giai thừa: n!
int Factorial(int n) | |
{ | |
int r = 1; | |
for(int i = 1; i <= n; i++) | |
r *= i; | |
return r; | |
} |
Thuật toán tính tổ hợp chập k của n: C(k,n)
int Combination(int k, int n) | |
{ | |
int r = 1; | |
for (int i = 1; i <= k; i++,n--) | |
r = r * n / i; | |
return r; | |
} |
Code by Phạm Văn Lâm
Share: