损坏的计算器

问题描述

问题陈述:

计算器坏了.仅少数数字[0 to 9]和运算符[+, -, *, /]在起作用.

There is a broken calculator. Only a few of the digits [0 to 9] and operators [+, -, *, /] are working.

要求编号需要使用工作数字和运算符组成.键盘上的每次按下都称为操作.

A req no. needs to be formed using the working digits and the operators. Each press on the keyboard is called an operation.

• =运算符始终处于工作状态，并在请求编号为1时使用.由运算符组成.
如果要求编号为
• -1，则需要打印.不能使用数字组成，且提供的运算符或超过最大编号.允许的操作数.
• 在计算结果的任何时候，没有.应该变成负数或超过999 [0 <= calcno <= 999]

• = operator is always working and is used when the req no. is formed using operators.
• -1 needs to be printed in case the req no. cannot be formed using the digits and the operators provided OR exceeds the max no. of operations allowed.
• At no point in time during the calculation of the result, the no. should become negative or exceed 999 [0 <= calcno <= 999]

输入:

• 第一行包含3个以空格分隔的编号:否.的工作数字，没有.最大工作运营商数量不允许进行任何操作.
• 第二行包含用空格分隔的工作数字.
• 第三行包含以空格分隔的工作运算符[1代表+，2代表-，3代表*，4代表/].
• 第4行包含要求.不成立.

• 1st line contains 3 space separated nos: no. of working digits, no. of working operators, max. no of operations allowed.
• 2nd line contains space separated working digits.
• 3rd line contains space separated working operators [1 represents +, 2 represents -, 3 represents *, 4 represents /].
• 4th line contains the req. no to be formed.

输出:

找到最低要求操作以形成要求编号.

Find the minimum required operations to form the req no.

示例:

输入1:

2 1 8
2 5
3
50

可能的方式:

案例1: 2*5*5 =-> 6 operations
情况2: 2*25 =-> 4 operations

Case 1: 2*5*5 = -> 6 operations
Case 2: 2*25 = -> 4 operations

---

输入2:

3 4 8
5 4 2
3 2 4 1
42

可能的方式:
情况1:42-> 2 operations(直接键入)
情况2:5*4*2+2 =-> 8 operations
..........其他方式

Possible ways:
Case 1: 42 -> 2 operations (direct key in)
Case 2: 5*4*2+2 = -> 8 operations
..........some other ways

---

我没有针对此问题的正确方法.
有人可以提出一些解决问题的方法吗?

---

I am not getting a proper approach to this problem.
Can someone suggest some ways to approach the problem.

推荐答案

提供更多上下文，vish4071在评论中说.

Giving some more context what vish4071 said in the comments.

通过以下方式设置图形:从根开始图形，然后是新节点，这是您要大声使用的数字(例如，该数字是2和5).并逐级建立图形.按照以下方式创建每个级别，一个新节点将由加号或您大声使用的运算符组成.每个运算符之后都不能再有另一个运算符.

Set up a graph in the following way:Starting the graph with a root, and than the new node are the number you're aloud to use (for the example this is 2 and 5). And build up the graph level by level.Make each level in the following way, a new node will consist either of adding number or a operator which you're aloud to use. After each operator there cannot be another operator.

如果该节点的值大于目标值，则大于杀死该节点(目标作为尾注)，这仅适用于此示例(如果运算符为*和+).如果您将能够使用-和/运算符，则此值不是vallid.

If the node has a higher value than the Target value, than kill the node (target as end note), this only works for this example (if the operators are * and +). If you would be able to use the - and / operator this is not vallid.

执行此操作直到找到所需的值，然后您便会得到级别(+1，由于=操作).

Do this till you find the required value, and the level (+1, due to the = operation) is you're answer.

下面是图形的例子

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


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
           \
            (*)

这比强行强制略胜一筹，也许有更好的方法.

This is slightly better than brute forcing, maybe there is a more optimal way.

这篇关于损坏的计算器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！