[Project Euler]Problem 4

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

问题4：
　　回文数：将一个数的数字按相反的顺序重新排列后，所得到的数和原来的数一样.
　　最大的可以表示为两个两位数的乘积的回文数是9009=91  99.
　　求最大的可以表示为两个三位数的乘积的回文数.

本题有两个思路：
　　1.循环两个三位数,判断乘积是否为回文数.
　　2.循环回文数,判断是否可以表示为两个三位数的乘积. 

思路一：
　　循环遍历一:
　　　　两个数的乘积符合交换律,所以遍历的时候可以只遍历 a>=b的数，这样子就减少了一半的遍历数目.
　　　　循环的终止,我们不需要将所有的乘积,当我们求出一个符合条件的result时,对于a*b<=result的值都可以不用遍历. 

View Code

def isPalindromic(n):
    return str(n)==''.join(reversed(str(n)))

def f1():
    result=0
    for i in range(999,99,-1):
        if i*999<=result:
            break
        for j in range(999,i-1,-1):
            if i*j<=result:
                break
            if isPalindromic(i*j) and i*j>result:
                result=i*j;
    return result

　　优化:
　　　　P=x*100000+y*10000+z*1000+z*100+y*10+x
　　　　  =x*100001+y*10010+z*1100
　　　　  =11*(x*9091+y*910+z*100)

　　　　所以P=a*b, a,b中必有一个是11的倍数.

View Code

def f2():
    result=0
    for i in range(999,99,-1):
        if i*999<=result:
            break
        for j in range(999 if i%11==0 else 990,i-1,-1 if i%11==0 else -11):
            if i*j<=result:
                break
            if isPalindromic(i*j) and i*j>result:
                result=i*j;
    return result

　　循环遍历二:
　　　　前面是一行一行遍历，也可以对角线遍历.
　　　　对角线上两数的不变, 易知对角线上的最大乘积为 (两数和/2)**2.此值小于result时停止遍历.

View Code

def f3():
    i=(999,999)
    result=0
    while (sum(i)/2)**2>result:
        while i[1]<=i[0]:
            if isPalindromic(i[0]*i[1]) and i[0]*i[1]>result:
                result=i[0]*i[1]
            i=(i[0]-1,i[1]+1)
        i=(999,sum(i)-1000)
    return result

思路二：
　　因为六位数的回文数都是 abccba形式的,所以我们可以将abc从999 循环到100形成从大到小的所有回文数.
　　现在要判断一个6位数是否为两个三位数的乘积我们可以用100到999的数去除他,如果有一个数,可以使余数为0,商小于等于999,大于等于100.那么此6位数可以表示为两个3位数的积.
　　优化:
　　　　1.我们不必用100到999所有的数去除,因为a*b=P,则a,b中必有一个数大于等于sqrt(P) .
　　　　2.我们不必判断商是否小于等于999而且大于等于100,对于sqrt(P)<=i<=999.
　　　　   j=P/i 不能是两位数,因为两位数*三位数<100*1000=100000.
　　　　　j=P/i也不可能是4位数,因为 i>=sqrt(P),所以j=P/i<=sqrt(P) <=j<=999.

View Code

性能