A palindrome number reads the same both ways.The largest palindrome made from the product of two 2-digit numbers is 9009 = 91x91.
Find the largest palindrome made from the product of two 3-digit numbers.

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def ispalin(x):     #判断是否回文
i = 0
flag = True
while i < len(x)/2:
if(x[i] != x[-(i+1)]):
flag = False
break
i += 1
return flag

i = 999
largestpalindromeproduct = 0
while i >= 100:
j = 999 #从大到小计算,先算出最大回文数,以便跳过i*j小于的情况
while j >= i: #避免重复计算,比如999*998和998*999
if i*j <= largestpalindromeproduct:
break
if ispalin(str(i*j)):
largestpalindromeproduct = i*j
j -= 1
i -= 1
print(largestpalindromeproduct)

上面的方法还有可优化空间,如果仔细分析回文数,会发现3位数乘积所产生都是六位数,设回文数P,个位、十位、百位分别为x、y、z,那么

P = 100000x + 10000y + 1000z + 100z + 10y + x
P = 100001x + 10010y + 1100z
P = 11(9091x + 910y + 100z)
回文数总是11的倍数,那个上面程序中的i,j至少有一个会是11的倍数,所以可以改为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def ispalin(x):
i = 0
flag = True
while i < len(x)/2:
if(x[i] != x[-(i+1)]):
flag = False
break
i += 1
return flag


i = 999
largestpalindrome = 0
while i > 100:
if i%11 == 0:
j = 999
de = 1
else:
j = 990 #990是小于999的最大的11的倍数
de = 11
while j >= i:
if i*j <= largestpalindrome:
break
if(ispalin(str(i*j))):
largestpalindrome = i*j
j -= de
i -= 1

print(largestpalindrome)