Является ли какое-либо решение правильным решением?
Я всегда думаю про себя после решения задачи программирования, с которой я был связан в течение некоторого времени: "Это работает, это достаточно хорошо".
Я не думаю, что это действительно правильный образ мыслей, на мой взгляд, и я думаю, что я всегда должен пытаться кодировать с максимальной производительностью.
Во всяком случае, с этим сказал, я только что попробовал вопрос 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;
?>
Обратите внимание, это не домашняя работа. Я бросил школу сотни лет назад. Мне просто скучно и я прохожу вопросы по проекту Эйлера
8 ответов
Я всегда думаю про себя после решения задачи программирования, с которой я был связан в течение некоторого времени: "Это работает, это достаточно хорошо".
Я не думаю, что это действительно правильный образ мыслей, на мой взгляд, и я думаю, что я всегда должен пытаться кодировать с максимальной производительностью.
Одна из классических вещей, представленных в Code Complete, заключается в том, что программисты, имея заданную цель, могут создать "оптимальную" компьютерную программу, используя одну из многих метрик, но невозможно оптимизировать все параметры одновременно. Параметры, такие как
- Код Readabilty
- Понятность вывода кода
- Длина кода (строки)
- Скорость выполнения кода (производительность)
- Скорость написания кода
Не стесняйтесь оптимизировать для любого из этих параметров, но имейте в виду, что оптимизация для всех их одновременно может быть упражнением для разочарования или привести к чрезмерной системе.
Вы должны спросить себя: каковы ваши цели? Что "достаточно хорошо" в этой ситуации? Если вы просто учитесь и хотите сделать вещи более оптимизированными, во что бы то ни стало, просто знайте, что для создания идеальной программы требуется бесконечное время, а время само по себе ценно.
Вы можете избежать раздела 2 мода, выполнив операцию три раза (каждый третий элемент является четным), так что он читает: $fibonacci = 3*$number + 2*$previous; и новый вход для Фибоначчи ($fibonnacci,2*$number+$previous) Я не знаком с php, так что это всего лишь общий совет алгоритма, я не знаю, правильный ли это синтаксис. Это практически та же операция, она просто заменяет несколько умножений на модули и дополнения.
Также убедитесь, что вы начинаете с $ number как четного, а $ previous как нечетного, предшествующего ему в последовательности (вы можете начать с $ number как 2, $previous как 1, а сумма также должна начинаться с 2),
Забудьте о Фибоначчи (проблема 2), я говорю, просто продвиньтесь в Эйлере. Не тратьте время на поиск оптимального кода для каждого вопроса.
Если ваш ответ достигает правила одной минуты, тогда вы можете попробовать следующий. После нескольких проблем все станет сложнее, и вы будете оптимизировать код, пока будете писать для достижения этой цели.
Это полностью ваш выбор, довольны ли вы решением или хотите улучшить его дальше. Существует много проблем проекта Эйлера, в которых решение грубой силы займет слишком много времени, и вам придется искать хитрый алгоритм.
Задача 2 не требует какой-либо оптимизации. Ваше решение уже более чем достаточно быстро. Еще позвольте мне объяснить, какая оптимизация возможна. Часто это помогает сделать некоторые исследования по этому вопросу. Например, вики-страница о числах Фибоначчи содержит эту формулу
fib(n) = (phi^n - (1-phi)^n)/sqrt(5)
где фи - золотое сечение. Т.е.
фи = (sqrt(5)+1)/2.
Если вы используете, что fib (n) приблизительно равно phi^n/sqrt(5), то вы можете найти индекс наибольшего числа Фибоначчи, меньшего, чем M, на
n = этаж (log(M * sqrt(5)) / log(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+ эпсилон)). Для небольших чисел любое решение, конечно, хорошо.
Я на самом деле не проверял это... но было кое-что, что я лично попытался бы решить в этом решении, прежде чем называть его "выполненным".
Как можно больше избегать глобальных переменных, используя рекурсию с аргументом суммы
РЕДАКТИРОВАТЬ: Обновление в соответствии с рекомендациями алгоритма 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);
[Развести руками]
Решение должно быть оценено по требованиям. Если все требования соблюдены, то все остальное - мексиканское. Если все требования соблюдены, и вы лично не удовлетворены решением, то, возможно, требования требуют переоценки. Это примерно настолько, насколько вы можете ответить на этот метафизический вопрос, потому что мы начинаем углубляться в такие вещи, как управление проектами и бизнес:S
Гм, в отношении вашего вопроса об Эйлер-Проекте, просто мои две пенсы:
- Рассмотрим рефакторинг на итеративный, а не рекурсивный
- Обратите внимание, что каждый третий член в серии является четным? Нет необходимости по модулю, как только вы получите свой начальный срок
Например
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, но я уверен, что вы могли бы перевести его довольно хорошо.
Надеюсь это поможет,:)
ура
Другие здесь также сказали это: "Это часть проблемы с примерами вопросов против реальных проблем бизнеса "
На этот вопрос очень сложно ответить по ряду причин:
- Язык играет огромную роль. Некоторые языки больше подходят для некоторых проблем, поэтому, если вы столкнулись с несоответствием, вы найдете решение "менее красноречивым"
- Это зависит от того, сколько времени у вас есть на решение проблемы, чем больше времени для ее решения, тем больше вероятность того, что вы придете к решению, которое вам нравится (хотя иногда и верно обратное, так как слишком много времени заставляет задуматься)
- Это зависит от вашего уровня удовлетворенности в целом. Я работал над несколькими проектами, в которых я думал, что части, которые великолепно написаны и красиво написаны, и другие части, где полный мусор, но они были за пределами того, что я успел решить.
Я думаю, суть в том, что если вы думаете, что это хорошее решение, а ваш клиент / покупатель / команда / и т. Д. Согласны, то это хорошее решение на данный момент. Вы можете изменить свое решение в будущем, но сейчас это хорошее решение.
Используйте указание, что код для решения проблемы не должен занимать больше минуты. Это самое важное для проблем Эйлера, ИМО.
Кроме того, просто убедитесь, что он читабелен - убедитесь, что вы можете легко увидеть, как работает код. Таким образом, вы сможете легче увидеть, как все работает, если у вас возникнет такая проблема, как одна из проблем Эйлера, которую вы решили, что, в свою очередь, позволит вам решить эту проблему быстрее, потому что вы уже знаете, как ее решить.
Вы можете установить другие критерии для себя, но я думаю, что это выходит за рамки намерений проблем Эйлера - мне кажется, что контекст проблем кажется гораздо более подходящим для сосредоточения внимания на эффективности и удобочитаемости, чем что-либо еще.