最少的运算符来表达C ++中的数字

假设我们有一个正整数x，我们将写一个形式为x(op1)x(op2)x(op3)x ...的表达式，其中op1，op2等是运算符。这些运算符可以是加，减，乘或除。例如，在x = 3的情况下，我们可以写成3 * 3/3 + 3-3（其值为3）。有一些规则，如下所示-

• 除法运算符（/）返回有理数。

• 没有括号放在任何地方。

• 我们使用通常的运算顺序-乘法和除法的优先级高于加法和减法。

• 一元求反运算符是不允许的。

我们必须编写一个运算符数量最少的表达式，以使该表达式等于给定的目标。因此，我们将找到最少数量的运算符。

因此，如果输入像x = 4，target = 15，那么输出将是3，因为我们可以将15表示为4 * 4- 4/4

为了解决这个问题，我们将遵循以下步骤-

• 如果目标与x相同，则-

• 返回（x-目标）* 2和（target * 2）-1的最小值

• 如果x>目标，则-

• 和：= x，t：= 0

• 而总和<目标，做-

• 总和：=总和x

• （将t增加1）

• 如果总和与目标相同，则-

• 返回t

• l：= inf，r：= inf

• 如果sum-目标目标，则-

• r：= minimumOpsExpressTarget(x,sum-target)

• l：= minimumOpsExpressTarget（x，目标-（sum / x））

• 返回1 + l和r的最小值

让我们看下面的实现以更好地理解-

示例

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

输入项

4, 15

输出结果

3