任务是使用符号+ * ( )
(加法、乘法和括号)和数字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
任务是使用符号+ * ( )
(加法、乘法和括号)和数字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
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])
这是我的递归解决方案。在我的平板电脑上,它可以处理大约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
>>> timeit('minconstruct(2000)', 'from __main__ import minconstruct', number=1)
12.012599471759474