2

我通过 Twitter 从 centerofmath.org发现了这个谜题：

有一个十位数字，其中最左边的数字也是数字中零的个数，最左边的第二个数字是一的个数，依此类推，直到最后一个数字（或最右边的数字）是该数字中的九个数. 这个数字是多少，它是独一无二的吗？

我用 Python 写了一个程序来解决这个难题：

def yielder(exponent):
     i = 10**exponent
     while i < (10**(exponent+1))-1:
          yield i
          i += 1

def is_solution(num):
     l = list(num)
     #l.reverse()
     is_sol = True
     for i, e in enumerate(l):
          if int(e) != l.count(str(i)):
               is_sol = False
               break
     return is_sol

if __name__=="__main__":
     import sys
     ofile = open('solution.txt', 'w')
     j = int(sys.argv[1])
     print("checking between {0} and {1}".format(10**j, (10**(j+1))-1))
     ofile.write("Solutions between {0} and {1}:\n".format(10**j, (10**(j+1))-1))
     for x in yielder(j):
          if is_solution(str(x)):
              ofile.write('\t{0}\n'.format(x))
              print("solution is {0}".format(x))
     ofile.close()

我得到的解决方案是6210001000

但问题是需要几个小时才能解决。我想知道是否有一些我可以用来让它更快的技术

顺便说一句，这些是 10 9,999,999,999 之间的数字，它们是解决方案

Solutions between 10 and 99:
Solutions between 100 and 999:
Solutions between 1000 and 9999:
    1210
    2020
Solutions between 10000 and 99999:
    21200
Solutions between 100000 and 999999:
Solutions between 1000000 and 9999999:
    3211000
Solutions between 10000000 and 99999999:
    42101000
Solutions between 100000000 and 999999999:
    521001000
Solutions between 1000000000 and 9999999999:
    6210001000
4

2 回答 2

3

您可以通过使用更多逻辑来减少大量的数字检查。例如，您知道各个数字的总和必须为 10，否则数字的位数太多，因此请尝试利用这一点。

例如，您可以将您的 yielder 更改为仅生成sum(int(n) for n in num) == len(num)满足条件的数字，然后您无需检查您已经知道没有意义的数字的昂贵循环。

于 2012-10-03T08:03:44.737 回答
3

如果您构造数字而不是搜索它，它会快得多。

def to_the_number(n):
    digits=list(map(int,n))
    assert(len(digits))==10
    done = False
    while not done:
        done = True
        for i in range(10):
            if digits[i]!=digits.count(i):
                digits[i]=digits.count(i)
                print(digits)
                done = False
    return ''.join(map(str, digits))

并从任何数字开始：

>>> to_the_number('1234567890')
[1, 1, 3, 4, 5, 6, 7, 8, 9, 0]
[1, 1, 0, 4, 5, 6, 7, 8, 9, 0]
[1, 1, 0, 0, 5, 6, 7, 8, 9, 0]
[1, 1, 0, 0, 0, 6, 7, 8, 9, 0]
[1, 1, 0, 0, 0, 0, 7, 8, 9, 0]
[1, 1, 0, 0, 0, 0, 0, 8, 9, 0]
[1, 1, 0, 0, 0, 0, 0, 0, 9, 0]
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[8, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[8, 1, 0, 0, 0, 0, 0, 0, 1, 0]
[7, 1, 0, 0, 0, 0, 0, 0, 1, 0]
[7, 2, 0, 0, 0, 0, 0, 0, 1, 0]
[7, 2, 1, 0, 0, 0, 0, 0, 1, 0]
[7, 2, 1, 0, 0, 0, 0, 1, 1, 0]
[7, 2, 1, 0, 0, 0, 0, 1, 0, 0]
[6, 2, 1, 0, 0, 0, 0, 1, 0, 0]
[6, 2, 1, 0, 0, 0, 1, 1, 0, 0]
[6, 2, 1, 0, 0, 0, 1, 0, 0, 0]
'6210001000'
于 2012-10-03T08:43:42.060 回答