Проблема Эйлера номер 4

Некоторые проблемы с эффективностью:

1. начать сверху (так как мы можем использовать это, пропуская много вычислений)
2. не рассчитывай дважды

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

def biggest():
    big_x, big_y, max_seen = 0,0, 0
    for x in xrange(999,99,-1):
        for y in xrange(x, 99,-1):  # so we don't double count   
            if x*y < max_seen: continue  # since we're decreasing, 
                                # nothing else in the row can be bigger
            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y

    return big_x,big_y,max_seen

biggest()
# (993, 913, 906609)

Попробуйте вычислить x из произведения z и y, а не проверять каждое число от 1 до миллиона. Подумайте об этом: если бы вас попросили вычислить 500 * 240, что более эффективно - умножить их или считать от 1, пока вы не найдете правильный ответ?

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

1) если вы уже проверили z = 995, y = 990, вам не нужно проверять z = 990, y = 995. Грег Линд правильно с этим справляется.

2) Вы вычисляете произведение z * y, а затем запускаете x в огромном диапазоне и сравниваете это значение с y * z. Например, вы только что вычислили 900 * 950, а затем вы запускаете x от 1000 до 1M и смотрите, если x = 900 * 950. Вы видите в этом проблему?

3) Что происходит со следующим кодом? (вот почему ваш код ничего не возвращает, но вы все равно не должны этого делать)

x = str(100)
y = 100
print x == y

4) Если вы выясните (3), вы будете печатать там много информации. Вам нужно найти способ сохранить максимальное значение и вернуть это значение только в конце.

5) Вот хороший способ рассчитать время для ваших задач Эйлера:

if __name__ == "__main__":
    import time
    tStart = time.time()
    print "Answer = " + main()
    print "Run time = " + str(time.time() - tStart)

вместо того, чтобы перечислять все произведения трехзначных чисел (~ 900 ^ 2 итераций), перечислить все 6- и 5-значные палиндромы (это занимает ~ 1000 итераций); затем для каждого палиндрома решите, может ли он быть представлен произведением двух трехзначных чисел (если нет, он должен иметь четырехзначный простой множитель, так что это отчасти легко проверить).

Кроме того, вы спрашиваете о проблеме №4, а не о проблеме №3.

сравнение строки с целым числом в

x == z*y

есть также логические ошибки

начать в обратном порядке range(999, 99, -1). так будет эффективнее. полностью удалите третий цикл и второе сравнение.

Вау, этот подход немного лучше других реализаций на этой странице, включая мою.

Вместо того

• проходя по трехзначным множителям строка за строкой (сначала выполните все y для x = 999, затем все y для x = 998 и т. д.),

we

• пройдите по диагоналям: сначала сделайте все x, y так, чтобы x + y = 999 + 999; затем сделайте все x, y так, чтобы x + y = 999 + 998; и т.п.

Нетрудно доказать, что на каждой диагонали чем ближе x и y друг к другу, тем выше произведение. Таким образом, мы можем начать с середины, x = y (или x = y + 1 для нечетных диагоналей) и по-прежнему проводить те же оптимизации с коротким замыканием, что и раньше. И поскольку мы можем начать с самых высоких диагоналей, которые являются самыми короткими, мы, скорее всего, найдем палиндром с наивысшей квалификацией гораздо раньше.

maxFactor = 999
minFactor = 100

def biggest():
    big_x, big_y, max_seen, prod = 0, 0, 0, 0

    for r in xrange(maxFactor, minFactor-1, -1):
        if r * r < max_seen: break

        # Iterate along diagonals ("ribs"):

        # Do rib x + y = r + r
        for i in xrange(0, maxFactor - r + 1):
            prod = (r + i) * (r - i)

            if prod < max_seen: break

            if is_palindrome(prod):
                big_x, big_y, max_seen = r+i, r-i, prod

        # Do rib x + y = r + r - 1
        for i in xrange(0, maxFactor - r + 1):
            prod = (r + i) * (r - i - 1)

            if prod < max_seen: break

            if is_palindrome(prod):
                big_x, big_y, max_seen = r+i,r-i-1, prod

    return big_x, big_y, max_seen

