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

[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.