ตัวเลขเสริมใน C++

สมมติว่าเรามีสตริงที่มีตัวเลขตั้งแต่ '0' ถึง '9' เท่านั้น เราต้องเขียนฟังก์ชันเพื่อระบุว่าเป็นตัวเลขบวกหรือไม่ หมายเลขการบวกเป็นสตริงที่มีตัวเลขสามารถสร้างลำดับการบวกได้ ลำดับการเติมที่ถูกต้องควรมีตัวเลขอย่างน้อยสามตัว ในที่นี้ ยกเว้นตัวเลขสองตัวแรก แต่ละหมายเลขในลำดับต่อมาจะต้องเป็นผลรวมของสองตัวก่อนหน้า ดังนั้นหากอินพุตเป็น “112358” คำตอบจะเป็นจริง เช่น 2 =1 + 1, 3 =1 + 2, 5 =2 + 3, 8 =3 + 5.

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

• กำหนดวิธีการที่เรียกว่า ok() ซึ่งจะใช้เวลา s, index, prev1, prev2

• ถ้า index>=size ของ s แล้วคืนค่า true

• req :=prev1 + prev2 และ num :=req เป็นสตริง

• x :=หนึ่งสตริงว่าง

• สำหรับฉันอยู่ในช่วงดัชนีถึงขนาดของ s

  • x :=x + s[i]

  • ถ้า x =num และ ok(s, i + 1, prev2, x เป็นจำนวนเต็ม) แล้วคืนค่า จริง

• คืนค่าเท็จ

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• n :=ขนาดของ num

• สำหรับผมอยู่ในช่วง 1 ถึง n – 2

  • สำหรับ j ในช่วง 1 ถึง i

    • s1 :=สตริงย่อยของ num จาก 0 ถึง j – 1

    • s2 :=สตริงย่อยของ num จาก j ถึง i – j

    • x :=สูงสุดของขนาด s1 และ s2

    • ถ้า x> n – i ให้ทำซ้ำต่อไป

    • ถ้า (s1[0] เป็น 0 และขนาดของ s1> 0) หรือ (s2[0] เป็น 0 และขนาดของ s2> 1) ให้ข้ามไปที่การวนซ้ำถัดไป

    • ถ้า ok(num, i + 1, s1 เป็นจำนวนเต็ม และ s2 เป็นจำนวนเต็ม) เป็นจริง ให้คืนค่า true

• คืนค่าเท็จ

ตัวอย่าง(C++)

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

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   bool ok(string s, int idx, lli prev1, lli prev2){
      if(idx >= s.size()) return true;
      lli req = prev1 + prev2;
      string num = to_string(req);
      string x = "";
      for(int i = idx; i < s.size(); i++){
         x += s[i];
         if(x == num && ok(s, i + 1, prev2, stol(x))) return true;
      }
      return false;
   }
   bool isAdditiveNumber(string num) {
      int n = num.size();
      for(int i = 1; i < n - 1; i++){
         for(int j = 1; j <= i; j++){
            string s1 = num.substr(0, j);
            string s2 = num.substr(j, i - j + 1);
            int x = max((int)s1.size(), (int)s2.size());
            if(x > n - i) continue;
            if((s1[0] == '0' && s1.size() > 1) || (s2[0] == '0' && s2.size() > 1)) continue;
            if(ok(num, i + 1, stol(s1), stol(s2))) return true;
         }
      }
      return false;
   }
};
main(){
   Solution ob;
   cout << (ob.isAdditiveNumber("112358"));
}

อินพุต

"112358"

ผลลัพธ์

1