Đếm Trong Lập Trình - Từ Bài Toán Nhỏ Đến Big Data?

Đếm Trong Lập Trình – Từ Bài Toán Nhỏ Đến Big Data?

Tổng quan

21-05-2021

NỘI DUNG BÀI VIẾT

Chúng ta có lẽ đều đã được học đếm từ thuở mới biết nói. Tuy nhiên, những bài toán đếm không chỉ dừng lại ở lớp 1. Trong công nghệ thông tin, những bài toán đếm ấy trải dài từ những vấn đề cơ bản chúng ta luyện tập hàng ngày cho tới những vấn đề nhức nhối nhất của Data Science (Khoa học dữ liệu).

Hôm nay chúng ta sẽ hiểu rõ hơn về 2 quy tắc đếm cơ bản các bạn có thể sẽ cần phải mang theo trong suốt hành trình “lập trình”!

Trong bài viết đầu tiên, mình có đề cập đến một bài toán đếm như sau:

Ví dụ 1: Có bao nhiêu số có 7 chữ số và các chữ số đều khác nhau?

Và mình cũng có nhắc tới một công thức khá kì lạ: Kết quả là 9 * 9 * 8 * 7 * 6 * 5 * 4

Vậy tại sao chúng ta lại suy ra được công thức “dị” ấy? Sau đây chúng ta sẽ tìm hiểu về những quy tắc cơ bản giúp chúng ta có được kết quả đó nhé!

1. Quy tắc cộng

Thực ra đây là một quy tắc chúng ta đều sử dụng hàng ngày, chỉ là chúng ta đã mặc định sử dụng quy tắc này quá nhiều, khiến nó ăn sâu vào bản năng chúng ta.

Quy tắc này được phát biểu một cách tổng quát như sau:

Nếu một công việc có thể thực hiện theo n phương án khác nhau, trong đó:

Phương án 1 có m₁ cách thực hiện
Phương án 2 có m₂ cách thực hiện

…

Phương án n có m_n cách thực hiện

Khi đó, sẽ có m₁ + m₂ + ... + m_n cách để hoàn thành công việc đã cho.

Để hiểu rõ hơn về quy tắc này, hãy xét ví dụ sau đây:

Ví dụ 2: Có 3 chồng quà, chồng quà thứ 1 có 6 món, chồng quà thứ 2 có 5 món và chồng thứ 3 có 3 món. Hỏi có bao nhiêu cách để chọn quà?

Solution: Thực ra cụm từ “cách chọn quà” chỉ là một cách nói “fancy” khác cho “bao nhiêu hộp quà”. Thực ra chúng ta chỉ cần cộng 3 số lại để được kết quả.

Hoặc chúng ta có thể áp dụng quy tắc cộng nêu trên, coi “chồng quà” là “phương án”, như vậy sẽ có 6 + 5 + 3 “cách chọn quà”.

Thoạt đầu quy tắc này trông có vẻ hiển nhiên nhưng nó sẽ hỗ trợ rất nhiều cho bạn trong những vấn đề đếm chác như thế này đấy!

2. Quy tắc nhân

Mình thấy đây là một quy tắc ít được dùng hơn quy tắc cộng, vì vậy nó sẽ rất hữu dụng một khi các bạn thành thạo nó.

Quy tắc này được phát biểu một cách tổng quát như sau:

Nếu một công việc được thực hiện trong n giai đoạn, trong đó:

Giai đoạn 1 có m₁ cách thực hiện
Giai đoạn 2 có m₂ cách thực hiện

…

Giai đoạn n có m_n cách thực hiện

Khi đó, sẽ có m₁ * m₂ * ... * m_n cách để hoàn thành công việc đã cho.

Ví dụ 3: Lớp 1A có 14 bạn, lớp cần bầu ra 1 lớp trưởng, 1 lớp phó học tập và 1 lớp phó lao động, ngoài ra không ai được phép làm nhiều hơn 1 chức vụ. Hỏi có bao nhiêu cách chọn bộ 3 cán sự lớp trên?

