Помню дали задачку, вывести ряд Фибоначи. Нарисовал рекурсию. Не понравилось. Видать не поняли.

[mazzy]

Цитата:

Сообщение от Silence

ЗЫ. Помню дали задачку, вывести ряд Фибоначи. Нарисовал рекурсию. Не понравилось. Видать не поняли.

Рекурсия для Фибоначчи?
Без дополнительного кэширования полученных результатов?
И без дополнительных комментариев почему именно так?

мне бы тоже не понравилось.

[eugene egorov]

Цитата:

Сообщение от mazzy

Рекурсия для Фибоначчи?
Без дополнительного кэширования полученных результатов?
И без дополнительных комментариев почему именно так?

мне бы тоже не понравилось.

А по моему логично....в ТЗ именно так сказано - "каждое последующее число равно сумме двух предыдущих чисел"....и почему не рекурсия А про глубину стека пусть постановщик ТЗ думает.....

[belugin]

Цитата:

Сообщение от eugene egorov

А про глубину стека пусть постановщик ТЗ думает.....

Может быть там была хвостовая рекурсия с tail call optimization

[Silence]

Цитата:

Сообщение от mazzy

Рекурсия для Фибоначчи?
Без дополнительного кэширования полученных результатов?
И без дополнительных комментариев почему именно так?

мне бы тоже не понравилось.

Задача стояла именно вывести ряд. Не до какого-то значения,не какое-то число, а именно ряд без каких либо ограничений. Их не было в условии задачи.

Кеширование конечно хорошо, но бесполезно. Ибо ряд бесконечен и программа все равно упадет из-за переполнения. Или Вы предлагаете после достижения результата в N-1 знаков, где N = кол-во не влезающее в память, разбивать результат на части и обсчитывать их отдельно, после чего выводить потоком на экран? (Точнее на бумажку, так как предлагалось писать код на листе А4) А потом так же поступать и с отдельными частями результата ибо и они переполнятся. А это рекурсия.

Цитата:

Сообщение от eugene egorov

А по моему логично....в ТЗ именно так сказано - "каждое последующее число равно сумме двух предыдущих чисел"....и почему не рекурсия А про глубину стека пусть постановщик ТЗ думает.....

Вот-вот. Дали задачу которая в любом случае приведет к ошибке и удалились.
Единственный логичный выход, по моему, это сделать так же. Удалиться. )

Цитата:

Сообщение от mazzy

И без дополнительных комментариев почему именно так?

Видится мне код из трех строчек включая декларативную часть с тремя десятками комментариев...

[mazzy]

Цитата:

Сообщение от eugene egorov

А про глубину стека пусть постановщик ТЗ думает.....

)))))

Цитата:

Сообщение от Silence

Задача стояла именно вывести ряд. Не до какого-то значения,не какое-то число, а именно ряд без каких либо ограничений. Их не было в условии задачи.

Я отлично прочитал и понял первоначальную формулировку.
Спасибо за разъяснения.

Свое мнение не изменил.

[Silence]

Цитата:

Сообщение от mazzy

Свое мнение не изменил.

Т.е. Вы считаете, что для бесконечного цикла нужно писать нечто вроде:

while (true)

???

Или Вы думаете, нужно было объяснить, что задача поставлена не верно? Сомневаюсь, что ждали именно этого.

ЗЫ. Наверное это не то место для таких дискуссий

[mazzy]

Цитата:

Сообщение от Silence

Т.е. Вы считаете, что для бесконечного цикла нужно писать нечто вроде:

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

Сходу можно привести 4-5 решений. Где-то видал статью с 15 способами. Один из них, где время расчета меньше O(n).

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

while(true)...
му-ха-ха-ха!!!! хороший панк-юмор

Цитата:

Сообщение от Ace of Database

и написал такой джоб

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

момент, который не оговорен - целочисленные значения.
для такого случая было бы хорошо оговорить область применимости )))
в обычных системах, скорее всего, выполнение прервется по переполнению раньше, чем пользователь нажмет CTRL + BREAK/
в аксапте приведенный алгоритм, скорее всего, будет просто выдавать неправильные (отрицательные) значения начиная с некоторого числа, причем достаточно близкого к началу последовательности.

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

