036. 双基回文数(double-base palindromes)

十进制数585对应的二进制表示是1001001001,这两个数字都是回文数。求一百万以下十进制和二进制表示都是回文数的所有数字之和。(注意在两种进制下,回文数的首位都不能为零)

分析:此题至少有两种解法,第一种可以利用我们在第四题里已经编写的检验数学是否是回文数的函数,遍历一百万以下的所有数字,计算它的二进制表示,并分别检测十进制和二进制表示是否都是回文数,如果都是则加入到总和中,最后的总和即为所求。这种方法在我的电脑大约耗时640毫秒,尚可以接受,不过我们还有一种效率更高的算法。

我们可以考虑如下回文数的生成过程,比如说数字123可以生成两个回文数,分别是123321和12321。通过观察我们可以发现,每个数字都可以生成两个对应的回文数。不过根据题目要求,我们需要保证生成的回文数不能大于一百万,因此999是满足这个条件的最大数,它可以生成999999这个回文数,是一百万以下最大的回文数。因此,我们不需要遍历一百万以下的所有数字,而只需要遍历1到999这999个数字,可以将搜寻的规模缩小一千倍。

我们需要编写一个生成回文数的函数,它生成原数字对应的两个回文数。此外我们需要编写一个检测数字是否是回文数的函数,这个函数在第四题我们已经编写过了,这里引用即可。然后我们遍历从1至999的所有数字,生成两个对应的回文数并检测这两个回文数的二进制表示是否也为回文数,如果是则加入到总和中,最后的总和即为所求。执行这种算法在我的电脑上大约需要花费2.5毫秒,所耗时间大约缩小了256倍。

def make_palindrome(x):
    s = str(x)
    p1 = s + s[::-1]
    p2 = s + s[:-1][::-1]
    return int(p1),int(p2)

def main():
    is_palindrome = lambda x : x[-1]!=0 and x == x[::-1]
    res = 0
    for i in range(1,1000):
        p1,p2 = make_palindrome(i)
        p1_base2,p2_base2 = bin(p1)[2:],bin(p2)[2:]
        if is_palindrome(p1_base2):
            res = res + p1
        if is_palindrome(p2_base2):
            res = res + p2
    return res