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

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

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 位数字的乘积构成的最大回文数。

思路分析

回文数就是一个从左往右读和从右往左读都是一样的数字,例如数字:9009101

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

解题步骤:

  1. 依次枚举所有的三位数
  2. 计算它们的乘积
  3. 筛选所有乘积中是回文数的数字:回文乘积
  4. 找到所有回文乘积中的最大值,即所求

代码实现

/*
 * @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



相关文章
|
Python
【欧拉计划第 8 题】序列中最大的乘积 Largest product in a series
【欧拉计划第 8 题】序列中最大的乘积 Largest product in a series
124 0
【欧拉计划第 8 题】序列中最大的乘积 Largest product in a series
|
人工智能
【待补】UPC No Need(二分+bitset || 背包dp)
【待补】UPC No Need(二分+bitset || 背包dp)
58 0
HDU-1016,Prime Ring Problem(DFS+素数)
HDU-1016,Prime Ring Problem(DFS+素数)
LeetCode之Palindrome Number(回文数)
LeetCode之Palindrome Number(回文数)
71 0