幸运数字 Python 程序输出不正确

Question

练习题 / 幸运字符串 所有提交到这个问题的内容都是公开的。查看所有提交。

幸运数字是只包含“4”和/或“5”的数字。比如说，4、5、44、54、55、444都是幸运数字，而457、987、154就不是。

幸运数字序列是指所有幸运数字按升序排列的序列，比如4、5、44、45、54、55、444、445、454、455……

现在我们把所有幸运数字（按升序）连接起来，形成一个幸运字符串“4544455455444445454455……”

给定一个数字n，你的任务是找到幸运字符串的第n个数字。如果这个数字是4，你就要输出“黑客”，如果是5，就输出“地球”。

输入：

第一行包含测试用例的数量T，接下来的T行每行包含一个整数n。

输出：

对于每个测试用例，如果幸运字符串的第n个数字是4，就输出黑客；如果是5，就输出地球。

限制条件：

1 <= t <= 10^5
1 <= n <= 10^15

以下是python代码：

test_cases = int(input())

final = []

def check(stra,num):
    if stra[num-1]==4:
        final.append("Hacker")
    else:
        final.append("Earth")

def GenStr(num):
    stra = "4"
    i = int(5)
    while(len(stra)<num+2):
        X = str(i)
        flag = True
        for j in range(len(str(i))):
            if(X[j]==4 or X[j]==5):
                pass
            else:
                flag = False
        if flag==True:
            stra+=X
        i+=1
    print(stra)
    return stra

for i in range(test_cases): 
    num = int(input())
    # generate string
    stra = GenStr(num)
    print("stra "+stra)
    # check the stat
    check(stra,num)

print("\n".join(final))

---

这段代码有什么问题吗？请不要介意，如果是个傻瓜式的错误，我只是个python编程的初学者。

Answer 1

正如 @Gassa 所说，直接暴力破解是行不通的；你需要一百万个千兆字节的内存，而且这样做会花费太长时间。

那么，分析解决方案会是什么样的呢？

如果你把“4”换成“0”，把“5”换成“1”，你会发现幸运数字序列变成了 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, ...。这应该很熟悉：它是所有1位二进制数按顺序排列，接着是所有2位二进制数，再接着是所有3位二进制数，依此类推。

所以如果你做类似这样的操作：

n = 491         # the digit we are seeking (for example)

d = 1           # number of binary digits
p = 2           # 2**d == number of items encoded
while n > d*p:  # sought digit is past the end of the next binary expansion?
    n -= d*p        # reduce offset by appropriate number of digits
    d += 1
    p *= 2

那么 n = 233, d = 6 就意味着我们在寻找第233个字符，在6位扩展中。

但我们可以进一步优化：

k, n = n // d, n % d

这意味着 n = 5, k = 38, d = 6 就是我们在查看第38个6位值的第5个字符。

注意：这里的所有偏移量都是从0开始的；如果你期待从1开始的偏移量，你需要相应地调整你的计算！

第38个6位值就是把38转换成6位的二进制值；你可以通过字符串操作来提取你想要的字符，但记住整数在内部是以二进制存储的，这样用一点数学就能得到我们想要的结果，可能会更简单：

digit = (k >> (d - n - 1)) & 1   # => 0

所以在原始字符串中的字符就是“4”。

Answer 2

1. 首先，有一点是明显错误的。stra 的值是 4，而 flag 总是变成 False。所以 stra 的值一直不会增加，这样 while(len(stra)<num+2): 就会变成一个无限循环。

2. 这个方法本身也无法完全解决问题，因为你无法构建一个长度为 10¹⁵ 的字符串，这样做会花费太多时间，而且根本放不进内存里。

Answer 3

关于你代码的评论

你的代码里有几个地方不太合理，需要改进：

• int(input()) 这行代码让用户输入内容，但没有提示他们输入什么。它会试图把用户输入的内容转换成整数，如果转换失败就会出错。
• 在Python中，使用 for i in range(len(x)) 这种写法几乎总是错的。因为字符串是可以直接遍历的（它们是字符的列表），所以你可以直接用 for j in str(i) 来遍历字符串。
• 使用 if x==True: 这种写法在Python中是永远不对的。我们更喜欢用 if x:。
• i = int(5) 这行代码没有必要把整数转换成整数。正确的写法是 i = 5。
• 尽量使用更好的变量名。你的代码和思路很难理解，因为里面有很多没有意义的标识符，比如 stra（这是字符串a吗？）、X、num 等等。

---

如何处理这个作业

我得坦白说：我不太明白这个作业的具体要求。什么是“测试用例”也不清楚，输入格式是什么（或者说输入来自哪里）也不明确。不过，我有一些建议可以帮助你处理这个问题：

• 找出只包含4或5的数字，这意味着要把它们当作字符串来处理。可以简单地用 len(str(x).replace('4', '').replace('5', '')) 来测试，当然还有更好的方法。
• 按升序列出“幸运数字”，可以使用内置的 sorted 函数来实现。
• 连接 这个列表可以用 ''.join(sorted(lucky_numbers)) 或类似的方法。
• 获取该列表的第n个数字，可以像之前那样使用字符串索引。