Является ли какое-либо решение правильным решением?

Question

Я всегда думаю про себя после решения задачи программирования, с которой я был связан в течение некоторого времени: «Это работает, это достаточно хорошо».

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

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

<?php
  /* Each new term in the Fibonacci sequence is generated by adding the previous two
     terms. By starting with 1 and 2, the first 10 terms will be:

     1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

     Find the sum of all the even-valued terms in the sequence which do not exceed
     four million.
   */
   function fibonacci ( $number, $previous = 1 ) {
     global $answer;
     $fibonacci = $number + $previous;
     if($fibonacci > 4000000) return;
     if($fibonacci % 2 == 0) {
       $answer = is_numeric($answer) ? $answer + $fibonacci : $fibonacci;
     }
     return fibonacci($fibonacci, $number);
   }
   fibonacci(1);
   echo $answer;
?>

Обратите внимание, что это не домашняя работа.Я бросил школу сотни лет назад.Мне просто скучно, и я прохожу вопросы по проекту Эйлера

Answer 1

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

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

Одна из классических вещей, представленных в Code Complete , заключается в том, что программисты, получив цель, могут создать «оптимальную» компьютерную программу, используя один из многих показателей, но невозможно оптимизировать для все параметров сразу. Параметры, такие как

• Код Readabilty
• Понятность вывода кода
• длина кода (строки)
• Скорость выполнения кода (производительность)
• Скорость написания кода

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

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

Answer 2

Вы можете избежать раздела 2 мода, выполнив операцию три раза (каждый третий элемент четный), так что она гласит: $ fibonacci = 3 * $ number + 2 * $ previous; и новый вход для Фибоначчи ($ fibonnacci, 2 * $ число + $ предыдущий) Я не знаком с php, так что это всего лишь общий совет алгоритма, я не знаю, правильный ли это синтаксис. Это практически та же операция, она просто заменяет несколько умножений на модули и дополнения.

Кроме того, убедитесь, что вы начинаете с четного числа $ и $ предыдущего как нечетного, который предшествует ему в последовательности (вы можете начать с $ number как 2, $ previous как 1, и сумма также начинается на 2).

Answer 3

Забудьте о Фибоначчи (проблема 2), я говорю, просто продвиньтесь в Эйлере. Не тратьте время на поиск оптимального кода для каждого вопроса.

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

Answer 4

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

Задача 2 не требует какой-либо оптимизации. Ваше решение уже более чем достаточно быстро. Еще позвольте мне объяснить, какая оптимизация возможна. Часто это помогает сделать некоторые исследования по этому вопросу. Например. страница вики на числа Фибоначчи содержит эту формулу

fib (n) = (phi ^ n - (1-phi) ^ n) / sqrt (5)

где фи - золотое сечение. * 1011 Т.е. *

phi = (sqrt (5) +1) /2.

Если вы используете, что fib (n) приблизительно равно phi ^ n / sqrt (5), то вы можете найти индекс наибольшего числа Фибоначчи, меньшего, чем M, на

n = этаж (журнал (M * sqrt (5)) / журнал (phi)).

например. для M = 4000000 мы получаем n = 33, следовательно, fib (33) наибольшее число Фибоначчи меньше 4000000. Можно наблюдать, что fib (n) четное, если n кратно 3. Следовательно, сумма четного числа Фибоначчи цифры

fib (0) + fib (3) + fib (6) + ... + fib (3k)

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

fib (0) + fib (3) + fib (6) + ... + fib (3k) = (fib (3k + 2) - 1) / 2.

Поскольку fib (n) имеет размер O (n), прямое решение имеет сложность O (n ^ 2). Используя приведенную выше закрытую формулу вместе с быстрым методом для вычисления чисел Фибоначчи имеет сложность O (n log (n) ^ (1 + эпсилон)). Для небольших чисел любое решение, конечно, хорошо.

Answer 5

[пожать плечами]

Решение должно оцениваться по требованиям. Если все требования удовлетворены, то все остальное - мокс. Если все требования соблюдены, и вы лично не удовлетворены решением, то, возможно, требования требуют переоценки. Это примерно настолько, насколько вы можете ответить на этот метафизический вопрос, потому что мы начинаем заниматься такими вещами, как управление проектами и бизнес: S

