Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Phân tích số nguyên (Integer Break) trong C++

Mô tả bài toán

Cho số nguyên dương n. Phân tích thành tổng của ít nhất 2 số nguyên dương để tích các số đó lớn nhất. Trả về tích lớn nhất.

Ví dụ: n=10 → 3+3+4, tích = 36.

Giải thuật Quy hoạch động / Toán học

DP: dp[i] = max_{1≤j.

Toán học tối ưu: Tách thành nhiều số 3 nhất có thể.

  • Nếu n % 3 == 0: toàn số 3.
  • Nếu n % 3 == 1: lấy một cặp 2+2 (thay 3+1) → 4 * 3^{(n-4)/3}.
  • Nếu n % 3 == 2: thêm một số 2 → 2 * 3^{(n-2)/3}.
(Đặc biệt: n=2→1, n=3→2).

Cài đặt C++ (Cách toán học O(1))

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        int q = n / 3, r = n % 3;
        if (r == 0) return pow(3, q);
        if (r == 1) return 4 * pow(3, q - 1);
        return 2 * pow(3, q);
    }
};

int main() {
    Solution ob;
    cout << ob.integerBreak(10); // 36
    return 0;
}

Độ phức tạp

  • Thời gian: O(log n) (hàm pow) hoặc O(1) dùng lũy thừa nhanh.
  • Không gian: O(1).