Số cộng trong C ++

Giả sử chúng ta có một chuỗi chỉ chứa các chữ số từ '0' đến '9', chúng ta phải viết một hàm để xác định đó có phải là một số cộng hay không. Số cộng là một chuỗi mà các chữ số của nó có thể tạo thành chuỗi cộng. Một chuỗi phụ gia hợp lệ phải chứa ít nhất ba số. Ở đây ngoại trừ hai số đầu tiên, mỗi số tiếp theo trong dãy phải là tổng của hai số trước đó. Vì vậy, nếu đầu vào là “112358”, thì câu trả lời sẽ là đúng, là 2 =1 + 1, 3 =1 + 2, 5 =2 + 3, 8 =3 + 5.

Để 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 phương thức được gọi là ok (), phương thức này sẽ lấy s, chỉ mục, trước đó, chiếm ưu thế2
if index> =size of s, thì trả về true
req:=pres1 + prev2 và num:=req dưới dạng chuỗi
x:=một chuỗi trống
cho tôi trong phạm vi chỉ mục đến kích thước của s
- x:=x + s [i]
- nếu x =num và ok (s, i + 1, prev2, x là số nguyên), thì trả về true
trả về false
Từ phương thức chính, hãy làm như sau -
n:=kích thước của num
cho tôi trong phạm vi từ 1 đến n - 2
- cho j trong phạm vi từ 1 đến i
  - s1:=chuỗi con của num từ 0 đến j - 1
  - s2:=chuỗi con của num từ j đến i - j
  - x:=tối đa của kích thước s1 và kích thước s2
  - nếu x> n - i, thì hãy chuyển sang lần lặp tiếp theo
  - nếu (s1 [0] là 0 và kích thước là s1> 0) HOẶC (s2 [0] là 0 và kích thước là s2> 1), thì bỏ qua lần lặp tiếp theo
  - nếu ok (num, i + 1, s1 là số nguyên và s2 là số nguyên) là true, thì trả về true
trả về false

Ví dụ (C ++)

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

Đầu vào

"112358"

Số cộng trong C ++

Ví dụ (C ++)

Đầu vào

Đầu ra