Озадаченный проблемой палиндромного продукта

Question

Я изучал Ruby, поэтому я решил попробовать свои силы в некоторых головоломках проекта Эйлера.Смущающе, я только добрался до задачи 4 ...

Задача 4 выглядит следующим образом:

Палиндромное число читается одинаково в обоих направлениях.Самый большой палиндром, полученный из произведения двух двузначных чисел, равен 9009 = 91 × 99.

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

Таким образом, я решил, что я бы зациклился с 999 до 100 во вложенном цикле for и выполнил тест для палиндрома, а затем вырвался из циклов, когда нашел первый (который должен быть самым большим):

final=nil
range = 100...1000
for a in range.to_a.reverse do
  for b in range.to_a.reverse do
    c=a*b
    final=c if c.to_s == c.to_s.reverse
    break if !final.nil?
  end
  break if !final.nil?
end
puts final

Это выдает палиндром 580085, но, очевидно, это не самое высокое произведение двух трехзначных чисел в пределах диапазона.Как ни странно, тот же код успешно возвращает 9009, как в примере, если я изменю диапазон на 10 ... 100.

• Может кто-нибудь сказать мне, где я иду не так?
• Кроме того, есть ли лучший способ вырваться из внутреннего цикла?

Спасибо

Answer 1

Вы тестируете 999 * (999 ... 100), затем 998 * (999 ... 100)

Следовательно, вы будете тестировать 999 * 500 перед тестированием 997 * 996.

Итак, как вы нашли это правильное число?

Сначала обратите внимание, что умножение является отражающим, a * b == b * a, поэтому b не нужно переходить из 999 ... 0 каждый раз, простоa ... 0.

Когда вы найдете палиндрон, сложите два фактора вместе и сохраните сумму (также сохраните два фактора)

Внутри цикла, если (a + b)всегда меньше сохраненной суммы, откажитесь от внутреннего цикла и перейдите к следующему.Когда опускается ниже суммы / 2, никакая будущая стоимость, которую вы можете найти, не будет выше той, которую вы уже нашли, так что все готово.

Answer 2

Проблема в том, что вы можете найти палиндром для a из 999 и b из 200, но вы сломаетесь слишком рано, поэтому вы никогда не увидите, что есть один для 998 * 997 (только примерные числа) .

Вам нужно либо найти все палиндромы, либо, когда вы найдете первый, установить значение b в качестве минимальной границы и продолжить просмотр цикла a.

Answer 3

Рассмотрим цифры P - пусть они будут x, y и z.Длина P должна быть не менее 6 цифр, поскольку палиндром 111111 = 143 × 777 - произведение двух трехзначных чисел.Так как P палиндромно:

P=100000x + 10000y + 1000z + 100z + 10y + x
P=100001x + 10010y + 1100z
P=11(9091x + 910y + 100z)

Так как 11 простое, по крайней мере одно из целых чисел a или b должно иметь коэффициент 11. Поэтому, если a не делится на 11, мы знаем, что b должно быть.Используя эту информацию, мы можем определить, какие значения b мы проверяем в зависимости от a.

Answer 4

Что касается второго вопроса, мой совет - подходить к проблеме более функционально, чем процедурно.Таким образом, вместо того, чтобы зацикливаться, вы можете попытаться «описать» вашу проблему функционально, и пусть Ruby сделает всю работу:

• Из всех пар 3-значных чисел,
  • select только те, чей продукт является палиндромом,
    • и найдут тот, у которого самый большой продукт

Хотя такой подход может и недать наиболее эффективное решение, оно может научить вас нескольким идиомам Ruby.

Answer 5

C # Реализация:

using System;

