mild personality changes and possibly death (lepin) wrote,
mild personality changes and possibly death
lepin

количество путей (математика)

Не помнить математику - наверное, стыдно. Но не так страшно, если можешь вывести результат при потребности. Я как-то вспоминал в уме, как решается квадратное уравнение. Решил, но теперь уже не помню. Но знаю, что могу опять это сделать.
Так вот, в Khan Academy есть раздел головоломок, очень занятный. Я не придумал сам, как решить togglers, а решение синих лбов до сих пор не готов принять. А вот тут результат посчитал правильно,
http://www.khanacademy.org/video/path-counting-brain-teaser - но у меня схема была куда менее элегантная (и уж тем более я не использовал факториалы, как надо было)

Варианта пойти со старта два, поэтому количество путей в прямоугольнике X на Y равно числу путей в прямоугольнике (X-1) на Y плюс числу путей в прямоугольнике (Y-1) на X.
Если одна сторона два, то можно не редуцировать, число вариантов равно второй стороне (то есть, сколько вариантов сдвинуться - по одному на каждую из клеток).
Соответственно, f(6x6)=2*f(5x6)
f(5x6)=f(5x5)+f(4x6)
=2f(5x4)+f(3x6)+f(4x5)
=3f(5x4)+f(3x6)
=3f(4x4)+3f(5x3)+f(2x6)+f(3x5)
=3f(4x4)+4f(3x5)+f(2x6)
=6f(4x3)+4f(3x4)+4*5+6
=10f(4x3)+26
=10f(4x2)+10f(3x3)+26
=40+20*3+26
=126
А у 6х6, соответственно, 252.
Ну только я не так расписывал, а нарисовал сначала мелкие квадратики и число путей в них посчитал, а потом пошел в сторону увеличения.
Но как это все объединить в упрощенную формулу - это еще надо подумать (как отсюда прийти к факториалу?)
Tags: math
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments