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 题有类似思想,详情参考
答案:906609