python上下颠倒的数字拼图。效率方面需要帮助

Question

倒数是一个整数，其中i 左起第个数字加上i 右边的第个数字是 总是等于10。例如13579是一个颠倒的数字，因为1+9=10，3+7=10和（因为 5是从左到右的第三个数字）5+5=10。 前几个颠倒的数字，按数字顺序是5，19，28，37，…，82，91，159

任务

编写一个程序来确定第n个倒数（按数字顺序）。 输入将由单个整数n（1<；n<；2^31）组成。你应该输出一个 给出第n个倒数的整数。在

我的代码

def upsidecheck(tocheck):
    intolist=list(map(int, str(tocheck)))
    x=0
    while x<(len(intolist)/2):
        if (intolist[x]+intolist[len(intolist)-x-1])!= 10 :
            return False
            break
        x+=1
    return True
print("which nth upsidedownnumber do you want?")
nth=int(input())
y=0
answer=0
for x in range (1,(2**31)):
    counter=upsidecheck(x)
    if counter == True:y+=1
    if y==nth:answer=x;break
print("the answeris",answer)

这个代码对于小于100的数字来说是可以的，但是对于像“1234”这样大的数字，它需要在两秒钟内运行，这应该会得到“4995116”的答案。在

一）确实有效，但时间太长（通常为30秒左右），需要在2秒钟内工作；（

提前感谢您的帮助。

注意：这不是为了考试/家庭作业等，只是为了帮助我准备考试

Answer 1

首先，我们需要一个函数来告诉我们哪些数字是颠倒的：

def is_ud(n):
    digits = [int(ch) for ch in str(n)]
    check = (len(digits) + 1) // 2
    return all(digits[i] + digits[-1 - i] == 10 for i in range(check))

然后我们生成一些值并查找模式：

^{pr2}$

这给了

1: 1
2: 9
3: 9
4: 81
5: 81
6: 729
7: 729

所以有81个4位数的解，729个6位数的解；这应该是有意义的，因为6位数的解看起来像“1”+（每个4位数的解）+“9”，“2”+（每个4位数的解）+“8”9“+（每个4位数的解决方案）+“1”-因此，每个4位数的解决方案有9个6位数的解决方案（如果您以这种方式生成它们，您将按升序生成它们）。同样，对于每一个4位数的解决方案，通过在中间粘贴一个5，有一个相应的5位数解。在

看看这张表，你应该可以看到，如果你想要（例如）第200个解，它必须有6位数；事实上，它必须是第19个6位数的解。更重要的是，因为19<；81，它必须看起来像“1”+第19个4位数的解决方案+“9”！在

现在，您已经拥有了编写递归解决方案以直接生成第n个倒挂数字所需的一切。祝你好运！在

Answer 2

由于暴力强制通过这里的所有数字不是一个选项，您需要首先解决数学问题：

1. 按升序生成“倒置”数字
2. 如果可能的话，确定有多少个“颠倒”的数字有一定的长度，因为你的指数上限相当高，甚至暴力生成这些数字。在

对于第一个，“颠倒”的数字是：

• 长度2n：a₁…a_na'_n…a'₁
• 长度2n+1：a₁…a_n5a'_n…a'₁
  其中a_i是除0以外的任何数字，a'_i是它的10个补码。在

因为相同长度的数字是一位数一位数地比较的，猜猜哪个顺序是升序的。在

第二次

• 长度2n或2n+1的“倒置”数都是a1…an所有可能组合的数目。在
• 因为前面的表达式非常简单，你甚至可以算出一个求和的公式——所有“倒装”数字的数目，直到长度N。在

剩下的部分很简单，我只想补充一下，^{}或{a2}可能对生成的算法很有用。在

Answer 3

这是一个有趣的问题。第一部分，正如其他人所说的，你想要任何位数的第n个数，所以如果你能找到位数较少的值的总数，你可以从值中减去它们，然后忽略它们。在

然后你有一个更简单的问题：找到第n个值，正好有k个数字。如果k是奇数，则中心数字为“5”，否则前半部分只是以n为底的9，但数字的范围是1..9。尾部是相同的基数9值，数字颠倒，使用9..1的范围表示0..8的值。在

此函数将一个值转换为以9为基数，但使用一个特定字符来表示每个数字：

def base9(n, size, digits):
    result = []
    for i in range(size):
        result.append(n%9)
        n //= 9
    return ''.join(digits[i] for i in reversed(result))

例如：

^{pr2}$

现在要打印第n个倒数第n个数字，正好是k位数，我们将其转换为以9为基数的数字，并在需要时插入一个“5”。在

def ud_fixed(n, k):
    """Upside down number of exactly k digits
    0 => 1..159..9
    1 => 1..258..9
    and so on
    """
    ln = k // 2
    left = base9(n, ln, "123456789")
    right = base9(n, ln, "987654321")[::-1]
    if k%2:
        return left + "5" + right
    else:
        return left + right

现在我们要做的就是数一数有多少更短的结果，然后忽略它们：

def upside_down(n):
    number = [1, 9]
    total = [1, 10]
    if n==1: return "5"
    while total[-1] < n:
        number.append(9*number[-2])
        total.append(total[-1]+number[-1])
    length = len(total)
    if length >= 2:
        n -= total[length-2]  # Ignore all the shorter results.
    return ud_fixed(n-1, length)

打印一些要检查的值：

if __name__=='__main__':
    for i in range(1, 21):
        print(i, upside_down(i))
    print(1234, upside_down(1234))

输出如下：

C:\Temp>u2d.py
1 5
2 19
3 28
4 37
5 46
6 55
7 64
8 73
9 82
10 91
11 159
12 258
13 357
14 456
15 555
16 654
17 753
18 852
19 951
20 1199
1234 4995116