с точки зрения аксапты, я бы обратил внимание, что автор использует int2str вместо strfmt. Это была бы тема для дополнительных вопросов.

свое мнение не изменил - мне бы тоже не понравилось.

[macklakov]

Цитата:

Сообщение от Silence

Сомневаюсь, что ждали именно этого.

Сложно сказать чего они ждали. Это могла быть тупая задачка из букваря, а мог быть завуалированный вопрос:"какие ассоциации вызывает у вас слово рекурсия?"

[AlexeyS]

Цитата:

Сообщение от Silence

Задача стояла именно вывести ряд. Не до какого-то значения,не какое-то число, а именно ряд без каких либо ограничений. Их не было в условии задачи.

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

[mazzy]

"Большие числа" - это как раз то, о чем говорил Silence в самом начале

Цитата:

Сообщение от Silence

Кеширование конечно хорошо, но бесполезно. Ибо ряд бесконечен и программа все равно упадет из-за переполнения. Или Вы предлагаете после достижения результата в N-1 знаков, где N = кол-во не влезающее в память, разбивать результат на части и обсчитывать их отдельно, после чего выводить потоком на экран? (Точнее на бумажку, так как предлагалось писать код на листе А4) А потом так же поступать и с отдельными частями результата ибо и они переполнятся. А это рекурсия.

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

Но я бы очень внимательно смотрел на повторные вычисления и на переполнение.

чтобы понять, что кандидат понимает проблему.
"на листочке" вполне хватило бы комментария
// функция применима для 30-60 первых чисел

Наивный рекурсивный код {... result = fib(n-1) + fib(n-2)} делает слишком много повторных вычислений.
для "листочка" хватило бы простого кэширования уже полученных чисел.
или изящного решения, о котором я конечно же забыл, и которое показал Андре в этой ветке - передается больше параметров в стек, но полностью и ультимативно решается вопрос повторных вычислений в рекурсии.

или решения через итерацию и хранение в памяти только двух последних чисел, как показал Ace of Database.

[Ace of Database]

Прочитал, что такое "Фибоначчи" в википедии и написал такой джоб. В аксапте не проверял
Прерывается через CTRL + BREAK/
Без рекурсии.

x = 0;
y = 1;
info(int2str(x));
info(int2str(y));
while (true)
{
    info(int2str(x + y));
    [x, y] = [y, x + y];
}

[dech]

Задача была вывести ряд Фибоначчи. Человек справился. Но я бы тоже на их месте подумал, стоит ли брать к себе человека, решающего задачи путем рекурсии.

"Шурик, вы комсомолец? Это же не наш метод!" ©

[mazzy]

Цитата:

Сообщение от dech

стоит ли брать к себе человека, решающего задачи путем рекурсии.

рекурсия сама по себе не плоха.

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

[AP-1055D]

Замечу, что решение с помощью рекурсии является точной имплементацией определения чисел Фибоначчи.

На одном собеседовании я показывал ещё два способа, с помощью которых можно решить эту задачу, хотя начал с рекурсии.

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

[mazzy]

Цитата:

Сообщение от AP-1055D

Замечу, что решение с помощью рекурсии является точной имплементацией определения чисел Фибоначчи.

конечно же нет.
числа фибоначчи определяются через золотое сечение. именно этим они и интересны.
рекуррентная последовательность - это следствие из определения.

кстати, именно возврат к исходному определению через золотое сечение и позволяет перейти от суммирования последовательности к умножению матриц достигнуть производительности < O(n)


https://ru.wikipedia.org/wiki/%D0%A7...87%D1%87%D0%B8

[AP-1055D]

Цитата:

Сообщение от mazzy

конечно же нет.
числа фибоначчи определяются через золотое сечение. именно этим они и интересны.
рекуррентная последовательность - это следствие из определения.

кстати, именно возврат к исходному определению через золотое сечение и позволяет перейти от суммирования последовательности к умножению матриц достигнуть производительности < O(n)


