Toán tử ít nhất để biểu thị số trong C ++

Giả sử chúng ta có một số nguyên dương x, chúng ta sẽ viết biểu thức có dạng x (op1) x (op2) x (op3) x ... trong đó op1, op2, v.v. là các toán tử. Và các toán tử này có thể là cộng, trừ, nhân hoặc chia. Ví dụ, với x =3, chúng ta có thể viết 3 * 3/3 + 3 - 3 là giá trị của 3. Có một số quy tắc, những quy tắc này như sau -

• Toán tử chia (/) trả về số hữu tỉ.

• Không có dấu ngoặc đơn nào được đặt ở bất kỳ đâu.

• Chúng tôi sử dụng thứ tự các phép toán thông thường - phép nhân và phép chia có mức độ ưu tiên cao hơn phép cộng và phép trừ.

• Toán tử phủ định riêng không được phép.

Chúng ta phải viết một biểu thức với số lượng toán tử ít nhất sao cho biểu thức bằng với mục tiêu đã cho. Vì vậy, chúng tôi sẽ tìm ra số lượng toán tử ít nhất.

Vì vậy, nếu đầu vào là x =4, target =15, thì đầu ra sẽ là 3, vì chúng ta có thể biểu thị 15 là 4 * 4 4/4

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

• nếu mục tiêu giống với x, thì -

  • nếu x> target, thì -

    • trả về tối thiểu (x - target) * 2 và (target * 2) - 1

• tổng:=x, t:=0

• while sum

  • sum:=sum * x

  • (tăng t lên 1)

• nếu tổng giống với mục tiêu, thì -

  • trả lại t

• l:=inf, r:=inf

• if sum - target target, then -

  • r:=lessOpsExpressTarget (x, sum - target)

• l:=lessOpsExpressTarget (x, target - (sum / x))

• trả về 1 + tối thiểu l và r

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int leastOpsExpressTarget(int x, int target) {
      if(target == x) return 0;
      if(x > target){
         return min((x - target) * 2, (target * 2) - 1);
      }
      lli sum = x;
      int t = 0;
      while(sum < target){
         sum *= x;
         t++;
      }
      if(sum == target) return t;
      int l = INT_MAX;
      int r = INT_MAX;
      if(sum - target < target){
         r = leastOpsExpressTarget(x, sum - target) + t;
      }
      l = leastOpsExpressTarget(x, target - (sum / x)) + t - 1;
      return min(l, r) + 1;
   }
};
main(){
   Solution ob;
   cout << (ob.leastOpsExpressTarget(4, 15));
}

Đầu vào

4, 15

Đầu ra

3