1

我有一个任务要做。问题是这样的。你给一个数字，比如 x。该程序计算从 1 开始的数字的平方，并且仅当它是回文时才打印它。程序会继续打印这些数字，直到达到您提供的数字 x。

我已经解决了这个问题。它适用于 uptil x = 10000000。在合理的时间内执行时效果很好。我想提高我的代码的效率。如果需要，我愿意更改整个代码。我的目标是制作一个可以在大约 5 分钟内执行 10^20 的程序。

limit = int(input("Enter a number"))
def palindrome(limit):
 count = 1
 base = 1 
 while count < limit:
  base = base * base #square the number
  base = list(str(base)) #convert the number into a list of strings
  rbase = base[:] #make a copy of the number
  rbase.reverse() #reverse this copy
  if len(base) > 1: 
   i = 0
   flag = 1 
   while i < len(base) and flag == 1:
    if base[i] == rbase[i]: #compare the values at the indices
     flag = 1
    else:
     flag = 0
    i += 1
   if flag == 1:
    print(''.join(base)) #print if values match
 base = ''.join(base)
 base = int(base)
 base = count + 1
 count = count + 1
palindrome(limit)
4

5 回答 5

2

他是我的版本：

import sys

def palindrome(limit):
    for i in range(limit):
        istring = str(i*i)
        if istring == istring[::-1]:
            print(istring,end=" ")
    print()

palindrome(int(sys.argv[1]))

你的版本在我的机器上的时间：

pu@pumbair: ~/Projects/Stackexchange  time python3 palin1.py 100000
121 484 676 10201 12321 14641 40804 44944 69696 94249 698896 1002001 1234321 
4008004 5221225 6948496 100020001 102030201 104060401 121242121 123454321 125686521
400080004 404090404 522808225 617323716 942060249

real    0m0.457s
user    0m0.437s
sys     0m0.012s

对于我的：

pu@pumbair: ~/Projects/Stackexchange  time python3 palin2.py 100000
0 1 4 9 
121 484 676 10201 12321 14641 40804 44944 69696 94249 698896 1002001 1234321 
4008004 5221225 6948496 100020001 102030201 104060401 121242121 123454321 125686521
400080004 404090404 522808225 617323716 942060249

real    0m0.122s
user    0m0.104s
sys     0m0.010s

顺便说一句，我的版本给出了更多的结果（0、1、4、9）。

于 2013-08-17T18:32:52.393 回答
0

当然，这样的事情会表现得更好（避免不必要的额外列表操作）并且更具可读性：

def palindrome(limit):
  base = 1 
  while base < limit:
    squared = str(base * base)
    reversed = squared[::-1] 
    if squared == reversed:
       print(squared)

    base += 1

limit = int(input("Enter a number: "))
palindrome(limit)
于 2013-08-17T18:29:07.677 回答
0

我认为我们可以更轻松一点。

def palindrome(limit):
    count = 1
    while count < limit:
        base = count * count # square the number
        base = str(base) # convert the number into a string
        rbase = base[::-1] # make a reverse of the string
        if base == rbase:
            print(base) #print if values match
        count += 1

limit = int(input("Enter a number: "))
palindrome(limit)

字符串到数字和数字到字符串的转换是不必要的。可以比较字符串，这就是为什么你不应该做一个循环。

于 2013-08-17T18:29:27.777 回答
0

您可以在内存中保留一个方形回文列表直到某个限制（例如 L）。如果输入数字 x 小于 sqrt(L)，您可以简单地遍历回文列表并打印它们。这样你就不会遍历每个数字并检查其平方是否为回文。

您可以在此处找到方形回文列表：http ://www.fengyuan.com/palindrome.html

于 2013-08-17T18:32:06.523 回答
0

好的，这是我的程序。它缓存正方形的有效后缀（即，n^2 mod 10^k固定的值k），然后搜索具有该后缀并以反转后缀开头的正方形。这个程序非常快：在 24 秒内，它列出了 10^24 以内的所有回文方格。

from collections import defaultdict

# algorithm will print palindromic squares x**2 up to x = 10**n.
# efficiency is O(max(10**k, n*10**(n-k)))
n = 16
k = 6

cache = defaultdict(list)

print 0, 0 # special case

# Calculate everything up to 10**k; these will be the prefix/suffix pairs we use later
tail = 10**k
for i in xrange(tail):
    if i % 10 == 0: # can't end with 0 and still be a palindrome
        continue
    sq = i*i
    s = str(sq)
    if s == s[::-1]:
        print i, s
    prefix = int(str(sq % tail).zfill(k)[::-1])
    cache[prefix].append(i)

prefixes = sorted(cache)

# Loop through the rest, but only consider matching prefix/suffix pairs
for l in xrange(k*2+1, n*2+1):
    for p in prefixes:
        low = (p * 10**(l-k))**.5
        high = ((p+1) * 10**(l-k))**.5
        low = int(low / tail) * tail
        high = (int(high / tail) + 1) * tail
        for n in xrange(low, high, tail):
            for suf in cache[p]:
                x = n + suf
                s = str(x*x)
                if s == s[::-1]:
                    print x, s

样本输出：

0 0
1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
<snip>
111010010111 12323222344844322232321
111100001111 12343210246864201234321
111283619361 12384043938083934048321
112247658961 12599536942224963599521
128817084669 16593841302620314839561
200000000002 40000000000800000000004
于 2013-08-17T21:43:01.267 回答