2

Twitter 経由で centerofmath.org からこのパズルを見つけました。

10 桁の数字があり、左端の数字が数字のゼロの数でもあり、左から 2 番目の数字が 1 の数字であり、最後の数字 (または右端の数字) がその数字の 9 の数字になるまで続きます。 . この番号は何ですか? また、一意ですか?

パズルを解くために 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 でなければならないことがわかっています。そうしないと、桁数が多すぎます。それを利用してみてください。

たとえば、条件sum(int(n) for n in num) == len(num)が満たされた数値のみを生成するようにyielderを変更すると、意味をなさないことがすでにわかっている数値の高価なループでチェックする必要がなくなります。

于 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 に答える