Một số thuật toán cơ bản

 

Kiểm tra 1 số nguyên tố

 + Định nghĩa: Là số nguyên lớn hơn 1, chỉ có 2 ước là 1 và chính nó. Các số nguyên tố từ 1-100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

+ Thuật toán: Để kiểm tra 1 số nguyên n có phải số nguyên tố hay không, ta làm theo các bước.
- Nếu n<2 thì không phải số nguyên tố.
- Kiểm tra trong đoạn từ 2..sqrt(n) xem có ước của n không, nếu có tồn tại thì n không phải số nguyên tố
- Ngược lại, n là số nguyên tố.

 

 
Phương pháp sàng Eratosthene

 + Mục đích: Để lập bảng các số nguyên tố nhỏ hơn hoặc bằng 1 số n cho trước.

+ Thuật toán: Sử dụng 1 bảng bool isPrimeNumber[0..n+1] để lưu kết quả
- Khởi tạo: tất cả các số từ 1->n là nguyên tố.
- Xóa số 1 ra khỏi bảng.
- Lặp: Tìm 1 số nguyên tố đầu tiên trong bảng sau đó xóa tất cả các bội của nó trong bảng.
- Quá trình lặp kết thúc khi gặp số nguyên tố >= sqrt(n).
- Tất cả các số chưa bị xóa trong bảng là số nguyên tố.

 

Tìm ước số chung lớn nhất (GCD)

+ Định nghĩa: Ước số chung lớn nhất (Greatest Common Divisor) của 2 số a và b, được định nghĩa như sau: gcd(a,b)=d <=> d là số lớn nhất trong tất cả các ước chung của a và b.

+ Thuật toán: Giải thuật Euclid, định nghĩa đệ qui như sau:
- gcd(a,0)=a
- gcd(a,b)=gcd(b,a mod b)

 

 

Tìm bội số chung nhỏ nhất (lcm)

 + Định nghĩa: Bội số chung nhỏ nhất (Least Common Multiple) của 2 số a và b được định nghĩa LCM(a,b)=m <=> m là số nhỏ nhất trong tất cả các bội chung của a và b.

+ Thuật toán: Ta có công thức:

 

 

Tính n giai thừa (Factorial)

 + Công thức:

 

 Phát biểu bằng lời: Giai thừa của 1 số nguyên dương n là tích tất cả các số nguyên dương nhỏ hơn hoặc bằng n.

 + Thuật toán: Ta có thuật toán đệ qui như sau:

 

 
Tính tổ hợp chập k của n

 + Công thức:

  

 + Thuật toán:
- Trâu bò (Brute Force): sử dụng hàm tính giai thừa.

- Sử dụng vòng lặp:

 

Kiểm tra số chính phương

 + Định nghĩa: Số chính phương (SquareNumber) là số có căn bậc 2 là 1 số nguyên. Ví dụ: 4,9,100...

+ Thuật toán: Để kiểm tra n có phải số chính phương hay không ta lấy phần nguyên của căn bậc 2 của n rồi bình phương, sau đó so sánh với n.
Ví dụ: sqrt(4)=2.0 Ta thấy 2^2=4 => 4 là số chính phương
sqrt(7)=2.4657 , phần nguyên là 2. Ta thấy 2^2 <> 7 => 7 không phải số chính phương.

Tìm kiếm nhị phân (Binary Search)

 + Sơ lược: Tìm kiếm nhị phân là thuật toán nhằm xác định vị trí của 1 phần tử trong 1 mảng đã được sắp xếp. Thuật toán hoạt động dựa trên việc so sánh giá trị phần tử đầu vào với phần tử ở giữa (middle) của dãy. Việc so sánh sẽ cho biết phần tử ở giữa này bằng, nhỏ hơn hay lớn hơn giá trị đầu vào. Khi phần tử được đem so sánh mà bằng input thì việc tìm kiếm sẽ kết thúc và trả về vị trí của phần tử đó. Nếu phần tử này nhỏ hơn input thì đồng nghĩa với việc ta cần tìm input trong đoạn từ middle+1..top, ngược lại nếu lớn hơn input thì ta cần tìm input trong đoạn bottom..middle-1. Khi dãy tại bước hiện tại không có phần tử nào (bottom>top) thì không cần tìm kiếm. Kết thúc quá trình tìm kiếm nếu không thấy input xuất hiện trong dãy thì kết quả trả về -1.

