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: