查找使用指定数字范围计算数字所需的最小操作数

Question

让我从一个例子开始 - 我有一系列从1到9的数字.让我们说我想要的目标数是29.在这种情况下,所需的最小操作数将是(9*3)+2 = 2次操作.类似地,对于18,最小操作数是1(9*2 = 18).我可以使用4个算术运算符中的任何一个 - +, - ,/和*.

如何以编程方式找出所需的最少操作数？提前感谢您提供的任何帮助.

澄清: 仅限整数,在计算中不允许小数.即以下内容无效(来自以下评论):((9/2)+ 1)*4 == 22 我必须承认我没有彻底考虑这个问题,但就我的目的而言,十进制数字是否出现在计算中间并不重要.((9/2)+ 1)*4 == 22有效.对困惑感到抱歉.

Answer 1

对于设置 Y = [1..9] 且 n > 0 的特殊情况：

• n <= 9 : 0 次操作
• n <=18 : 1 次操作 (+)
• 否则：删除 Y 中找到的任何除数。如果这还不够，则对所有偏移量 -9 .. +9 的余数进行递归。偏移量 0 可以跳过，因为它已经被尝试过。

请注意在这种情况下如何不需要除法。对于其他 Y，这不成立。

该算法以 log(n) 为指数。精确的分析是比我更有代数知识的人的工作。

为了提高速度，请添加修剪以消除对较大数字的某些搜索。

示例代码：

def findop(n, maxlen=9999):
    # Return a short postfix list of numbers and operations

    # Simple solution to small numbers
    if n<=9: return [n]
    if n<=18: return [9,n-9,'+']

    # Find direct multiply
    x = divlist(n)
    if len(x) > 1:
        mults = len(x)-1
        x[-1:] = findop(x[-1], maxlen-2*mults)
        x.extend(['*'] * mults)
        return x

    shortest = 0

    for o in range(1,10) + range(-1,-10,-1):
        x = divlist(n-o)
        if len(x) == 1: continue
        mults = len(x)-1

        # We spent len(divlist) + mults + 2 fields for offset. 
        # The last number is expanded by the recursion, so it doesn't count. 
        recursion_maxlen = maxlen - len(x) - mults - 2 + 1

        if recursion_maxlen < 1: continue
        x[-1:] = findop(x[-1], recursion_maxlen)
        x.extend(['*'] * mults)
        if o > 0:
            x.extend([o, '+'])
        else:
            x.extend([-o, '-'])
        if shortest == 0 or len(x) < shortest:
            shortest = len(x)
            maxlen = shortest - 1
            solution = x[:]

    if shortest == 0:
        # Fake solution, it will be discarded
        return '#' * (maxlen+1)
    return solution

def divlist(n):
    l = []
    for d in range(9,1,-1):
        while n%d == 0:
            l.append(d)
            n = n/d
    if n>1: l.append(n)
    return l