+ Code:Visual C# Code:

public int BinarySearch(int[] a, int value, int bottom, int top)
{
while (bottom <= top) // trong khi dãy đang xét còn phần tử
{
int middle = (bottom + top) / 2;
if (a[middle] == value) return middle; // đã tìm thấy tại vị trí middle, quá trình tìm kiếm dừng.
else if (a[middle] > value) top = middle - 1; // cần tìm value trong đoạn bottom..middle-1
else bottom = middle + 1; // cần tìm value trong đoạn middle+1..top
}
return -1; //Không tìm thấy
}

Chú ý: 
+ Độ phức tạp của thuật toán là O(log(n))
+ Thông thường giá trị bottom và top ban đầu tương ứng với 0 và N-1.

Số hoàn hảo (Perfect Number)

 + Định nghĩa: Số hoàn hảo là số có tổng các ước nhỏ hơn nó bằng chính nó. Ví dụ: 6 = 1+2+3. 28 = 1+2+4+7+14.

+ Thuật toán: Để kiểm tra n có phải Perfect Number hay không, đi tìm tổng tất cả các ước nhỏ hơn n rồi so sánh.

 

 

Kiểm tra số nguyên tố cùng nhau

 + Đặt vấn đề: Trong khi thao tác với các con số nhiều lúc các bạn gặp phải cụm từ hai số nguyên tố cùng nhau!; lúc đó có bạn nghĩ rằng đó phải là 2 số nguyên tố gần nhau. Hì, sai mất rồi đó; vậy nên trong Vấn đề 5 Peter đã khái quát qua (dẫn các bạn trước khi vào vấn đề này) là: Hai số nguyên dương a và b được gọi là nguyên tố cùng nhau khi và chỉ khi Ước chung lớn nhất của chúng là 1; tức là (a,b)=1; chứ không hẳn a và b phải là 2 số nguyên tố đứng gần nhau (hoặc có một cái hiểu tương tự), dĩ nhiên nếu a và b là hai số nguyên tố khác nhau thì chúng cũng thoả mãn tính chất là hai số "nguyên tố cùng nhau" (Lẫn lộn quá, nhưng các bạn chú ý cho điều này).

+ Phương pháp: Vậy làm sao để kiểm tra chúng nguyên tố cùng nhau hay không? Rất đơn giản là (ký hiệu hàm là CoPrime()):
- Nếu ước chung lớn nhất của chúng khác 1 thì trị trả về cho hàm kiểm tra là 0, báo hiệu hai số không nguyên tố cùng nhau.
- Ngược lại, thì trị trả về cho hàm kiểm tra là 1, báo hiệu hai số nguyên tố cùng nhau.

 

 

Số các ước số nguyên dương của một số nguyên dương

 + Đặt vấn đề: Trong toán lý thuyết số thì vấn đề về liệt kê các ước nguyên dương của một số nguyên dương chiếm một vị trí cũng khá quan trọng, số các ước số nguyên dương của một số nguyên dương n được cho bởi công thức sau:
Các bạn thường gặp một bài toán phổ biến là Phân tích một số ra tích các thừa số nguyên tố (mà ngày xưa học lớp 6 Peter mới được tiếp cận); nhìn thấy các bạn giải quyết chúng khá đơn giản bằng các vòng lặp for. Đó là:

+ Code:C++ Code:
int NoOfDivisor(int n)
{
int dem=0;
for (int i=1;i<=(int)sqrt(n);i++)
if (n%i==0)
dem++;
return dem;
}