Số bước để giảm một số trong biểu diễn nhị phân thành một trong C ++

Giả sử chúng ta có một số s ở dạng nhị phân. Chúng tôi phải tìm số bước để giảm nó xuống còn 1 theo các quy tắc này -

Nếu số hiện tại là số chẵn, chúng ta phải chia nó cho 2.
Nếu số hiện tại là số lẻ, bạn phải thêm 1 vào số đó.

Vì vậy, nếu đầu vào là "1101", thì đầu ra sẽ là 6, như "1101" là 13. Vì vậy, 13 là số lẻ, thêm 1 và nhận được 14. Sau đó, 14 là chẵn, chia cho 2 và thu được 7. Sau 7 là số lẻ, thêm 1 và nhận được 8.

Sau đó 8 lại là chẵn, chia cho 2 và được 4. Lại 4 là chẵn, chia cho 2 được 2, cuối cùng là 2 chẵn, chia cho 2 được 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm addStrings (), điều này sẽ nhận một mảng num1, một mảng num2,
Xác định ret mảng
mang:=0, sum:=0
đảo ngược num1 và num2
i:=0, j:=0
while (i
- nếu tôi
  - sum:=carry + (num1 [i] + num2 [j])
  - chèn sum mod 2 vào cuối ret
  - mang:=sum / 2
  - (tăng tôi lên 1)
  - (tăng j lên 1)
- ngược lại khi tôi
  - sum:=carry + (num1 [i])
  - chèn sum mod 2 vào cuối ret
  - mang:=sum / 2
  - (tăng tôi lên 1)
- Nếu không
  - sum:=carry + (num2 [j])
  - chèn sum mod 2 vào cuối ret
  - mang:=sum / 2
  - (tăng j lên 1)
nếu carry là khác 0, thì -
- chèn mang vào cuối ret
i:=kích thước của ret
ans:=chuỗi trống
đối với i> =0, cập nhật (giảm i đi 1), thực hiện -
- ans:=ans + (ret [i] + ASCII của '0')
return (nếu kích thước của ans bằng 0 thì là "0", ngược lại là ans)
Xác định một hàm addBinary (), điều này sẽ nhận một mảng a, một mảng b,
trả về addStrings (a, b)
Xác định một makeVector mảng và sao chép từ v
- Xác định ret mảng
- để khởi tạo i:=0, khi i
  - insert v [i] - ASCII of '0' vào cuối ret
- trả lại ret
Từ phương thức chính, hãy làm như sau,
ret:=0
Xác định một mảng x =makeVector từ s
trong khi kích thước x> 1, do -
- (tăng ret lên 1)
- nếu phần tử cuối cùng của x giống 0, thì -
  - xóa phần tử cuối cùng khỏi x
- Nếu không
  - Xác định nhiệt độ mảng có kích thước 1
  - tạm thời [0]:=1
  - x:=makeVector (addBinary (x, temp))
trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string addStrings(vector<int> num1, vector<int> num2){
      vector<int> ret;
      int carry = 0;
      int sum = 0;
      reverse(num1.begin(), num1.end());
      reverse(num2.begin(), num2.end());
      int i = 0;
      int j = 0;
      while (i < num1.size() || j < num2.size()) {
         if (i < num1.size() && j < num2.size()) {
            sum = carry + (num1[i]) + (num2[j]);
            ret.push_back(sum % 2);
            carry = sum / 2;
            i++;
            j++;
         }
         else if (i < num1.size()) {
            sum = carry + (num1[i]);
            ret.push_back(sum % 2);
            carry = sum / 2;
            i++;
         }
         else {
            sum = carry + (num2[j]);
            ret.push_back(sum % 2);
            carry = sum / 2;
            j++;
         }
      }
      if (carry)
         ret.push_back(carry);
      i = ret.size() - 1;
      string ans = "";
      for (; i >= 0; i--)
         ans += (ret[i] + '0');
      return ans.size() == 0 ? "0" : ans;
   }
   string addBinary(vector<int>& a, vector<int>& b){
      return addStrings(a, b);
   }
   vector<int> makeVector(string v){
      vector<int> ret;
      for (int i = 0; i < v.size(); i++)
         ret.push_back(v[i] - '0');
      return ret;
   }
   int numSteps(string s){
      int ret = 0;
      vector<int> x = makeVector(s);
      while (x.size() > 1) {
         ret++;
         if (x.back() == 0) {
            x.pop_back();
         }
         else {
            vector<int> temp(1);
            temp[0] = 1;
            x = makeVector(addBinary(x, temp));
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.numSteps("1101"));
}

Đầu vào

"1101"

Số bước để giảm một số trong biểu diễn nhị phân thành một trong C ++

Ví dụ

Đầu vào

Đầu ra