Bỏ qua

Bài toán phân chia đạt tích lớn nhất

Question

Cho một số nguyên dương \(n\), hãy phân chia nó thành tổng của ít nhất hai số nguyên dương sao cho tích của các số nguyên này đạt giá trị lớn nhất, như được thể hiện trong hình dưới đây.

Định nghĩa bài toán phân chia đạt tích lớn nhất

Giả sử chúng ta phân chia \(n\) thành \(m\) thừa số nguyên, trong đó thừa số thứ \(i\) được ký hiệu là \(n_i\), tức là

\[ n = \sum_{i=1}^{m}n_i \]

Mục tiêu của bài toán này là tìm tích lớn nhất của tất cả các thừa số nguyên, cụ thể là

\[ \max(\prod_{i=1}^{m}n_i) \]

Chúng ta cần xác định nên chia thành bao nhiêu phần \(m\) và mỗi phần \(n_i\) nên bằng bao nhiêu.

Xác định chiến lược tham lam

Theo kinh nghiệm thực tế, tích của hai số nguyên thường lớn hơn tổng của chúng. Giả sử chúng ta tách một thừa số \(2\) ra khỏi \(n\), tích thu được là \(2(n-2)\). Chúng ta so sánh tích này với \(n\):

\[ \begin{aligned} 2(n-2) & \geq n \newline 2n - n - 4 & \geq 0 \newline n & \geq 4 \end{aligned} \]

Như thể hiện trong hình dưới đây, khi \(n \geq 4\), việc tách ra một số \(2\) sẽ làm tăng tích số, điều này chỉ ra rằng các số nguyên lớn hơn hoặc bằng \(4\) đều nên được phân chia.

Chiến lược tham lam thứ nhất: Nếu phương án phân chia chứa một thừa số \(\geq 4\), nó nên được chia tiếp. Phương án phân chia cuối cùng chỉ nên chứa các thừa số \(1\), \(2\) và \(3\).

Việc phân chia làm tích số tăng lên

Tiếp theo, hãy xem xét thừa số nào là tối ưu. Trong số ba thừa số \(1\), \(2\) và \(3\), rõ ràng \(1\) là tệ nhất, bởi vì \(1 \times (n-1) < n\) luôn đúng, nghĩa là việc tách ra số \(1\) thực sự sẽ làm giảm tích số.

Như thể hiện trong hình dưới đây, khi \(n = 6\), chúng ta có \(3 \times 3 > 2 \times 2 \times 2\). Điều này có nghĩa là việc tách ra số \(3\) tốt hơn so với việc tách ra số \(2\).

Chiến lược tham lam thứ hai: Trong phương án phân chia, chỉ nên có tối đa hai số \(2\), vì ba số \(2\) luôn có thể được thay thế bằng hai số \(3\) để thu được tích lớn hơn.

Thừa số phân chia tối ưu

Tóm lại, chúng ta có thể rút ra các chiến lược tham lam sau đây.

  1. Nhập số nguyên \(n\), liên tục tách thừa số \(3\) cho đến khi số dư là \(0\), \(1\) hoặc \(2\).
  2. Khi số dư là \(0\), nghĩa là \(n\) là một bội số của \(3\), vì vậy không cần làm gì thêm.
  3. Khi số dư là \(2\), không phân chia thêm nữa mà giữ nguyên nó.
  4. Khi số dư là \(1\), vì \(2 \times 2 > 1 \times 3\), hãy thay thế số \(3\) cuối cùng và số \(1\) còn lại bằng hai số \(2\).

Triển khai mã nguồn

Như thể hiện trong hình dưới đây, chúng ta không cần dùng vòng lặp để phân chia số nguyên. Thay vào đó, chúng ta sử dụng phép chia nguyên để lấy số lượng số \(3\), ký hiệu là \(a\), và phép chia lấy dư để lấy số dư \(b\), ta có:

\[ n = 3 a + b \]

Vui lòng lưu ý rằng đối với trường hợp biên (edge case) \(n \leq 3\), bắt buộc phải tách ra một số \(1\), với tích thu được là \(1 \times (n - 1)\).

[file]{max_product_cutting}-[class]{}-[func]{max_product_cutting}

Phương pháp tính toán cho tích phân chia lớn nhất

Độ phức tạp thời gian (time complexity) phụ thuộc vào cách triển khai phép lũy thừa trong ngôn ngữ trình. Lấy Python làm ví dụ, có ba cách thường dùng để tính lũy thừa.

  • Cả toán tử ** và hàm pow() đều có độ phức tạp thời gian là \(O(\log⁡ a)\).
  • Hàm math.pow() gọi hàm pow() của thư viện C bên trong, thực hiện phép lũy thừa số dấu phẩy động, với độ phức tạp thời gian là \(O(1)\).

Các biến \(a\) và \(b\) chỉ sử dụng một lượng không gian phụ trợ hằng số, do đó độ phức tạp không gian (space complexity) là \(O(1)\).

Chứng minh tính đúng đắn

Chúng ta sử dụng chứng minh phản chứng (proof by contradiction) và chỉ xem xét trường hợp \(n \geq 4\).

  1. Tất cả các thừa số \(\leq 3\): Giả sử phương án phân chia tối ưu có chứa một thừa số \(x \geq 4\). Khi đó, nó có thể được chia tiếp thành \(2(x-2)\) để thu được tích lớn hơn (hoặc bằng). Điều này mâu thuẫn với giả định ban đầu.
  2. Phương án phân chia không chứa số \(1\): Giả sử phương án phân chia tối ưu có chứa một thừa số là \(1\). Khi đó, nó có thể được gộp vào một thừa số khác để thu được tích lớn hơn. Điều này mâu thuẫn với giả định ban đầu.
  3. Phương án phân chia chứa tối đa hai số \(2\): Giả sử phương án phân chia tối ưu có chứa ba số \(2\). Khi đó, chúng có thể được thay thế bằng hai số \(3\), tạo ra tích lớn hơn. Điều này mâu thuẫn với giả định ban đầu.