Блог

Написание программы для решения четвертой задачи project euler: найдите наибольший палиндром, составленный из произведения двух двухзначных чисел. Вот мой reprex:

 #include <iostream>

int reverseNumber(int testNum)
{

    int reversedNum, remainder = 0;
    int temp = testNum;

    while(temp != 0)
    {
        remainder = temp % 10;
        reversedNum = reversedNum * 10   remainder;
        temp /= 10;
    }

    return reversedNum;
}

int main()
{
    const int MIN = 100;
    int numOne = 99;
    int product = 0;

    for(int numTwo = 10; numTwo < 100; numTwo  )
    {
        product = numOne * numTwo;

        if (reverseNumber(product) == product)
        {
            int solution = product;
            std::cout << solution << 'n';
            return 0;
        }        
    }

    return 0;
}
  

Мой основной мыслительный процесс, стоящий за этим, заключается в том, что цикл for будет проходить через каждое число от 10 до 99 и умножать его на 99. Мой предполагаемый результат состоит в том, чтобы он напечатал 9009, который является самым большим палиндромом с 2 множителями по 2 цифры. Итак, я думаю, что здесь должно произойти то, что цикл for будет проходить от 10 до 99, и в каждом цикле он должен проходить через параметры оператора if, который переворачивает число и проверяет, равно ли оно самому себе.
Я убедился, что это не было проблемой компилятора, поскольку это повторяется между разными компиляторами. Функция reverseNumber () возвращает правильное число каждый раз, когда я ее тестировал, так что это не должно быть проблемой, однако эта проблема возникает только тогда, когда функция задействована в логическом сравнении. Под этим я подразумеваю, что если даже я установлю его равным переменной и добавлю переменную в параметры if, проблема все равно возникнет. Я в значительной степени в тупике. Я просто надеюсь, что это не какая-то глупая ошибка, поскольку я занимаюсь этим уже пару дней.

 int reversedNum, remainder = 0;
  

Вы должны знать, что это дает вам (в контексте автоматической переменной) ноль, remainder но произвольное reversedNum значение. На самом деле это одна из причин, по которой в некоторых центрах разработки существует правило «одна переменная на объявление».

Другими словами, вероятно, это должно быть:

 int reversedNum = 0, remainder;
  

или даже:

 int reversedNum = 0;
int remainder;
  

Еще одна вещь, которая часто помогает, — это ограничить область видимости переменной как можно меньшей областью, вызывая их к существованию только при необходимости. Примером этого может быть:

 int reverseNumber(int testNum) {
    int reversedNum = 0;

    while (testNum != 0) {
        int remainder = testNum % 10;
        reversedNum = reversedNum * 10   remainder;
        testNum /= 10;
    }

    return reversedNum;
}
  

На самом деле, я бы, вероятно, пошел дальше и полностью исключил remainder , поскольку вы используете его только один раз:

 reversedNum = reversedNum * 10   testNum % 10;
  

Вы заметите, что я также избавился от temp этого. Ввод testNum во временную переменную мало что даст, поскольку она уже является копией оригинала (поскольку она была передана по значению).

И еще одно замечание, больше связанное с проблемой, а не с кодом. Вы, кажется, предполагаете, что сформирован палиндром, кратный 99 . Это может быть так, но осторожный программист не стал бы полагаться на это — если вам разрешено предполагать подобные вещи, вы могли бы просто заменить всю свою программу на:

 print 9009
  

Следовательно, вам, вероятно, следует проверить все возможности.

Вы также получаете первый найденный оператор, который не обязательно является самым высоким (например, давайте предположим, что 99 * 17 и 99 * 29 оба являются палиндромными — вам не нужен первый оператор.

И, поскольку вы проверяете все возможности, вы, вероятно, не захотите останавливаться на первой, даже если вложенные циклы уменьшаются вместо увеличения. Это потому, что if 99 * 3 и 97 * 97 оба являются палиндромными, вам нужен самый высокий, а не первый.

Таким образом, лучшим подходом может быть запуск high и выполнение исчерпывающего поиска, при этом также гарантируя, что вы игнорируете проверку палиндрома кандидатов, которые меньше вашего текущего максимума, что-то вроде (псевдокод)

 # Current highest palindrome.

high = -1

# Check in reverse order, to quickly get a relatively high one.

for num1 in 99 .. 0 inclusive:
    # Only need to check num2 values <= num1: if there was a
    # better palindrome at (num2 * num1), we would have
    # already found in with (num1 * num2).

    for num2 in num1 .. 0 inclusive:
        mult = num1 * num2

        # Don't waste time doing palindrome check if it's
        # not greater than current maximum - we can't use
        # it then anyway. Also, if we find one, it's the
        # highest possible for THIS num1 value (since num2
        # is decreasing), so we can exit the num2 loop
        # right away.

        if mult > high:
            if mult == reversed(mult):
                high = mult
                break

if high >= 0:
    print "Solution is ", high
else:
    print "No solution"
  

В дополнение к правильной инициализации ваших переменных, если вам нужен самый большой палиндром, вам следует переключить направление вашего цикла for — например:

 for(int numTwo = 100; numTwo > 10; numTwo--) { 
    ...
}
  

или же вы просто печатаете первый палиндром в пределах указанного вами диапазона