项目Euler #4:查找最大的回文，它是两个3位数字更新的乘积。

Question

更新！我得到了很多关于提高程序昨天的可读性、结构和效率的提示、建议和技巧，所以我对程序进行了建议的改进，并很高兴地宣布，我成功地将程序的执行时间缩短到了将近1/25！尽管如此，我还是希望对我的程序的改进状态进行反馈。感谢所有对我上一篇文章发表评论的人！

// Largest palindrome product (4)
#include <iostream>
#include <chrono>

bool is_palindrome(int num);
void compute_palindromes(void);
void save_palindrome(int i, int j, int val);
void log_palindrome(void);
void time_function(void (*func)(void), const char *desc);
void version_one(void);
void version_two(void);

struct Palindrome_storage {
    static int primary;
    static int secondary;
    static int palindrome;
};
int Palindrome_storage::primary = 0;
int Palindrome_storage::secondary = 0;
int Palindrome_storage::palindrome = 0;

int main(void) {
    time_function(version_one, "Program -- Version 1.0");
    time_function(version_two, "Program -- Version 1.1 (yesterday's code)");
    time_function(compute_palindromes, "Program -- All optimizations");
    log_palindrome();
    return 0;
}

bool is_palindrome(int num) { // Determine if a given number is a palindrome or not
    int original = num;
    int reversed = 0;
    while (num > 0) {
        reversed *= 10;
        reversed += num % 10;
        num /= 10;
    }
    return reversed == original;
}
void compute_palindromes(void) {
    int max_palindrome = 0;
    for (int i=999; i>99; --i) {
        if (i < max_palindrome/1000) break; // Optimalization
        for (int j=999; j>=i; --j) {
            int product = i*j;
            if ((product > max_palindrome) && is_palindrome(product)) {
                max_palindrome = product;
                save_palindrome(i, j, product);
                break;
            }
        }
    }
}
void save_palindrome(int i, int j, int val) { // Stores the largest palindrome found in a struct with static variables
    Palindrome_storage::primary = i;
    Palindrome_storage::secondary = j;
    Palindrome_storage::palindrome = val;
}
void log_palindrome(void) { // Outputs the largest palindrome found
    std::cout << "Largest palindrome: " << Palindrome_storage::primary << " * " << Palindrome_storage::secondary << " == " << Palindrome_storage::palindrome << std::endl;
}
void time_function(void (*func)(void), const char *desc) { // Time how long a function takes to execute
    double best_time;

    for (int i=0; i<100; i++) { // Multiple checks to find the lowest (should maybe be average) computing time
        auto begin_time = std::chrono::high_resolution_clock::now();
        func();
        auto end_time = std::chrono::high_resolution_clock::now();
        double elapsed_time = std::chrono::duration_cast<std::chrono::microseconds>(end_time - begin_time).count();
        if (i == 0) best_time = elapsed_time;
        else if (elapsed_time < best_time) best_time = elapsed_time;
    }

    std::cout << desc << ":\n";
    std::cout << "Elapsed time is " << best_time/1000000.0 << " seconds." << '\n' << std::endl;
}

// Previous versions
void version_one(void) {
    int largest_palindrome = 0;
    for (int i=999; i>99; i--) {
        for (int j=999; j>99; j--) {
            int product = i*j;
            if (is_palindrome(product) && product>largest_palindrome) {
                largest_palindrome = product;
            }
        }
    }
}
void version_two(void) {
    int largest_palindrome = 0;
    for (int i=999; i>99; i--) {
        for (int j=999; j>99; j--) {
            if (i < largest_palindrome/1000) { // Optimalization
                i = 0;
                j = 0;
            } else {
                int product = i*j;
                if (is_palindrome(product) && product>largest_palindrome) {
                    largest_palindrome = product;
                    j = 0;
                }
            }
        }
    }
}

输出：

Program -- Version 1.0:
Elapsed time is 0.037895 seconds.

Program -- Version 1.1 (yesterday's code):
Elapsed time is 0.003956 seconds.

Program -- All optimizations:
Elapsed time is 0.000153 seconds.

Largest palindrome: 913 * 993 == 906609

Answer 1

你需要做的是，实际上，向相反的方向走，对于每个回文数，验证它是否有所需的两个3位数除数。以下是我要做的：

int rev_search()
{
  for (int i = 999; i >= 100; i--)
  {
    int palnum = i;
    for (int x = i; x > 0; x /= 10)
    {
      palnum *= 10;
      palnum += x % 10;
    }
    int start = 990;
    int step = 11;

    for (int j = start; j >= 100; j -= step)
    {
      int k = palnum / j;
      if (k >= 1000)
        break;
      if (k < 100)
        continue;       
      if ((k * j) == palnum)
      {
        return palnum;
      } 
    }
  }
  return -1;
}