首页 | 新闻 | 交流 | 问吧 | 文档 | 手册 | 下载 | 博客

[Project Euler]Problem 4

作者:  时间: 2011-04-18

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

性能

函数运行时间(秒/1000次)
f1 9.368944676683855
f2 1.5683888121888505
f3 7.196826392766362
f4 0.9873344893079895


作者: class 发表于 2011-04-18 22:29 原文链接

评论: 0 查看评论 发表评论


最新新闻:
· 甲骨文测试显示近场通信系统速度过慢(2011-04-18 22:43)
· 微软发布Office 365公测版(2011-04-18 22:42)
· 惠普计划推出流媒体音乐服务挑战苹果谷歌(2011-04-18 22:26)
· 雅虎4月21日关闭新闻推荐服务Buzz(2011-04-18 22:11)
· 谷歌回击韩国搜索引擎垄断指控(2011-04-18 22:08)

编辑推荐:上周热点回顾(4.11-4.17)

网站导航:博客园首页  我的园子  新闻  闪存  小组  博问  知识库