Числа в себе

[humbug]

Очевидно, что p(15)=1 и p(14)=1. А вот p(n)=p(n+1)+(n+2). То есть мы снова получаем всю ту же последовательность Фибоначчи. Исключением является только p(1)=p(3).

WAT

[ElGatoAhuecado]

p(1)=p(3), а не p(2)+p(3), потому что рекурсия заканчивается при n<3, т.е. при аргументе n=2 функция себя не вызывает.

[Sirion]

За такую рекурсию руки отрывать надо.

[ElGatoAhuecado]

неэффективность алгоритмов экспоненциальной сложности не отменяет факта их существования

[Sirion]

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

[Sirion]

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

Интересно, минусующие это осознают?

[ElGatoAhuecado]

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

[Sirion]

Вы таки определитесь, «показывать разницу» или «для восьмого класса».

[ElGatoAhuecado]

А что, одно другому мешает? Или в 8 классе можно кодить не заморачиваясь по поводу сложности алгоритма?

[Sirion]

Хорошо. Как, по-вашему, должен выглядеть план урока?

[ElGatoAhuecado]

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

[Sirion]

А был разобран рекурсивный алгоритм с линейной сложностью?

[ElGatoAhuecado]

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

[Sirion]

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

Методическая ценность этого куска кода вместе с «замечательным фактом» — отрицательна. Даже если на его примере «показывать разницу между эффективным и неэффективным алгоритмом» — всё равно больше гемора, чем пользы.

[lesobrod]

Ставлю плюс в качестве поддержки развития математики на Хабре.
Идея с замощениями интересна, а вот програмная реализация… гм. как-то не очень.
Кстати, подобные вещи (особенно для школьников) очень хорошо делать на GeoGebra

[Sirion]

Идея с замощениями интересна

Стандартная задача о ступеньках. Есть лестница из n ступенек. Со ступеньки можно спуститься либо на следующую, либо через одну. Сколькими способами можно спуститься с лестницы?