首页 > itarticle > largest palindrome produc

largest palindrome produc

admin 11月 14, 2020 0

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)
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能