# biggest()
# (993, 913, 906609)

Улучшение почти в 3 раза

Вместо вызова is_palindrome () 6124 раза, теперь мы вызываем его только 2228 раз. И общее накопленное время уменьшилось с 23 мс до 9!

Мне все еще интересно, существует ли идеально линейный (O (n)) способ создания списка продуктов из двух наборов чисел в порядке убывания. Но я очень доволен приведенным выше алгоритмом.

В вопросе говорится:

What is the largest prime factor of the number 600851475143?

Я решил это с помощью C #, но сам алгоритм не зависит от языка.

1. Создайте метод определения того, является ли число простым или нет. Это может быть грубая сила (вместо использования гораздо более эффективного алгоритма просеивания) и выглядит так:

private static long IsPrime(long input)
        {
            if ((input % 2) == 0)
            {
                return 2;
            }
            else if ((input == 1))
            {
                return 1;
            }
            else
            {
                long threshold = (Convert.ToInt64(Math.Sqrt(input)));
                long tryDivide = 3;
                while (tryDivide < threshold)
                {
                    if ((input % tryDivide) == 0)
                    {
                        Console.WriteLine("Found a factor: " + tryDivide);
                        return tryDivide;
                    }
                    tryDivide += 2;
                }
                Console.WriteLine("Found a factor: " + input);
                return -1;
            }
        }

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

private static long HighestPrimeFactor(long input)
{
    bool searching = true;
    long highestFactor = 0;
    while (searching)
    {
        long factor = IsPrime(input);
        if (factor != -1)
        {
            theFactors.Add(factor);
            input = input / factor; 
        }
        if (factor == -1)
        {
            theFactors.Add(input);
            highestFactor = theFactors.Max();
            searching = false;
        }
    }
    return highestFactor;
}

Я надеюсь, что это поможет, не выдавая слишком много.

Другой совет здесь отличный. Этот код тоже работает. Я начинаю с 999, потому что мы знаем, что наибольшая возможная комбинация - 999 * 999. Не на питоне, а на каком-то быстро написанном псевдокоде.

public static int problem4()
    {       
    int biggestSoFar=0;
        for(int i = 999; i>99;i--){
            for(int j=999; j>99;j--){
                if(isPaladrome(i*j))
                   if(i*j>biggestSoFar)
                        biggestSoFar=i*j;
            }
        }
        return biggestSoFar;    
    }

Это добавляет пару оптимизаций к хорошему решению @ GreggLind, сокращая время выполнения вдвое:

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

def biggest():
    big_x, big_y, max_seen = 0,0, 0
    for x in xrange(999,99,-1):
        # Optim. 1: Nothing in any row from here on can be bigger.
        if x*x < max_seen: break  

        for y in xrange(x, 99,-1):  # so we don't double count   
            # Optim. 2: break, not continue
            if x*y < max_seen: break  # since we're decreasing, 
                                # nothing else in the row can be bigger

            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y

    return big_x,big_y,max_seen

biggest()
# (993, 913, 906609)

Линия

if x*x < max_seen: break

означает, что как только мы дойдем до точки, где x меньше, чем sqrt самого большого палиндрома, который мы видели, нам не только не нужно больше исследовать какие-либо факторы в этой строке; нам даже не нужно вообще исследовать какие-либо строки, поскольку все оставшиеся строки будут начинаться с числа, меньшего, чем текущее значение x.

Это не уменьшает количество вызовов is_palindrome(), но означает намного меньше итераций внешнего цикла. Значение x, на которое он разбивается, составляет 952, поэтому мы исключили проверку 853 строк (хотя и «меньших», благодаря другим break).

Я также заметил, что

if x*y < max_seen: continue

должно быть

if x*y < max_seen: break

Мы пытаемся замкнуть всю строку, а не только текущую итерацию внутреннего цикла.

Когда я запускал этот скрипт с помощью cProfile, совокупное время для biggest() до оптимизации составляло в среднем около 56 мсек. Оптимизация сократила его примерно до 23 мсек. Любая оптимизация сама по себе принесет большую часть этого улучшения, но первая из них немного более полезна, чем вторая.

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

