ElGatoAhuecado Jun 12 2013 at 10:39

Числа в себе

2 min

6.1K

Mathematics *

From sandbox

Comments 18

humbug Jun 12 2013 at 12:28

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

WAT

ElGatoAhuecado Jun 12 2013 at 13:33

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

Sirion Jun 12 2013 at 12:57

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

ElGatoAhuecado Jun 12 2013 at 13:39

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

Sirion Jun 12 2013 at 14:44

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

UFO landed and left these words here

Sirion Jun 12 2013 at 18:26

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

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

ElGatoAhuecado Jun 12 2013 at 20:35

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

Sirion Jun 12 2013 at 21:30

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

ElGatoAhuecado Jun 13 2013 at 07:49

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

Sirion Jun 13 2013 at 09:20

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

ElGatoAhuecado Jun 13 2013 at 09:31

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

Sirion Jun 13 2013 at 09:38

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

ElGatoAhuecado Jun 13 2013 at 09:44

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

UFO landed and left these words here

Sirion Jun 13 2013 at 00:27

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

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

lesobrod Jun 12 2013 at 13:59

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

Sirion Jun 12 2013 at 18:33

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

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