https://ru.wikipedia.org/wiki/%D0%A7...87%D1%87%D0%B8

Конечно же нет.

Из той же статьи:

Цитата:

Более формально, последовательность чисел Фибоначчи задаётся линейным рекуррентным соотношением.

Можно прочесть ту же статью на английском, где также даётся определение через рекурсию, что намного очевиднее чем определение через матрицы:

Цитата:

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation.

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

Приведённое определение через матрицы и определители отсылает нас к значениям континуант на наборе единиц, которые в свою очередь определяются рекуррентным соотношением.

И я очень сомневаюсь, что математики древней Индии знали что такое матрица, что такое определитель матрицы, символ кронекера и как перемножать матрицы, так как соответствующая теория сформировалась в конце 17-го-середине 18-го веков.

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

Но при чём тут система ценностей? Исходя из моего опыта, у большинства работодателей есть только одна система ценностей: скорость работы, а качество кода, его выразительность, оптимизация не так уж важны.

[mazzy]

Цитата:

Сообщение от AP-1055D

Конечно же нет.

Лайк

Цитата:

Сообщение от AP-1055D

Можно прочесть ту же статью на английском, где также даётся определение через рекурсию, что намного очевиднее чем определение через матрицы:

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

я полностью согласен с тем, что числа Фибонначчи ЗАДАЮТСЯ через рекурентную формулу.

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

Цитата:

Сообщение от AP-1055D

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

1. прекрасно, что вы посмотрели. это отлично
2. через рекурсию они задаются/выводятся, а не определяются.

Цитата:

Сообщение от AP-1055D

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

Можно и их.
Но почему ИЛИ-ИЛИ? Можно и то, можно и другое...

Цитата:

Сообщение от AP-1055D

Но при чём тут система ценностей? Исходя из моего опыта, у большинства работодателей есть только одна система ценностей: скорость работы, а качество кода, его выразительность, оптимизация не так уж важны.

Т.е. вы утверждаете, что для вас работодатели применяют только одну систему ценностей - скорость? ))))
И вы утверждаете, что для вас работодатели не применяют систему ценностей - качества кода, выразительность, оптимизация?

А почему, как вы думаете?

[AP-1055D]

Цитата:

Сообщение от mazzy

Т.е. вы утверждаете, что для вас работодатели применяют только одну систему ценностей - скорость? ))))
И вы утверждаете, что для вас работодатели не применяют систему ценностей - качества кода, выразительность, оптимизация?

А почему, как вы думаете?

Исходя из моего опыта, на первом месте, то есть в приоритете, в мире AX, и, особенно, в консалтинге, важна именно скорость реализации / разработки, а потом уже всё остальное. Иногда Потому что время - деньги.

То есть, да, качество кода и всё остально тоже важно, но не на первом месте.

А выразительность кода может оценить только программист не менее сильный чем ты сам, но это бывает так редко, да и обычно не до этого, так как есть сроки в часах, дедлайн и так далее )

[mazzy]

Цитата:

Сообщение от AP-1055D

задачу лучше решить хорошо

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

[Удвой Покуров]

Цитата:

Сообщение от mazzy

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

...и самый главный - как решение этой задачи поможет ему в Аксапте

Я, честно, стал опасаться кудесников, которые могут решить подобные задачи, но не знают основных паттернов в Dax - FormLetter'a там или ничего не слышали хорошего про SettleNow.

А еще лучше - по бизнесу задать вопросы. Тогда понятно, кто это - кодер (поставь задачу - я решу, если хорошо разжевать) или Программист (сначала пойму задачу, изучу настройки, часть так / часть из кода, пойму что от меня хотят, как это работает в другом модуле, попробую переубедить или поискать другой воркэраунд или запрограммировать малой кровью).
Как можно заметить, второй - это Программист, которому лень быть консультантом. Т.е. мы получаем 2-в-1. Даже 3 в 1, т.к. отсутствует процесс коммуникации и тестирование легче. Подобные люди стоят хоть и подороже, но в разы эффективнее.