Computer >> Máy Tính >  >> Lập trình >> C ++

Số lần lật để tạo chuỗi nhị phân thay thế - Đặt 1 trong C ++

Giả sử bạn đã cung cấp một chuỗi nhị phân "10011". Để tạo một chuỗi nhị phân thay thế, chúng ta cần lật tối thiểu 2 ký tự là "10101".

Có hai khả năng cho chuỗi thay thế. Nó sẽ bắt đầu bằng 0 hoặc 1. Chúng tôi sẽ kiểm tra hai thay thế và đếm số lần lật cần thiết cho cả hai.

Và sau đó trả về giá trị tối thiểu của cả hai. Hãy xem một ví dụ.

Đầu vào 

binary = "10011"

Đầu ra 

2

Nếu chúng ta bắt đầu chuỗi bằng 0, thì chúng ta phải lật 3 lần. Và nếu chúng ta bắt đầu chuỗi bằng 1, thì chúng ta phải lật 2 lần. Mức tối thiểu là 2.

Thuật toán

  • Khởi tạo chuỗi nhị phân.
  • Đếm số lần lật bắt buộc để tạo chuỗi thay thế bắt đầu bằng 1.
  • Tương tự, hãy đếm số lần lật bắt buộc để tạo chuỗi thay thế bắt đầu bằng 0.
  • Tìm giá trị tối thiểu từ hai điểm trên.
  • In số liệu tối thiểu.

Thực hiện

Sau đây là cách thực hiện thuật toán trên trong C ++ 

#include <bits/stdc++.h>
using namespace std;
char flip(char binaryDigit) {
   return binaryDigit == '0' ? '1' : '0';
}
int getFlipCountToAlternateString(string binary, char expected) {
   int flipCount = 0;
   for (int i = 0; i < binary.length(); i++) {
      if (binary[i] != expected) {
         flipCount++;
      }
      expected = flip(expected);
   }
   return flipCount;
}
int main() {
   string binary = "10011";
   cout << min(getFlipCountToAlternateString(binary, '0'), getFlipCountToAlternateString(binary,       '1')) << endl;
   return 0;
}

Đầu ra

Nếu bạn chạy đoạn mã trên, bạn sẽ nhận được kết quả sau. 

2