namespace HighestPalindrome
{
    class Program
    {
        static void Main(string[] args)
        {
            int i, j;
            int m = 1;
            bool flag = false;

            while (true)
            {
                if (flag) j = m + 1;
                else j = m;

                for (i = m; i > 0; i--)
                {
                    Console.WriteLine("{0} * {1} = {2}", 1000 - i, 1000 - j, (1000 - i) * (1000 - j));
                    j++;

                    //--- Palindrome Check ------------------------------

                    int number, temp, remainder, sum = 0;
                    number = temp = (1000 - i) * (1000 - j);

                    while (number > 0)
                    {
                        remainder = number % 10;
                        number /= 10;
                        sum = sum * 10 + remainder;
                    }

                    if (sum == temp)
                    {
                        Console.WriteLine("Highest Palindrome Number is - {0} * {1} = {2}", 1000 - i, 1000 - j, temp);
                        Console.ReadKey();
                        return;
                    }

                    //---------------------------------------------------
                }

                if (flag)
                    m++;
                flag = !flag;
            }

        }
    }
}

Answer 6

ar=[]
limit = 100..999
for a in limit.to_a.reverse do
  for b in (100..a).to_a.reverse do
    c=a*b
    if c.to_s == c.to_s.reverse
      palndrm=c 
      ar << palndrm
    end  
  end
end
print ar
print"\n"
puts ar.max
puts ar.min 

Answer 7

Ты разбиваешься на первом палиндроме, к которому ты пришел, не обязательно на самом большом.

Скажем, у вас есть A, B, C, D, E. Вы тестируете E * A перед тестированием D * C.

Answer 8

Я могу ответить на ваш первый вопрос: вам нужно найти самый высокий продукт, а не продукт, содержащий самый высокий фактор. Другими словами a * b может быть больше c * d, даже если c > a > b.

Answer 9

Ошибка в том, что вы предполагаете, что если вы найдете палиндром с наибольшим значением a, это даст наибольший продукт, который не соответствует действительности.Решение состоит в том, чтобы сохранить значение max_product и обновить его в соответствии с решением, которое вы найдете.

Answer 10

Для этой проблемы, так как мы ищем самый высокий палиндром, я предположил, что он будет начинаться с 9, таким образом, заканчивая 9 (палиндром).

если вы обратите внимание, чтобы получить число, заканчивающееся на 9, вы можете получить его только с номерами, заканчивающимися на 9 и 1, 3 и 3, 7 и 7.

Тогда бесполезно проверять другие значения (например, 999 * 998, поскольку они не заканчиваются на 9).

Начиная с 999 и 991, вы можете затем вычесть 10 из 991, попробовав 999 и 981 и т. Д. Вы делаете то же самое с 993 и 993 ... 993 * 983 то же самое с 997 * 997, затем 997 * 987 и т. д. Вам не нужно идти дальше, чем 900 или 10 ^ 4 - 10 ^ 3, так как вы можете быть уверены, что самый высокий будет раньше.

int PB4_firstTry(int size)
{
    int nb1 = (int)pow(10.0,size+1.0) - 1, nb2 = (int)pow(10.0,size+1.0) - 1;
    int pal91 = getFirstPalindrome(size,9,1);
    int pal33 = getFirstPalindrome(size,3,3);
    int pal77 = getFirstPalindrome(size,7,7);

    int bigger1 = (pal91 > pal33) ? pal91 : pal33;
    return (bigger1 > pal77) ? bigger1 : pal77;
}

int getFirstPalindrome(int size,int ending1,int ending2)
{
    int st1 =  (int)pow(10.0,size+1.0) - 10 + ending1;
    int comp = st1 - pow(10.0,size);
    int st2 =  (int)pow(10.0,size+1.0) - 10 + ending2;
    int answer = -1;
    while (st1 > comp)
    {
        for (int i = st2; i > comp && st1*i > answer; i-=10)
        {
            if (PB4_isPalindrome(st1*i))
                answer = st1*i;
        }
        st1 -= 10;
    }
    return answer;
}

bool PB4_isPalindrome(int number)
{
    std::string str = intToString(number);
    for (int i = 0; i < (int)(str.length() / 2); i++)
    {
        if (str[i] != str[str.length() - 1 - i])
            return false;
    }
    return true;
}

std::string intToString(int number)
{
    std::ostringstream convert;
    convert << number;
    return convert.str();
}

Конечно, это работает для 4-значных чисел и т. Д.