Solution: Chúng ta sẽ chọn như sau:

Trước tiên chọn lớp trưởng: Có 14 cách để chọn (tại lớp có 14 bạn)
Sau đó chọn lớp phó học tập: Có 13 cách để chọn (trừ lớp trưởng ra vì không ai được giữ nhiều hơn 1 chức vụ)
Cuối cùng chọn lớp phó lao động: Có 12 cách để chọn (trừ 2 chức vụ trên ra)

Vậy có tổng cộng 14 * 13 * 12 cách để chọn bộ 3 cán sự lớp 1A (số cụ thể thì các bạn bấm máy cũng được, mình lười 😉 ). Tất nhiên ta có thể chọn lớp phó học tập trước hoặc lớp phó lao động trước, nhưng mình hầu như thấy rằng lớp trưởng là cán sự lớp được bầu đầu tiên :v

Quay lại ví dụ 1:

Chúng ta sẽ chọn như sau:

Chọn chữ số đầu tiên: Có 9 cách chọn, từ 1 đến 9 (không được chọn số 0)
Chọn chữ số thứ 2: Có 9 cách chọn, từ 0 đến 9 (không được giống với chữ số trước)
Chọn chứ số thứ 3: Có 8 cách chọn, từ 0 đến 9 (không được giống với 2 chữ số trước)

…

Chọn chữ số thứ 7: Có 4 cách chọn (không được giống với 6 chữ số trước)

Tới đây, áp dụng quy tắc nhân, ta sẽ được kết quả mong muốn.

3. Áp dụng những quy tắc đếm căn bản

Sau đây chúng ta sẽ đặt một vài vấn đề, phân tích và so sánh giữa cách làm “cần cù” và cách “thông minh” nhé!

Các bạn hãy cố gắng thử sức với nhưng vấn đề dưới trước khi xem solution, sử dụng những kiến thức trên nhé!

Vấn đề 1: Có bao nhiêu số nguyên dương chẵn nhỏ hơn 1 tỉ và có các chữ số khác nhau?

Naive Solution (Cách “ngây thơ”): Duyệt tất cả các số chẵn từ 2 đến 1 tỉ, đồng thời kiểm tra tất cả các chữ số của từng số, xem chúng có khác nhau hay không.

ĐPT (Độ phức tạp thời gian): O(n log n)

Efficient Solution (Cách hiệu quả): Ta thấy rằng tất cả các số nhỏ hơn 1 tỉ là tất cả các số có 1 chữ số, 2 chữ số, …, 9 chữ số. Vì vậy ở đây mình sẽ chỉ phân tích đếm xem có bao nhiêu số có 3 chữ số thỏa mãn. Phần còn lại các bạn có thể từ đó mà suy ra nhé!

Vì ta cần tìm những số chẵn nên ta sẽ ưu tiên chọn chữ số ở cuối trước. Tuy nhiên, trong những bài toán đếm số như thế này, các bạn phải cẩn thận, vì 1 số không được phép bắt đầu bằng chữ số 0. Nếu không cẩn thận, trong quá trình đếm, các bạn có thể đếm thừa những số có chữ số 0 đứng trước (kiểu như 012). Vì vậy, ta sẽ chia 2 case (trường hợp):

Case 1: Chữ số đứng cuối là 0:
- Chữ số đầu tiên lúc này sẽ có 9 cách chọn, từ 1 đến 9.
- Chữ số thứ 2 sẽ có 8 cách chọn, vì chữ số này phải khác 0 (chữ số cuối) và chữ số đầu đã chọn.

Áp dụng quy tắc nhân, case này có: 9 * 8 = 72 số

