ProjectEuler Problem 4: Largest palindrome product
Mar 17, 2014
Problem 4: Largest palindrome product #
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.
分析 #
两个3位数乘积能得到的最大回文数。
思路：首先要能判断一个数是否是回文数isPalindrome()，其次要能判断一个数能否是两个3位数的乘积isProduct()，最后从两个三位数的最大乘积999999=9989001开始，到最小乘积100100=10000递减，判断是否是回文数和乘积。重点是isPalindrome()函数如何判断回文数。C\C++中，可以通过对要判断的数n，获取每一位上的数字，计算逆序形成的数是否和原数n相等，相等则是回文数，不等则不是。Python中，就相当简单了，将数n转换为string类型，然后再逆置一下，判断与原string是否相等即可。
方法1 通过数字的拆分重组，判断是否是回文 #
如 n = 123，依次拆得 3，2，1，并且对 3，2，1进行重组，即 sum = 3 + 2 * 10 + 1 * 100 判断 n 是否等于 sum，相等则为回文数
C++ #
#include <stdio.h>
bool isPalindrome(int n)
{
int m=n, sum = 0;
while (m) {
sum = sum*10 + m%10; // m%10 the lowest digital
m /= 10;
}
return (n == sum);
}
int main()
{
int max = 0;
for(int i = 999; i > 100; i--){
for(int j=i-1; j >= 100; j--){
if( i*j > max && isPalindrome(i*j)){
max = i*j;
}
}
}
printf("%d\n", max);
return 0;
}
讲解一下 isPalindrome() 函数，以isPalindrome(n=1234)为例，具体过程如下：
- 初始化时: m=n, sum=0；m用于拆分
- 取m的个位数，m%10 = 4，sum = sum*10 +m%10 = 0 *10 + 4 = 4， m= m/10 = 123
- 取m的个位数，m%10 = 3，sum = sum*10 +m%10 = 4 *10 + 3 = 43， m= m/10 = 12
- 取m的个位数，m%10 = 2，sum = sum10 +m%10 = 4310 + 2 = 432，m= m/10 = 1
- 取m的个位数，m%10 = 1，sum = sum10 +m%10 = 43210 + 1 = 432，m= m/10 = 0，结束
如此，n=1234,sum=4321. 判断两者是否相等，即可知道n是否是回文数
Golang #
package main
import "fmt"
func isPalindrome(n int) bool {
m, sum := n, 0
for m > 0 {
sum = sum*10 + m%10
m /= 10
}
return (n == sum)
}
func main(){
max := 0
for i := 999; i > 100; i-- {
for j := i -1; j >= 100; j-- {
if( i*j > max && isPalindrome(i*j) ){
max = i*j
}
}
}
fmt.Println(max)
}
Python #
def isPalindrome(n):
m, sum = n, 0
while m > 0 :
sum = sum*10 + m%10
m = int(m/10)
return (n == sum)
max = 0
for i in range(999, 100, -1):
for j in range(i-1, 99, -1):
if i*j > max and isPalindrome(i*j) :
max = i*j
print(max)
方法2 将数字转换为字符串，再将字符串逆序，比较字符串 #
C++ #
相比方法1，仅仅改变了 isPalindrome 函数
#include <stdio.h>
#include <string.h>
bool isPalindrome(int n)
{
char strN[32] = {0};
snprintf(strN,32,"%d", n);
int len = strlen(strN);
for(int i=0; i<len/2; i++){
if(strN[i] != strN[len-1-i]) return false;
}
return true;
}
int main()
{
int max = 0;
for(int i = 999; i > 100; i--){
for(int j=i-1; j >= 100; j--){
if( i*j > max && isPalindrome(i*j)){
max = i*j;
}
}
}
printf("%d\n", max);
return 0;
}
Golang #
package main
import "fmt"
func isPalindrome(n int) bool {
strN := fmt.Sprintf("%d",n)
sz := len(strN)
for i := 0; i < sz/2; i ++ {
if strN[i] != strN[sz-1-i] {
return false
}
}
return true
}
func main(){
max := 0
for i := 999; i > 100; i-- {
for j := i -1; j >= 100; j-- {
if( i*j > max && isPalindrome(i*j) ){
max = i*j
}
}
}
fmt.Println(max)
}
Python #
def isPalindrome(n):
strN = str(n)
strReversed = strN[::-1]
return strN == strReversed
max = 0
for i in range(999, 100, -1):
for j in range(i-1, 99, -1):
if i*j > max and isPalindrome(i*j) :
max = i*j
print(max)
isPalindrome函数中，利用str(n)将n转换为字符串strN，然后利用strN的步长为-1的切片，将strN反转，赋值给strReversed。判断strN与strReversed是否相等即可。
利用列表推导方法和max函数将代码合成了一行
print( max([x*y for x in range(100,1000) for y in range(100,1000) if str(x*y) == str(x*y)[::-1]]) )
答案 #
906609
知识点 #
- 判断回文数
- 字符串反转