Нахождение палиндромов по произведению двух чисел с N цифрами

Question

Мой код компилируется, но кажется, что он никогда не найдет ответ.Это странно, так как я посмотрел на почти идентичный код, который заканчивается за секунды.

Вот мой код:

#include <iostream>

#include <sstream>

int main()
{
       for(int i = 999; i >=100; i--)
       {
              for(int j=999; j>=100;j--)
              {
                     int num = (i*j);
                     std::string number;
                     std::string temp;
                     std::string reversed;
                     std::stringstream out;
                     out << num;
                     number = out.str();
                     temp = number;
                     std::reverse(temp.begin(),temp.end());
                     if( temp == number)
                     {
                           std::cout << number << std::endl;
                     }

              }
       }



       std::cin.get();
       return 0;
}

Теперь вот код, который я знаю, работает и работает невероятно быстро,Я не вижу, что мы делаем по-другому.

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    // Count down from largest to smallest, so first palindrome found is the largest

    unsigned biggestProduct = 0;

    for(unsigned n1=999; n1>=100; --n1) {
        for(unsigned n2=999; n2>=100; --n2) {
            unsigned thisProduct = n1 * n2;

            if(thisProduct > biggestProduct) {
                stringstream strmProduct;
                string strProductReverse;

                strmProduct << n1 * n2;

                strProductReverse = strmProduct.str();
                reverse(strProductReverse.begin(), strProductReverse.end());

                if(strmProduct.str() == strProductReverse)
                    biggestProduct = thisProduct;
            }
        }
    }

    cout << biggestProduct << endl;
    cin.get();

    return 0;

}

Answer 1

for(int i = 999; i <=100; i--)

Будет ли это когда-либо работать (то же самое для j)?:)

for(int i = 999; i >=100; i--)

Answer 2

Самая большая разница в этой строке if(thisProduct > biggestProduct).Если продукт меньше, чем текущий самый большой, вам не нужно проверять, является ли палиндром.

Answer 3

Разница между ними состоит в том, что первые тесты на палиндроменозу для каждого i*j, в то время как другие тесты только на i*j больше, чем самый большой палиндром, который он уже нашел.

Это можно сделать немного быстреепереходя от j= i к j>=100 и заканчивая, когда i*j<= biggestProduct или i*i<= biggestProduct.

Answer 4

ОК, при условии исправления для циклов for, есть важное различие в двух частях кода.Второй более быстрый фрагмент кода только пытается найти самый большой палиндром, поэтому он избегает большой работы.Ваш код пытается найти все палиндромы, что, очевидно, является более сложной проблемой и займет больше времени.

Answer 5

Вот несколько проблем, на которые я могу указать:

• Эта строка кода: for(int j=999; j>=100;j--) может быть уменьшена до for(int j=999; j>=i-1;j--). Это нужно для того, чтобы не пропустить число дважды.пример: для i=999 вы пройдете счетчик j, начиная с 999, затем 998, 997 и т. д. Это сэкономит время, если вы пропустите все ниже или равным 998, поскольку i=<998 и j=999 сделаютэти комбинации
• Второй намек на вопрос: вы ищете наибольшее, то есть первый палиндром самый большой.Поэтому вам нужно отфильтровать любую комбинацию, которая у вас есть, кроме этого.У вас есть это во втором коде, добавив if(thisProduct > biggestProduct).

• Также шаги для счетчика могут быть решающими.Из этого обсуждения я обнаружил, что изменение размера шага на 2 может быть полезным.

• Последнее, но не менее важное - это строки. здесь я также узнал, что создание строк может быть вычислительно дорогим.Редактирование блока с помощью std::string может быть другим вариантом.