Гм, в связи с вашим вопросом о проекте Эйлера, просто мои две пенсы:

1. Рассмотрим рефакторинг на итеративный, а не рекурсивный
2. Обратите внимание, что каждый третий член в серии является четным? Нет необходимости по модулю, как только вы получите свой начальный срок

Например

public const ulong TermLimit = 4000000;

public static ulong CalculateSumOfEvenTermsTo (ulong termLimit)
{
    // sum!
    ulong sum = 0;

    // initial conditions
    ulong prevTerm = 1;
    ulong currTerm = 1;
    ulong swapTerm = 0;

    // unroll first even term, [odd + odd = even]
    swapTerm = currTerm + prevTerm;
    prevTerm = currTerm;
    currTerm = swapTerm;

    // begin iterative sum,
    for (; currTerm < termLimit;)
    {
        // we have ensured currTerm is even,
        // and loop condition ensures it is 
        // less than limit
        sum += currTerm;

        // next odd term, [odd + even = odd]
        swapTerm = currTerm + prevTerm;
        prevTerm = currTerm;
        currTerm = swapTerm;

        // next odd term, [even + odd = odd]
        swapTerm = currTerm + prevTerm;
        prevTerm = currTerm;
        currTerm = swapTerm;

        // next even term, [odd + odd = even]
        swapTerm = currTerm + prevTerm;
        prevTerm = currTerm;
        currTerm = swapTerm;
    }
    return sum;
}

Итак, возможно, больше строк кода, но [практически] гарантированно будет быстрее. Итеративный подход не такой «элегантный», но экономит рекурсивные вызовы методов и экономит место в стеке. Во-вторых, генерация развертываемых терминов [то есть явное расширение цикла] уменьшает количество раз, которое вам пришлось бы выполнять операцию модуля, и проверка "четного" условия. Расширение также уменьшает количество раз, когда ваш конечный условный [если текущий срок меньше, чем предел] оценивается.

Это "лучше", нет, это просто "другое" решение.

Извиняюсь за C #, не знаком с php, но я уверен, что вы могли бы перевести его довольно хорошо.

Надеюсь, это поможет, :)

Приветствия

Answer 6

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

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

Вы можете установить другие критерии для себя, но я думаю, что это выходит за рамки задач Эйлера - мне кажется, что контекст проблем кажется гораздо более подходящим для концентрации на эффективности и читабельности, чем что-либо еще

Answer 7

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

Как можно больше избегать глобальных переменных, используя рекурсию с аргументом суммы

РЕДАКТИРОВАТЬ: Обновление в соответствии с рекомендациями алгоритма nnythm (круто!)

function fibonacci ( $number, $previous, $sum ) {
    if($fibonacci > 4000000) { return $sum; }
    else {
        $fibonacci = 3*$number + 2*$previous;
        return fibonacci($fibonnacci,2*$number+$previous,$sum+$fibonacci); 
    }
}
echo fibonacci(2,1,2);

Answer 8

Другие здесь тоже говорили это: «Это часть проблемы с примерами вопросов против реальных бизнес проблем»

На этот вопрос очень сложно ответить по ряду причин:

• Язык играет огромную роль. Некоторые языки более подходят для некоторых проблем, поэтому, если вы столкнулись с несоответствием, вы найдете решение «менее красноречивым»
• Это зависит от того, сколько времени у вас есть на решение проблемы, чем больше времени для решения проблемы, тем больше вероятность того, что вы придете к решению, которое вам нравится (хотя иногда и верно обратное, слишком много времени заставляет вас над думать)
• Это зависит от вашего общего уровня удовлетворенности. Я работал над несколькими проектами, в которых я думал, что детали были великолепны и красиво написаны, а в других частях - полный мусор, но они были за пределами того, что я успел рассмотреть.

Я думаю, суть в том, что если вы думаете, что это хорошее решение, а ваш клиент / покупатель / команда / и т. Д. Согласны, тогда это хорошее решение на данный момент. Вы можете изменить свое решение в будущем, но сейчас это хорошее решение.