euler-4: 回文数判断

求最大的由两个3位数相乘构成的回文数。

我一开始的想法是用两个循环i, j。i从999减到100, j从i减到100,然后逐个看i*j是不是回文数,这样第一个遇到的回文数就是答案。

但是这个想法不对,因为照该算法,结果会返回995*583=580085。
但实际上的正确答案是993*913=906609。因为上面的解法基于贪婪法,不能求得正确解。

正确解法就是全部遍历。代码如下:
 

/*************************************************************************
	> File Name: euler-4-2.cpp
	> Author: 
	> Mail: 
	> Created Time: Thu 05 Nov 2020 01:05:00 AM CST
 ************************************************************************/

#include <iostream>
using namespace std;

int func(int x) {
    int t = 0, raw = x;
    while (x) {
        t = t * 10 + x % 10;
        x /= 10;
    }
    return t == raw;
}

int main() {
    int ans = 0;
    for (int i = 100; i < 1000; i++) {
        for (int j = i; j < 1000; j++) {
            int t = i * j;
            if (func(t)) {
                ans = max(ans, t);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

 

    原文作者:纸上得来终觉浅 绝知此事要躬行
    原文地址: https://blog.csdn.net/roufoo/article/details/109502428
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