จำนวนขั้นตอนในการลดจำนวนในการแทนไบนารีเป็นหนึ่งใน C++

สมมติว่าเรามีตัวเลข s ในรูปแบบเลขฐานสอง เราต้องหาจำนวนขั้นตอนเพื่อลดให้เป็น 1 ภายใต้กฎเหล่านี้ -

• หากจำนวนปัจจุบันเป็นเลขคู่ เราต้องหารด้วย 2

• หากตัวเลขปัจจุบันเป็นเลขคี่ คุณต้องบวก 1 เข้าไป

ดังนั้น หากอินพุตเป็นเหมือน "1101" ผลลัพธ์จะเป็น 6 เนื่องจาก "1101" เป็น 13 ดังนั้น 13 เป็นเลขคี่ บวก 1 และรับ 14 จากนั้น 14 จะเป็นเลขคู่ หารด้วย 2 และรับ 7 หลังจาก 7 เป็นเลขคี่ บวก 1 และรับ 8

จากนั้น 8 ก็เหมือนเดิม หารด้วย 2 ได้ 4 อีกครั้ง 4 เป็นเลขคู่ หารด้วย 2 ได้ 2 สุดท้าย 2 เป็นเลขคู่ หารด้วย 2 ได้ 1

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน addStrings() ซึ่งจะใช้อาร์เรย์ num1 อาร์เรย์ num2

• กำหนดอาร์เรย์ ret

• พก :=0, ผลรวม :=0

• ย้อนกลับ num1 และ num2

• ผม :=0, j :=0

• ในขณะที่ (i <ขนาดของ num1 หรือ j <ขนาดของ num2) ทำ −

  • ถ้าฉัน <ขนาดของ num1 และ j <ขนาดของ num2 แล้ว −

    • sum :=carry + (num1[i] + num2[j])

    • ใส่ sum mod 2 ที่ท้าย ret

    • พก :=ผลรวม / 2

    • (เพิ่ม i ขึ้น 1)

    • (เพิ่มขึ้น j โดย 1)

  • มิฉะนั้นเมื่อฉัน <ขนาดของ num1 แล้ว−

    • sum :=carry + (num1[i])

    • ใส่ sum mod 2 ที่ท้าย ret

    • พก :=ผลรวม / 2

    • (เพิ่ม i ขึ้น 1)

  • มิฉะนั้น

    • sum :=carry + (num2[j])

    • ใส่ sum mod 2 ที่ท้าย ret

    • พก :=ผลรวม / 2

    • (เพิ่มขึ้น j โดย 1)

• หากการพกพาไม่ใช่ศูนย์ ดังนั้น −

  • ใส่ carry ที่ส่วนท้ายของ ret

• i :=ขนาดของ ret

• ตอบ :=สตริงว่าง

• สำหรับ i>=0, ปรับปรุง (ลด i โดย 1) ทำ -

  • ans :=ans + (ret[i] + ASCII ของ '0')

• return (ถ้าขนาดของ ans เท่ากับ 0 ให้ป้อน "0" มิฉะนั้น ans)

• กำหนดฟังก์ชัน addBinary() ซึ่งจะรับอาร์เรย์ a, อาร์เรย์ b

• ส่งคืน addStrings(a, b)

• กำหนดอาร์เรย์ makeVector และคัดลอกจาก v

  • กำหนดอาร์เรย์ ret

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • แทรก v[i] - ASCII ของ '0' ที่ส่วนท้ายของ ret

  • รีเทิร์น

• จากวิธีหลักให้ทำดังนี้

• ยกเลิก :=0

• กำหนดอาร์เรย์ x =makeVector จาก s

• ในขณะที่ขนาดของ x> 1 ทำ −

  • (เพิ่มการถอยกลับโดย 1)

  • ถ้าองค์ประกอบสุดท้ายของ x เหมือนกับ 0 แล้ว −

    • ลบองค์ประกอบสุดท้ายออกจาก x

  • มิฉะนั้น

    • กำหนดอุณหภูมิอาร์เรย์ขนาด 1

    • อุณหภูมิ[0] :=1

    • x :=makeVector(addBinary(x, temp))

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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"));
}

อินพุต

"1101"

ผลลัพธ์

6