Last Updated: February 25, 2016
·
1.903K
· zuozuo

# Project Euler 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.

``````def largest_palindrome_product
[].tap {|arr|
100.upto(999).each do |i|
100.upto(999).each do |j|
prod = i*j
prod.to_s == prod.to_s.reverse! and arr << prod
end
end
}.max
end
p largest_palindrome_product
#output=>:     906609``````

``````def largest_palindrome_product_optimized
[].tap {|arr|
100.upto(999).each do |i|
i.upto(999).each do |j|
prod = i*j
prod.to_s == prod.to_s.reverse! and arr << prod
end
end
}.max
end
p largest_palindrome_product_optimized
#output=>:     906609``````

``````def largest_palindrome_product_optimized1
max = 0
100.upto(999).each do |i|
i.upto(999).each do |j|
prod = i*j
prod.to_s == prod.to_s.reverse! && prod > max and max = prod
end
end
max
end
p largest_palindrome_product_optimized1``````

``````abccba
= a*100000 + b*10000 + c*1000 + c*100 + b*10 +a*1
= a*(100001) + b*(10010) + c*(1100)
= 11*(9091*a + 910*b + 100*c)``````

``````abccba = 11*(9091*a + 910*b + 100*c)
= 11 * x * y
= (11*x) * y

99 < 11*x, y <= 999
9  <     x   <= 90
99 <     y   <= 999``````

``````def largest_palindrome_product_best
top = 999*999
9.downto(0) do |a|
9.downto(0) do |b|
9.downto(0) do |c|
num = 9091*a + 910*b + 100*c
num > top and next
90.downto(10).each do |divider|
num%divider == 0 && num/divider < 999 and return num*11
end
end
end
end
100001
end
p largest_palindrome_product_best
#output=>:     906609``````

``````require 'benchmark'
Benchmark.bmbm do |results|
results.report("first")
{ largest_palindrome_product }
results.report("optimized")
{ largest_palindrome_product_optimized }
results.report("optimized1")
{ largest_palindrome_product_optimized1 }
results.report("best")
{ largest_palindrome_product_best }
end``````

``````Rehearsal ------------------------------------------
first        0.430000   0.000000   0.430000 (0.424545)
optimized    0.200000   0.000000   0.200000 (0.209293)
optimized1   0.220000   0.000000   0.220000 (0.212343)
best         0.000000   0.000000   0.000000 (0.000646)
-----------------------------------total: 0.850000sec

user     system      total       real
first        0.430000   0.000000   0.430000 (0.427489)
optimized    0.210000   0.000000   0.210000 (0.211230)
optimized1   0.210000   0.000000   0.210000 (0.210999)
best         0.000000   0.000000   0.000000 (0.000624)``````

3.339K
0

153.2K
9

### Centered Text And Images In Github Markdown

135.6K
0

#### 3 Responses

over 1 year ago ·

@wrymax 嘿嘿，不过这个网站很棒吧，最近发现的。貌似这上面都是老外。

over 1 year ago ·

over 1 year ago ·

#### Have a fresh tip? Share with Coderwall community!

Best #Ruby Authors
mcansky
130.2K
knoopx
109.8K
stevennunez
95.53K
Filed Under

Awesome Job