Hôm nay mình sẽ viết về những thuật toán sinh cơ bản, đó là những thuật toán khá quen thuộc đối với những sinh viên khi bắt đầu làm quen với lập trình. Tại sao lại là thuật toán mà không phải là những thuật toán cơ bản khác như pattern matching, sort, … Bởi vì, đó là thuật toán mình vấp phải nhiều nhất trong công việc hay những lúc code những thứ linh tinh.
Bài toán
Bài toán đặt ra như sau: Mình hay chơi trò xì tố 5 cây với bạn bè ( Mỗi người có 5 quân bài, hãy chọn ra 3 quân sao cho tổng của chúng chia hết cho 10, nếu không có thì mặc định thua luôn, và một trong hai quân còn lại sẽ được sắp xếp sao cho tổng lớn nhất có thể, và một trong hai quân sẽ là quân tẩy) => Nếu như mình muốn tạo một con bot có thể đánh bài với mình, rõ ràng phải phổ biến luật chơi cho nó =)), tức là nó phải biết cách làm thế nào để chọn được 3 quân có tổng chia hết cho 10, nhưng 2 quân còn lại phải có tổng cao nhất có thể ( lấy tổng chia hết cho 10, nên điểm có thể nằm trong khoảng từ 1 -> 10). Dĩ nhiên có nhiều thuật toán có thể giải quyết trò đó, nhưng sao ta không nghĩ đơn giản rằng, ta hãy liệt kê những trường hợp nhiều nhất có thể xảy ra, rồi lấy cách sắp xếp tốt nhất với N = 5, K = 3. Vậy số trường hợp có thể là “tổ hợp chập 3 của 5” (không nhiều lắm). Các bài toán liên quan đến xác suất, tổ hợp, chỉnh hợp, hoán vị … là những bài toán rất quan trọng trong ngành CNTT của mình, nên biết càng nhiều càng tốt. Do đó mình sẽ đi vào 3 thuật toán cụ thể như sau:
Sinh nhị phân
Đây là bài toán đầu tiên mình nhắc đến vì nó đơn giản nhất, giả sử mình có một số N cho trước, ví dụ N = 4 thì mình phải liệt kê các cấu hình gồm 3 chữ số có thể như:
0 0 0 0
0 0 0 1
0 0 1 0
……………
1 1 1 1
Nhưng đừng nhầm lẫn với việc ta đang coi việc sinh ra những chuỗi như vậy là mục đích cuối cùng của bài toán, nếu vậy ta chỉ cần dùng các phương pháp chia lấy phần dư như cách đổi các số hệ thập phân sang hệ nhị phân và cho vòng lặp chạy từ 0 đến 15 với N = 4, và từ 0 đến 32 với N = 5. Nhưng ta không làm như vậy, ta cần có một phương pháp nào đó để tìm ra quy luật đó hay ho hơn. Bản chất việc sinh ra chuỗi như vậy, để ta coi việc khi xuất hiện mỗi tổ hợp với 0 là “ẩn” và 1 là “hiện”. Từ đó ta có thể giải quyết được rất nhiều bài toán khác nhau từ mỗi tổ hợp như vậy.
Thuật toán : Cho một mảng n kí tự 0. Ta sẽ duyệt theo chiều ngược từ n – 1 về tới 0, biến tất cả các số 1 thành 0 rồi giảm tiếp, nhưng nếu gặp số 0 thì biến thành 1 và kết thúc lặp. Đến khi cả mảng chỉ chứa 1 thì kết thúc thuật toán.
void binaryGen( int B[], int n ){i = n; while (i > 0 && b[i] == 1) { b[i] = 0; i--; } if(i == 0) return; else b[i] = 1; }
Sinh tổ hợp
Tiếp theo là thuật toán sinh tổ hợp. Bài toán này giúp ta liệt kê được tất cả các tổ hợp chập K của N phần tử. Khi liệt kê, ta sẽ ưu tiên hiển thị các phần tử theo tổ hợp đã được sắp xếp theo kiểu từ điển. Ví dụ : 1, 2, 3 … a, b, c …. Ví dụ: với bài toán liệt kê tất cả các phần tử gồm 4 phần tử trong tổ hợp 6 phần tử với các item được đánh thứ tự từ 1 đến 6.
1 2 3 4
1 2 3 5
…………….
3 4 5 6
Có thể thấy quy tắc rất đơn giản, ở một ví trí thứ j bất kì khi một tổ hợp mới được chọn ra, nếu j = N – K + j thì ở vị trí j đó, ở vị trí đó giá trị đã đúng với tổ hợp cuối cùng. Ví dụ ở vị trí thứ 4 thì giá trị đó phải là 6 – 4 + 4 = 6. CỨ nhua vậy tổ hợp cuối cùng phải là 3,4,5,6 đúng với ví dụ trên. Nếu có vị trí nào đang chứa giá trị không đúng, thì ta sẽ ngừng duyệt và tăng các giá trị đang sai đó lên 1. Sau đó thay đổi các giá trị đằng sau theo giá trị vừa được thay đổi theo thứ tự từ điển, sao cho giá trị đó không được quá N.
Thuật toán: Cho một mảng gồm N phần tử và một giá trị K cho trước. Đầu tiên ta vẫn duyệt theo chiều ngược, nếu tại mỗi vị trí j có giá trị khác với N – K + j thì ta dừng lặp, giá trị aj = aj + 1. Và các giá trị đằng sau sẽ được tính từ giá trị aj đã được update, tăng dần theo thứ tự từ điển
void combinationGen( int B[], int K ){int i = K; while (B[i] == N - K + i) i--; B[i]++; for(j = i + 1; j <= N; j++) B[j] = B[i] + j - i; }
Sinh hoán vị
Cuối cùng là thuật toán sinh hoán vị, bài toán này nhìn thì có vẻ không khác mấy với thuật toán sinh tổ hợp, nhưng thuật toán thì lại khác hoàn toàn. Giả sử ta có N phần tử và cũng đang được sắp xếp theo thứ tự từ điển, và ta phải liệt kê tất cả các cấu hình được tạo bởi từ N phần tử đó. Ví dụ với bài toán liệt kê tất cả các hoán vị có thể của một mảng gồm 6 phần từ từ 1 đến 6
1 2 3 4 5 6
1 2 3 4 6 5
……………………
6 5 4 3 2 1
Có thể thấy hoán vị đầu tiên là một chuỗi các số tăng dần, nhưng hoán vị cuối cùng lại là một chuỗi số giảm dần, vâỵ ta phải áp dụng một thuật toán để có thể hoán vị các vị trí trong mảng để có thể sinh ra chuỗi số thoả mãn hoàn vị cuối cùng.
Thuật toán: Với một mảng gồm N phần tử, và tất nhiên các phần tử đang sắp xếp theo thứ tự từ điển tăng dần. Đầu tiên ta duyệt từ trái qua phải nếu gặp phần tử nào ở vị trí j mà nhỏ hơn vị trí j + 1 thì ta dừng lặp (vì theo lý thuyết, hoán vị cuối cùng phải là một chuỗi số giảm dần). Sau đó ta lại tìm từ vị trí j + 1 tới N để tìm được giá trị ở vị trí k nào đó sao cho giá trị đó nhỏ nhất. Sau đó ta sẽ hoán đổi hai giá trị ở vị trí k và j cho nhau. Cuối cùng từ vị trí j đó tới N, ta đảo ngược vị trí các phần tử trong với nhau.
void permutationGen( int B[]){int j,k,r,s,t j = N; while (B[j] > B[j + 1]) j--; k = N; while (B[j] > B[k) k--; t = B[j]; B[j] = B[k]; B[K] = t; r = j + 1; s = N; while(r < s){ t = r; r = s; s = t; } }
Kết luận
Mặc dù đây là những bài toán cơ bản, nhưng tính ứng dụng lại cực kì phổ biến với nhiều loại bài toán khác nhau. Đối với những bài toán xác suất thống kê, tìm các cấu hình, hoán vị, tổ hợp, chỉnh hợp, từ ba bài toán trên ta có thể tuỳ biến và sử dụng được để góp phần xử lý cho những bài toán lớn và phức tạp hơn.