损坏的计算器

Question

问题陈述：

计算器坏了。只有少数数字 [0 to 9] 和运算符 [+, -, *, /] 有效。

请求编号需要使用工作数字和运算符来形成。每按一次键盘就称为一次操作。

= 运算符始终有效，并在请求号时使用。使用运算符形成。
-1 需要打印，以防请求编号。不能使用提供的数字和运算符组成 OR 超过最大数量。允许的操作。
在计算结果的任何时间点，没有。应该变为负数或超过 999 [0 <= calcno <= 999]

输入：

第一行包含 3 个 space 分隔的编号：编号。工作数字，没有。工作操作员，最大。不允许任何操作。
第二行包含 space 个分隔的工作数字。
第 3 行包含 space 个分隔的工作运算符 [1 表示 +，2 表示 -，3 表示 *, 4代表/].
第 4 行包含请求。没有形成。

输出：

找到 最少需要 操作以形成请求编号。

示例：

输入 1:

可能的方式：

案例一： 2*5*5 = -> 6 operations
案例2： 2*25 = -> 4 operations

4 is the req Answer

输入 2:

可能的方式：
情况 1：42 -> 2 operations（直接键入）
案例 2：5*4*2+2 = -> 8 operations
..........其他一些方式

2 is the req Answer

我没有找到解决这个问题的正确方法。
有人可以建议一些解决问题的方法。

Answer 1

给 vish4071 在评论中所说的更多上下文。

按以下方式设置图形：以根开始图形，然后是新节点是您大声使用的数字（例如，这是 2 和 5）。并逐层构建图表。按照以下方式制作每个级别，一个新节点将包括添加数字或您大声使用的运算符。每个运算符之后不能有另一个运算符。

如果节点的值高于目标值，则终止节点（目标作为尾注），这仅适用于此示例（如果运算符是 * 和 +）。如果您能够使用 - 和 / 运算符，则这不是无效的。

这样做直到找到所需的值，并且级别（+1，由于 = 操作）就是你的答案。

图表示例如下

for your first example:
D=0    D=1    
       5
      /
Root /
     \
      


D=1    D=2   d=3   d=4
            --2
           / 
          /
        (*)___5  --> reaches answer but at level 6
        /   
       /     (*)___2  --> complete
      /     /   \  5
     /     /
  2 /____25_252    --> end node
    \     \
     \     \ 
      \     
       \    225    --> end node
        \  /
         22__222   --> end node
           \            
            (*)

这比暴力破解稍微好一点，也许有更优化的方法。

Answer 2

    #include <bits/stdc++.h>
using namespace std;

int main() {
    // your code goes here
    int n,m,o;
    cin>>n>>m>>o;
    int arr[n];
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        q.push(make_pair(arr[i],1));
    }
    int op[m];
    for(int i=0;i<m;i++) cin>>op[i];
    unordered_map<int,int> mp;
    for(int i=0;i<m;i++) mp[op[i]]=1;
    int target;
    cin>>target;
    int ans=INT_MAX;
    while(!q.empty())
    {
        int num=q.front().first;
        int count=q.front().second;
        if(num==target) ans=min(ans,count);
        q.pop();
        for(int i=0;i<=4;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==0 and count+1<=o)
                {
                    q.push(make_pair(num*10+arr[j],count+1));
                }
                else
                {
                    if(i==1 and mp.find(i)!=mp.end() and count+3<=o)
                    {
                        q.push(make_pair(num+arr[j],count+3));
                    }
                    if(i==2 and mp.find(i)!=mp.end() and count+3<=o)
                    {
                        q.push(make_pair(abs(num-arr[j]),count+3));
                    }
                    if(i==3 and mp.find(i)!=mp.end() and count+3<=o)
                    {
                        q.push(make_pair(num*arr[j],count+3));
                    }
                    if(i==4 and mp.find(i)!=mp.end() and count+3<=o)
                    {
                        q.push(make_pair(num/arr[j],count+3));
                    }
                }
            }
        }
    }
    if(ans==INT_MAX) cout<<"-1"<<endl;
    else cout<<ans<<endl;
    
    return 0;
}

损坏的计算器

Broken Calculator

algorithm

recursion

memoization

dynamic-programming