Đề bài
Cho một chuỗi nhị phân str. Tìm số phép toán tối thiểu cần thực hiện để tạo ra số được biểu diễn bởi str. Chỉ có thể thực hiện các phép toán sau:
- Thêm 2x
- Trừ 2x
Nếu chuỗi nhị phân là "1000" thì chúng ta chỉ cần thực hiện 1 phép toán là Thêm 23.
Nếu chuỗi nhị phân là "101" thì chúng ta cần thực hiện 2 phép toán là Thêm 22 + 20.
Ví dụ
#include <iostream> #include <string> #include <algorithm> using namespace std; int getMinOperations(string s){ reverse(s.begin(), s.end()); int n = s.length(); int result[n + 1][2]; if (s[0] == '0') { result[0][0] = 0; } else { result[0][0] = 1; } result[0][1] = 1; for (int i = 1; i < n; ++i) { if (s[i] == '0') { result[i][0] = result[i - 1][0]; result[i][1] = 1 + min(result[i - 1][1], result[i - 1][0]); } else { result[i][1] = result[i - 1][1]; result[i][0] = 1 + min(result[i - 1][0], result[i - 1][1]); } } return result[n - 1][0]; } int main(){ string str = "101"; cout << "Minimum required operations = " << getMinOperations(str) << endl; return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Minimum required operations = 2