Case 2: Chữ số đứng cuối khác 0:
- Chữ số đứng cuối bây giờ sẽ nằm trong 4 khả năng là 2, 4, 6, 8.
- Chữ số đầu tiên giờ sẽ có 8 cách chọn, vì nó phải khác 0 và khác chữ số cuối.
- Chữ số thứ 2 sẽ có 8 cách chọn, vì nó phải khác với hai chữ số trước.

Áp dụng quy tắc nhân, case này có: 4 * 8 * 8 = 256 số

Đến đây, áp dụng quy tắc cộng, ta sẽ được: 72 + 256 = 328 số có 3 chữ số thỏa đề bài.

Tiếp tục phân tích tương tự với các số còn lại, rồi áp dụng quy tắc cộng để cộng hết các trường hợp số có 1 chữ số, 2 chữ số, … thì ta sẽ thu được kết quả.

ĐPT: O(1) nếu bạn chịu khó “tính” hết ra giấy và đưa lên code, O(9) nếu bạn tìm ra được quy luật để áp dụng quy tắc nhân và dùng loop (mà nó vẫn là O(1) :v)

Mở rộng: Nếu các bạn tìm ra được quy luật, dù thay đổi đề bài từ 1 tỉ thành 10ⁿ thì các bạn vẫn áp dụng được cách làm trên với ĐPT là O(n) thay vì O(10ⁿn)

Vấn đề 2: Trong 1 thùng chứa bóng, có r quả bóng đỏ được đánh số từ 1 đến r, g quả bóng lục được đánh số từ 1 đến g, và b quả bóng lam được đánh số từ 1 đến b. Hỏi có bao nhiêu cách để chọn ra 3 quả bóng trong thùng đó sao cho cả 3 quả đều khác màu và khác số?

Naive Solution: Ta chỉ cần lồng 3 loop vào nhau, khi nào thấy được bộ 3 số khác nhau thì cộng đáp án thêm 1.

ĐPT: O(rgb)

Efficient Solution: Gọi (x, y, z) là 1 hoán vị của (r, g, b) sao cho x ≤ y ≤ z

Ta sẽ thực hiện 3 bước chọn như sau:

Chọn bóng có màu x: Có x cách chọn
Chọn bóng có màu y: Có y - 1 cách chọn, vì số của quả bóng này phải khác với số của quả trước.
Chọn bóng có màu z: Có z - 2 cách chọn, vì số của quả bóng này phải khác với số của 2 quả trước.

Áp dụng quy tắc nhân, có tổng cộng x * (y - 1) * (z - 2) cách chọn bóng.

“Khoan! Vì sao ta lại chọn bóng như vậy? Tại sao lại không chọn bóng màu z trước?”

Thực ra đây cũng là lí do mình sắp lại thứ tự của 3 số đó. Nếu chúng ta chọn bóng màu z trước, sẽ có nhiều trường hợp xảy ra, ví dụ như là trường hợp số của quả được chọn nhỏ hơn x hoặc lớn hơn x, dẫn đến việc phải xét nhiều trường hợp hơn, dễ rối hơn. Chọn có thứ tự như trên tạo được sự chắc chắn, ví dụ như sau khi chọn xong quả bóng ở bước 1, số của quả bóng đó chắc chắn thấp hơn y vì số đó đã thấp hơn x rồi, như vậy chúng ta chắc chắn loại trừ được 1 cách chọn bóng.

ĐPT: O(1)

Mở rộng: Khi thay đổi đề bài thành n màu bóng, các bạn hoàn toàn có thể áp dụng được cách làm trên với ĐPT là O(n log n) (vì phải sắp xếp lại dãy trước) bù cho ĐPT lũy thừa O(cⁿ)

Tạm kết

Trên đây là 2 quy tắc đơn giản nhưng hết sức quan trọng trong các phương pháp đếm, giúp giảm đáng kể thời gian thực hiện bài toán. Hy vọng bài viết này giúp ích cho bạn!

Nguồn: https://codelearn.io/sharing/dem-trong-lap-trinh