【欧拉计划第 4 题】最大回文数乘积 Largest palindrome product

攻城狮杰森

发布于 2022-06-03 13:10:46

2450

发布于 2022-06-03 13:10:46

文章被收录于专栏：技术集锦

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.

问题 4 最大回文数乘积

回文数的两种读法都是一样的。由两个 2 位数字的乘积构成的最大回文数是 9009 = 91 × 99。找出由两个 3 位数字的乘积构成的最大回文数。

思路分析

回文数就是一个从左往右读和从右往左读都是一样的数字，例如数字：9009、101

其实这道题没有什么更好的技巧，暴力可解

解题步骤：

依次枚举所有的三位数
计算它们的乘积
筛选所有乘积中是回文数的数字：回文乘积
找到所有回文乘积中的最大值，即所求

代码实现

/*
 * @Author: coder-jason
 * @Date: 2022-04-08 10:07:23
 * @LastEditTime: 2022-04-08 10:26:18
 */
#include <iostream>
#include <algorithm> 
using namespace std;

int ans; // 全局变量

bool judge(int a) { //判断乘积是否为回文数
    int temp = a, b = 0;
    while (temp) {
        b = b * 10 + temp % 10; // 数字反转(数位截取知识点),存到 b 中
        temp /= 10;
    }
    return a == b; //若是回文数，返回 true
}
int main() {
    for (int i = 100; i < 1000; i ++) // 仅检查100-999之间的数(保证三位数)
        for (int j = i; j < 1000; j ++){ // 双层循环保证每个三位数都做了乘积
            if (judge(i*j)) 
                ans = max(ans, i*j);
        }
    cout << ans << endl;
    return 0;
}

judge() 判断数字是否为回文数时，用到了数位截取，和 2021 年蓝桥杯省赛 C++ 组 B 题有类似思想，详情参考