如何用符号+ * ()和1以最小的代价表达整数？

Question

任务是使用符号+ * ( )（加法、乘法和括号）和数字1构建整数。您将获得一个整数，必须输出使用最少字符的表达式。例如：

4    = 1+1+1+1  
23   = 11+11+1  
242  = (11+11)*11  
1000 = 1+(1+1+1)*(1+1+1)*111 
1997 = (1+1)*(1+1+1)*111+11*11*11 

- user2807293

---

漂亮的问题，不适合在SO上讨论。 - tacaswell

我认为这并不是离题。只需添加一些你尝试过的代码，它就完全符合主题。 - Hari Menon

@tcaswell（和其他投票关闭的人）算法设计在SO上完全可以。 SO不仅限于“如何解析C中的字符串？” - 更高级别的问题在这里也受到欢迎，因为它们与编程密切相关。一旦思路清晰 - 就可以从算法构建一个程序（代码）。这个问题非常符合主题。 - amit

11**11是这个任务的有效表达式吗？ - dansalmo

我有一个非常棒的答案回答这个问题，但是这个评论框太小了装不下。投票重新打开。 - Colonel Panic

Answer 1

您可以使用动态规划，对于每个小于n的数字i，计算计算i的最短表达式和可用于乘法上下文中的计算i的最短表达式。通常，第二个表达式将比第一个表达式长：例如，2可以构造为“1+1”，但如果您想要在乘法中使用2，则会变成“(1+1)”。

以下是一些未经优化的代码，可打印出所有数字的最短解决方案高达2000。它在我的笔记本电脑上运行了略微超过2秒钟，但有很大的空间可以从代码中删除所有字符串构造。它以O(n ^ 2)时间运行。

def getbest(a, b):
    return a or b if not (a and b) else min((a, b), key=len)

def minconstruct(n):
    res = [[None, None] for _ in range(n + 1)]
    for i in xrange(1, n + 1):
        if set(str(i)) == set('1'):
            res[i][0] = res[i][1] = str(i)
        for j in xrange(1, i // 2 + 1):
            sol = '%s+%s' % (res[j][0], res[i-j][0])
            res[i][0] = getbest(res[i][0], sol)
            res[i][1] = getbest(res[i][1], '(' + sol + ')')
        for j in xrange(2, i):
            if i % j != 0:
                        continue
            sol = '%s*%s' % (res[j][1], res[i//j][1])
            res[i][0] = getbest(res[i][0], sol)
            res[i][1] = getbest(res[i][1], sol)             
    return res

r = minconstruct(2000)
for i, x in enumerate(r[1:]):
    print '%4d: %s' % (i, x[0])

- Paul Hankin

---

就我所见，这不是动态规划，而是简单的暴力算法。 - Roman Pekar

@RomanPekar，每个i的解决方案都取决于已经计算出的较小数字的结果。这不是动态规划吗？为什么要投反对票？ - Paul Hankin

抱歉，尽管它的功能不正确，我已经删除了踩（必须进行一些编辑）。你的实现很整洁，但仍然是暴力解法，我的解决方案更快，但代码不太优雅，稍后必须检查是否可以使其更清晰。 - Roman Pekar

@RomanPekar：这绝对是动态规划。 - Neil G

@NeilG 是的，我的错，我会再去复习Tim Roughgarden的讲座 :) - Roman Pekar

Answer 2

这是我的递归解决方案。在我的平板电脑上，它可以处理大约2000个元素，用时约1.4秒：

import math

def to_onestr(n, numbers=None, divs=None):
    if numbers is None:
        numbers = [None] * (n + 1)
        numbers[0] = ('', False)
    if divs is None:
        divs = get_divs(n)

    if numbers[n] is None:
        s = str(n)
        # Default representation is 11111 or 1+1+1+1
        if s == '1'*len(s): res = (s, False)
        else: res = ("+".join(['1'] * n), True)

        # Find all representations d*k + r, d < k
        for d in divs:
            if d >= n: break
            k, r = divmod(n, d)
            if k < d: d, k = k, d
            k_res, r_res, d_res = to_onestr(k, numbers, divs), to_onestr(r, numbers, divs), to_onestr(d, numbers, divs)

            res_str, res_bool = '', False
            if d != 1:
                res_str += '({})*'.format(d_res[0]) if d_res[1] else d_res[0] + '*'
            res_str += '({})'.format(k_res[0]) if k_res[1] else k_res[0]

            if d != 1 and len(k_res[0]) * d + d - 1 < len(res_str):
                res_str = '+'.join([k_res[0]]*d)
                res_bool = True

            if r != 0:
                res_str += '+{}'.format(r_res[0])
                res_bool = True
            if len(res_str) < len(res[0]):
                res = (res_str, res_bool)
        numbers[n] = res
    return numbers[n]

def get_divs(n):
    p = [1] * (n + 1)
    # Get all prime numbers + all numbers which contains only 1 + all numbers we could get from 11..1 by multiplication
    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if p[i] == 1:
            for j in range(i * i, n, i):
                if j % i == 0:
                    p[j] = 0

    for x in xrange(2, len(str(n)) + 1):
        i = int('1'*x)
        j = i
        while j <= n:
            p[j] = 1
            j = j * i

    return [i for (i, v) in enumerate(p) if v == 1 and i > 1]

速度测试：

>>> timeit('to_onestr(2000)', 'from __main__ import to_onestr', number=1)
1.1375278780336457
>>> timeit('to_onestr(4000)', 'from __main__ import to_onestr', number=1)
3.6481025870678696
>>> timeit('to_onestr(6000)', 'from __main__ import to_onestr', number=1)
7.732885259577177

也测试了 @Anonymous 的方法。

>>> timeit('minconstruct(2000)', 'from __main__ import minconstruct', number=1)
12.012599471759474

- Roman Pekar

---

测试你的代码，但是"len(str(n)) + 1]))"有些问题。 - tcpiper

@Pythoner 在提交时不得不离开，稍微修改了解决方案，现在它可以填充从0到n的所有数字列表。 - Roman Pekar

@Anonymous 是的，我也认为我需要尽量减少1的数量。必须对新代码进行一些测试。 - Roman Pekar

@Anonymous已经修复了，但代码并不像我想要的那样干净 :( - Roman Pekar

@Pythoner 谢谢，已修复（我想是的，现在无法测试，正在用手机写）。今天没有时间进一步优化代码，代码看起来很混乱，但我仍然喜欢这个想法。 - Roman Pekar