Tôi đang cố giải quyết vấn đề sau:Số nguyên n bit nhỏ nhất c có k 1-bit và là tổng của hai số nguyên n bit có g, bit h được đặt thành 1 (lập trình động)
Tìm nhỏ nhất n-bit số nguyên c có k 1-bit và là tổng của hai số nguyên n-bit có g, h bit thiết lập để 1. g, h, k < = n
Để bắt đầu, số nguyên n bit ở đây có nghĩa là chúng tôi có thể sử dụng tất cả các bit n, nghĩa là CPC giá trị của một số nguyên như vậy là 2^n - 1. Số nguyên được mô tả có thể không tồn tại. Rõ ràng là trường hợp k > g + h không có giải pháp và cho g + h = k câu trả lời chỉ là 2^k - 1 (đầu tiên k bit là 1 bit, k - n số không ở phía trước).
Đối với một số ví dụ về những gì chương trình có nghĩa vụ phải làm:
g = h = k = 4, n = 10 :
0000001111 + 0000001111 = 0000011110
15 + 15 = 30 (30 should be the output)
(4, 6, 5, 10):
0000011110 + 0000111111 = 0001011101
30 + 63 = 93
(30, 1, 1, 31):
1 + (2^30 - 1) = 2^30
Như tôi đã nghĩ về nó, đây là một vấn đề lập trình năng động và tôi đã chọn phương pháp sau đây: Hãy dp[g][h][k][n][c] là số nguyên được mô tả và c là một bit tùy chọn để thực hiện. Tôi cố gắng tái tạo lại các khoản tiền có thể tùy thuộc vào các bit đặt hàng thấp nhất. Vì vậy, dp[g][h][k][n + 1][0] là tối thiểu
(0, 0): dp[g][h][k][n][0]
(0, 0): 2^n + dp[g][h][k - 1][n][1]
(1, 0): 2^n + dp[g - 1][h][k - 1][n][0]
(0, 1): 2^n + dp[g][h - 1][k - 1][n][0]
Tương tự, dp[g][h][k][n + 1][1] là tối thiểu
(1, 1): dp[g - 1][h - 1][k][n][0]
(1, 1): dp[g - 1][h - 1][k - 1][n][1] + 2^n
(1, 0): dp[g - 1][h][k][n][1]
(0, 1): dp[g][h - 1][k][n][1]
Ý tưởng không phải là khó khăn nhưng tôi không thực sự có kinh nghiệm với những việc như vậy và thuật toán của tôi doesn 't làm việc ngay cả đối với trường hợp đơn giản nhất. Tôi đã chọn cách tiếp cận từ trên xuống. Thật khó cho tôi để xem xét tất cả các trường hợp góc. Tôi không thực sự biết nếu tôi đã chọn đúng cơ sở đệ quy, vv Thuật toán của tôi thậm chí không làm việc cho trường hợp cơ bản nhất cho g = h = k = 1, n = 2 (câu trả lời là 01 + 01 = 10). Không nên có câu trả lời cho g = h = k = 1, n = 1 nhưng thuật toán cung cấp cho 1 (về cơ bản là lý do tại sao ví dụ trước đây xuất kết quả là 1 thay vì 2). Vì vậy, ở đây có mã khủng khiếp của tôi (chỉ rất cơ bản C++):
int solve(int g, int h, int k, int n, int c = 0) {
if (n <= 0) {
return 0;
}
if (dp[g][h][k][n][c]) {
return dp[g][h][k][n][c];
}
if (!c) {
if (g + h == k) {
return dp[g][h][k][n][c] = (1 << k) - 1;
}
int min, a1, a2, a3, a4;
min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max();
if (g + h > k && k <= n - 1) {
a1 = solve(g, h, k, n - 1, 0);
}
if (g + h >= k - 1 && k - 1 <= n - 1) {
a2 = (1 << (n - 1)) + solve(g, h, k - 1, n - 1, 1);
}
if (g - 1 + h >= k - 1 && k - 1 <= n - 1) {
a3 = (1 << (n - 1)) + solve(g - 1, h, k - 1, n - 1, 0);
}
if (g + h - 1 >= k - 1 && k - 1 <= n - 1) {
a4 = (1 << (n - 1)) + solve(g, h - 1, k - 1, n - 1, 0);
}
min = std::min({a1, a2, a3, a4});
return dp[g][h][k][n][c] = min;
} else {
int min, a1, a2, a3, a4;
min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max();
if (g - 2 + h >= k && k <= n - 1) {
a1 = solve(g - 1, h - 1, k, n - 1, 0);
}
if (g - 2 + h >= k - 1 && k - 1 <= n - 1) {
a2 = (1 << (n - 1)) + solve(g - 1, h - 1, k - 1, n - 1, 1);
}
if (g - 1 + h >= k && k <= n - 1) {
a3 = solve(g - 1, h, k, n - 1, 1);
}
if (g - 1 + h >= k && k <= n - 1) {
a4 = solve(g, h - 1, k, n - 1, 1);
}
min = std::min({a1, a2, a3, a4});
return dp[g][h][k][n][c] = min;
}
}
Câu hỏi hay. Nhưng tôi tin rằng bạn nhảy quá nhanh đến kết luận sai (sử dụng lập trình động). Tôi sẽ tìm cách tiếp cận mang tính xây dựng hơn. Bằng cách giải quyết một vài trường hợp, như 1 <= k, g, h <= 3, bằng tay, bạn có thể nhận thấy một mẫu. Nitpick: "giá trị tối đa của một số nguyên như vậy là' 2^(n + 1) - 1' "- thực ra là' 2^n - 1'. – Gassa
@Gassa. Nếu bạn đang gợi ý rằng đối với g + h = k + 1 thì giải pháp là 10 + k, cho g + h = k + 2 nó là 110 + k và vân vân, bạn sai. Thứ nhất, có thêm một chút mẫu cho g + h - k> k. Thứ hai, cả hai đều có counterexamples! – Atin
Xin lỗi, tôi không có một mô hình cụ thể trong tâm trí. Thay vào đó, một phương pháp điều tra chung mà sẽ tiết lộ các mô hình - hoặc không tồn tại của nó, nếu đó thực sự là trường hợp. – Gassa