Yêu cầu số lượng tối thiểu các hoạt động để tính tổng thành chuỗi nhị phân S bằng cách sử dụng C ++.

Tuyên bố vấn đề

Cho một chuỗi nhị phân str. Tìm số thao tác tối thiểu cần thực hiện để tạo số được biểu diễn bởi str. Chỉ có thể thực hiện các thao tác sau -

• Thêm 2 ^x
• Trừ 2 ^x

Nếu chuỗi nhị phân là “1000” thì chúng ta chỉ phải thực hiện 1 thao tác tức là thêm 2 ³

Nếu chuỗi nhị phân là “101” thì chúng ta phải thực hiện 2 thao tác tức là thêm 2 ² + 2 ⁰

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;
}

Đầu ra

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