Bài toán 1: Bài toán nhân hai ma trận
Hầu như bất kỳ ai học qua toán đại cương ở trường đại học hay mới học lập trình đều đã từng biết về bài toán nhân ma trận. Một ma trận kích thước NxM là một bảng (mảng) hai chiều gồm N hàng, mỗi hàng gồm M cột, tại mỗi ô (i, j), tương ứng với hàng i và cột j, của bảng là một số nguyên (hoặc số thực). Khi số hàng N bằng với số cột M, ta sẽ có một ma trận vuông. Hai ma trận vuông NxN nhân với nhau sẽ cho ma trận tích kích thước NxN. Giả sử ma trận thứ nhất là a, ma trận thứ hai là b thì công thức để nhân a với b được cho như sau:
Cài đặt cho thuật toán nhân hai ma trận theo công thức trên như sau:
Quan sát một chút chúng ta sẽ thấy rằng đoạn chương trình thực hiện chức năng chính của việc nhân ma trận chính là 3 vòng lặp với các biến chỉ số i, j, k và việc thay đổi thứ tự của ba vòng lặp này không ảnh hưởng gì tới kết quả cuối cùng. Ở đây chúng ta có 3 vòng lặp với 3 chỉ số nên sẽ có 3! = 6 cách khác nhau để tiến hành nhân hai ma trận tương ứng với việc thay đổi thứ tự của ba vòng lặp. Các bạn có thể cho rằng 6 cách để nhân hai ma trận này có thời gian chạy giống nhau nhưng thực tế lại không phải như vậy. Chúng ta hãy phân tích xem tại sao lại có kết quả khác nhau và cách nào là tốt nhất cho bài toán nhân ma trận theo thuật toán trên.
Nếu nhân hai ma trận theo thứ tự chỉ số ijk như ở trên, các phần tử của ma trận a, c sẽ được truy cập theo từng hàng, còn ma trận b sẽ có các phần tử truy cập theo các cột. Còn nếu nhân hai ma trận theo thứ tự ikj thì cả ba ma trận đều có các phần tử được truy cập tới theo từng hàng. Các phần tử của một ma trận được tổ chức trong bộ nhớ thực chất là một dãy các ô nhớ liên tiếp trong đó các phần tử ở cùng một hàng sẽ nằm kế tiếp nhau, hết hàng này lại đến hàng khác của ma trận. Vì thế nếu các phần tử được truy cập tới theo hàng, kết quả sẽ nhanh hơn so với truy cập tới theo cột. Điều này là do nguyên tắc làm việc của máy tính: khi truy cập tới một phần tử bộ nhớ nào đó, các phần tử liền kề với nó cũng sẽ được đọc vào bộ nhớ trong của máy tính để tối ưu thời gian truy cập bộ nhớ theo nguyên lý: nếu một địa chỉ bộ nhớ nào đó được truy cập tới thì rất có thể trong tương lai các ô nhớ lân cận với nó cũng sẽ được sử dụng (truy cập tới). Chính vì vậy việc thực hiện thuật toán nhân hai ma trận theo thứ tự ikj sẽ nhanh hơn so với 5 cách còn lại của thuật toán nhân hai ma trận. Các bạn có thể sinh ngẫu nhiên các ma trận có N xấp xỉ 1000 để kiểm chứng kết quả này.
Bài toán 2: Bài toán trộn các dãy con
Bài toán trộn các dãy con được phát biểu như sau: cho hai dãy số (nguyên) đã được sắp xếp tăng dần là dãy a (có N phần tử) và dãy b (có M phần tử), hãy trộn hai dãy a và b thành một dãy kết quả c sao cho dãy c gồm tất cả các phần tử của a, b và cũng được sắp xếp tăng dần.
Thật ra có khá nhiều cách để cài đặt thuật toán cho bài toán trên, sau đây tôi sẽ đưa ra một cài đặt khá đơn giản và hiệu quả cho bài toán trộn 2 Run này (1 dãy sắp xếp được gọi là 1 Run). Trước hết cần để ý rằng dù có tiến hành theo cách nào thì Run kết quả c cũng sẽ có đủ N+M phần tử của cả Run a và Run b. Nếu ta gọi i, j, k lần lượt là chỉ số tương ứng của các Run a, b, c thì các chỉ số này sẽ lần lượt nhận các giá trị:
• Từ 0 tới N-1 cho biến i
• Từ 0 tới M-1 cho biến j
• Từ 0 tới (N+M)-1 cho biến k
Hơn nữa mỗi phần tử của Run c chỉ có thể nhận giá trị là 1 phần tử của Run a hoặc Run c, có nghĩa là c[k] = a[i] hoặc b[j] với k chạy từ 0 tới (N+M)-1. Việc gán c[k] bằng a[i] hay b[j] sẽ được quyết định dựa trên hai yếu tố: a[i] nhỏ hơn hay b[j] nhỏ hơn, hoặc một dãy đã hết (i hoặc j chạy qua giới hạn của nó) thì chỉ còn cách lấy phần tử của dãy còn lại. Tức là:
Với các nhận xét trên chúng ta có cài đặt sử dụng 1 vòng for như sau:
Thậm chí nếu dùng toán tử 3 ngôi chúng ta sẽ có đoạn chương trình ngắn gọn hơn như sau:
Các bạn có thể viết thành chương trình đầy đủ để kiểm chứng tính chính xác của đoạn chương trình trên. Sau khi đã trộn được 2 Run thì việc trộn 3, 4 hay nhiều Run hơn có thể thực hiện dễ dàng bằng cách cũng khá đơn giản: chúng ta lặp lại việc trộn hai Run nhiều lần.
Một thuật toán có liên quan tới thuật toán trộn hai Run chính là thuật toán sắp xếp bằng trộn (ở đây chúng ta cần phân biệt sắp xếp trong với sắp xếp ngoài: sắp xếp trong thường là sắp xếp mảng với số phần tử đủ để chứa trong bộ nhớ trong của máy tính trong quá trình sắp xếp, còn sắp xếp ngoài thường là sắp xếp các cơ sở dữ liệu lớn, không thể chứa hết trong bộ nhớ trong của máy tính như sắp xếp các file trên máy tính chẳng hạn, ở đây tôi chỉ đề cập tới thuật toán sắp xếp trong).
Nguyên lý của thuật toán sắp xếp trộn là như sau: ban đầu ta chia mảng cần sắp ra làm hai nửa, sau đó sắp xếp hai nửa đó bằng việc gọi đệ qui tới thuật toán, và cuối cùng trộn hai nửa đã được sắp thành mảng kết quả. Ở đây ta cần thấy hai điểm sau: một là sẽ phải dùng thêm 1 mảng trung gian để lưu kết quả trộn, hai là đoạn chính yếu của thuật toán nằm ở việc trộn hai nửa của mảng, tức là sử dụng thuật toán trộn 2 Run mà chúng ta vừa thấy ở trên. Sau đây là cài đặt đầy đủ của thuật toán sắp xếp trộn:
Bài toán 3: Số nhân đôi
Cho một dãy số nguyên a có N phần tử, hãy tìm số phần tử của dãy a có giá trị bằng 2 lần một phần tử khác cũng thuộc dãy. Ví dụ với dãy 1, 15, 4, 3, 2, 21, 9, 7, 18, 22 thì kết quả sẽ là 3 (các số 2, 4, 18).
Với bài toán này, các bạn có thể nhận thấy có điều gì đó tương đối giống với bài toán 1 và bài toán số trung bình trong bài viết “Học thuật toán qua các bài toán”. Chúng ta sẽ bắt đầu phân tích lần lượt từng thuật toán cho bài toán này để xem có tận dụng được ý tưởng của hai bài toán trên hay không.
Thuật toán 1: Duyệt qua các phần tử của dãy a, với mỗi phần tử a[i] tiến hành tìm tuần tự xem trong dãy a có phần tử nào bằng 2*a[i] hay không, nếu có thì tăng biến đếm lên 1 đơn vị. Thuật toán này có độ phức tạp O(N2) với N là số phần tử của dãy a.
Thuật toán 2: Sử dụng ý tưởng từ bài toán 1 trong bài viết “Học thuật toán qua các bài toán”, ban đầu sắp xếp dãy a tăng dần bằng 1 thuật toán có độ phức tạp O(N*log(N)), chẳng hạn như sắp xếp trộn hoặc vun đống chẳng hạn. Sau đó duyệt qua các phần tử của dãy a, với mỗi phần tử a[i] tiến hành tìm nhị phân trong khoảng a[i+1..N-1] để kết luận có tồn tại phần tử nào bằng 2*a[i] hay không, nếu có thì tăng biến đếm lên 1 đơn vị. Thuật toán này có độ phức tạp là O(N*log(N)).
Thuật toán 3: Ta sử dụng ý tưởng trong bài toán “Số trung bình”: sử dụng một mảng đánh dấu mark và gán tất cả các giá trị mark[a[i]] bằng đúng. Sau đó duyệt qua toàn bộ mảng a, với mỗi phần tử a[i], kiểm tra xem mark[2*a[i]] có bằng đúng hay không, nếu đúng thì tăng biến đếm lên 1 đơn vị. Thuật toán này có độ phức tạp là O(N).
Bài toán 4: Ma trận con có tổng lớn nhất
Cho một ma trận gồm các số nguyên (có thể âm hoặc dương) kích thước NxM, hãy tìm ma trận con của ma trận đã cho có tổng các phần tử trong ma trận là lớn nhất.
Ví dụ với ma trận:
Thì ma trận con có tổng lớn nhất sẽ là:
Thuật toán thuộc loại brute force (duyệt hết tất cả các trường hợp) cho bài toán là:
Thuật toán dễ hiểu trên có độ phức tạp là O(N3*M3) và sẽ không thể chạy được với N = M = 1000.
Đây là một bài toán quen thuộc sử dụng chiến lược qui hoạch động, chúng ta để ý tới việc tính tổng của một ma trận a[i..i1][j..j1] có thể được thực hiện nhờ các kết quả sum[i][j] với sum[i][j] là tổng của ma trận a[0..i][0..j] theo công thức sau:
temp = sum[i1][j1] - sum[i - 1][j1] - sum[i1][j - 1] + sum[i – 1][j – 1];
Trong đó temp là tổng các phần tử của ma trận a[i..i1][j..j1]. Việc tính các giá trị của mảng sum[i][j] được thực hiện theo công thức sau:
sum[i][j] = sum[i – 1][j] + sum[i][j-1] – sum[i-1][i-1] + a[i][j] nếu i, j đều lớn hơn 0.
sum[i][j] = sum[i – 1][j] + a[i][j] nếu i > 0 và j bằng 0.
sum[i][j] = sum[i][j-1] + a[i][j] nếu i bằng 0 và j > 0.
Như vậy việc tính ra mảng sum[i][j] sẽ được thực hiện với 2 vòng for lồng nhau và có độ phức tạp là O(N*M). Đoạn chương trình chính để tìm ma trận con có tổng lớn nhất sẽ có sự thay đổi: thay vì sử dụng 2 vòng lặp để tìm ra giá trị của ma trận con a[i..i1][j..j1] chúng ta sẽ sử dụng các giá trị của mảng sum để tính, do đó thuật toán bây giờ sẽ có độ phức tạp là O(N2*M2), đó cũng là độ phức tạp cho cả bài toán. Rõ ràng so với độ phức tạp là O(N3*M3) thì đây quả là một cải tiến đáng kể.
Bài toán 5: Ma trận 0/1
Cho một ma trận các số nguyên có kích thước là NxM (0 < N, M < 1000), mỗi phần tử ở hàng i, cột j của ma trận hoặc bằng 0 hoặc bằng 1. Hãy tìm kích thước ma trận con lớn nhất của ma trận đã cho mà các ô của nó chứa toàn số 1. Ví dụ với ma trận:
Kết quả sẽ là 15.
Bài toán này tương tự như bài toán số 4 ở trên nhưng ta không thể áp dụng cách làm việc tương tự để đưa ra lời giải cho bài toán (vì giới hạn của N, M) mà ta sẽ dựa vào một cách tính khác. Giả sử tại mỗi ô a[i][j] (bằng 0 hoặc 1) ta xây dựng được các phần tử tương ứng s[i][j] bằng số số 1 liên tiếp trên cùng hàng tính từ a[i][j]. Ví dụ với ma trận a trên ta tính được ma trận s tương ứng là:
Khi đó để tìm được ma trận con có kích thước lớn nhất thỏa mãn đầu bài ta để ý rằng để tính diện tích của ma trận gồm toàn số 1 tính tới vị trí i, j của ma trận gốc a ta cần kiểm tra a[i][j] có bằng 1 hay không, nếu a[i][j] bằng 1 thì cập nhập s[i][j], sau đó tìm diện tích lớn nhất của tất cả các ma trận con gồm toàn số 1 với phần tử chốt là a[i][j] dựa trên giá trị s[i][j] vừa tính, cụ thể như sau:
Thuật toán này có độ phức tạp là O(N2*M).
Bài toán 6: Bài toán tìm dãy con chia hết dài nhất
Cho một dãy các số nguyên a có N phần tử, hãy tìm dãy con dài nhất (gồm nhiều phần tử nhất) các phần tử (không thay đổi thứ tự của các phần tử) của dãy a sao cho trong dãy tìm được đó phần tử sau chia hết cho phần tử trước.
Ví dụ với dãy: 9, 2, 3, 7, 8, 14, 39, 145, 76, 320 thì kết quả sẽ là 3 (các phần tử 2, 8, 320).
Thực chất đây là một bài toán qui hoạch động nên chúng ta cần xác định công thức truy hồi liên quan tới dãy input và kết quả cần tìm của bài toán. Nếu ta gọi dãy b là dãy được xác định như sau: b[i] là độ dài dãy con dài nhất gồm các phần tử thỏa mãn yêu cầu của đầu bài khi input của bài toán là dãy a[0..i] thì ta sẽ có quan hệ qui nạp sau:
Với công thức qui nạp được xác định như trên, đoạn mã chương trình cài đặt cho thuật toán giải quyết bài toán là:
Bây giờ các bạn hãy vận dụng thuật toán trên để đưa ra thuật toán cho các bài toán sau như là một bài tập:
1. Cho một dãy các công việc, mỗi công việc có thời gian bắt đầu và khoảng thời gian để thực hiện. Hãy tìm dãy dài nhất các công việc sao cho thời gian thực hiện của chúng không chồng chéo lên nhau.
2. Cho một dãy các số nguyên, hãy tìm dãy con tăng dài nhất của dãy đã cho.
Chú ý: Các đoạn mã chương trình minh họa đều viết bằng C/C++ nên các mảng đều được đánh số từ 0.
Mặc dù đã hết sức thận trọng và xem xét kỹ các ví dụ đưa ra trong bài viết, tuy vậy vẫn có thể không tránh khỏi các sai sót, rất mong nhận được sự đóng góp ý kiến của các bạn độc giả. Mọi góp ý, thắc mắc xin gửi về địa chỉ email: tuannhtn@yahoo.com.
School@net (Theo Nguyễn Hữu Tuân - THNT)
|
Tìm kiếm
Khách: 3
Thành viên: 0
Tổng cộng: 3