largest = 0
for a in range(100, 1000):
    for b in range(100, 1000):
        c = a * b
        if str(c) == ''.join(reversed(str(c))):
            largest = max(largest, c)
print(largest)

Вот эффективное общее решение (примерно в 5 раз быстрее, чем другие, которые я видел):

def pgen(factor):
    ''' Generates stream of palindromes smaller than factor**2 
        starting with largest possible palindrome '''
    pmax = str(factor**2)
    half_palindrome = int(pmax[0:len(pmax)/2]) - 1
    for x in xrange(half_palindrome, 0, -1):
        yield int(str(x) + str(x)[::-1])

def biggest(factor):
    ''' Returns largest palindrome and factors '''
    for palindrome in pgen(factor):
        for f1 in xrange(factor/11*11, factor/10, -11):
            f2 = palindrome/f1
            if f2 > factor:
                break
            if f2*f1 == palindrome:
                return palindrome, f1, f2

>>> biggest(99)
(9009, 99, 91)
>>> biggest(999)
(906609, 993, 913)
>>> biggest(9999)
(99000099, 9999, 9901)
>>> biggest(99999)
(9966006699L, 99979, 99681L)
>>> biggest(9999999)
(99956644665999L, 9998017, 9997647L)
>>> biggest(99999999)
(9999000000009999L, 99999999, 99990001L)
>>> biggest(999999999)
(999900665566009999L, 999920317, 999980347L)

Если ваша программа работает медленно и у вас есть такие вложенные циклы:

for z in range(100, 1000):
    for y in range(100, 1000):
        for x in range(1, 1000000):

Тогда вы должны задать себе вопрос: «Сколько раз будет выполняться тело самого внутреннего цикла?» (тело вашего внутреннего цикла - это код, который начинается с: x = str(x))

В этом случае разобраться несложно. Внешний цикл будет выполнен 900 раз. Для каждой итерации средний цикл также будет выполняться 900 раз, что составляет 900 × 900, или 810 000 раз. Затем для каждой из этих 810 000 итераций внутренний цикл будет выполняться 999 999 раз. Думаю, мне нужно долго рассчитывать это:

>>> 900*900*999999
809999190000L

Другими словами, вы делаете свою палиндромную проверку почти 810 миллиардов раз. Если вы хотите сделать это в рекомендованном Project Euler ограничении в 1 минуту на задачу, вы можете немного оптимизировать :-) (см. Комментарий Дэвида)

Вот что я сделал на Java:

public class Euler0004
{
    //assumes positive int
    static boolean palindrome(int p)
    {
        //if there's only one char, then it's
        //  automagically a palindrome
        if(p < 10)
            return true;

        char[] c = String.valueOf(p).toCharArray();

        //loop over the char array to check that
        //  the chars are an in a palindromic manner
        for(int i = 0; i < c.length / 2; i++)
            if(c[i] != c[c.length-1 - i])
                return false;

        return true;
    }


    public static void main(String args[]) throws Exception
    {
        int num;
        int max = 0;

        //testing all multiples of two 3 digit numbers.
        // we want the biggest palindrome, so we
        // iterate backwards
        for(int i = 999; i > 99; i--)
        {
            // start at j == i, so that we
            //  don't calc 999 * 998 as well as
            //  998 * 999...
            for(int j = i; j > 99; j--)
            {
                num = i*j;

                //if the number we calculate is smaller
                //  than the current max, then it can't
                //  be a solution, so we start again
                if(num < max)
                    break;

                //if the number is a palindrome, and it's
                //  bigger than our previous max, it
                //  could be the answer
                if(palindrome(num) && num > max)
                    max = num;
            }
        }

        //once we've gone over all of the numbers
        //  the number remaining is our answer
        System.out.println(max);

    }
}

Вот мое решение:

polindroms = [(x, y, x * y) for x in range(100, 999) for y in range(100, 999) if str(x * y) == str(x * y)[::-1]]
print max(polindroms, key = lambda item : item[2])