Нахождение рекуррентного соотношения и матричного возведения в степень
Я пытаюсь найти отношение повторения для этой проблемы на Codechef:
http://www.codechef.com/problems/BWALL
Я знаю, что когда я это найду, я легко смогу решить это с помощью возведения в матрицу. Но мне трудно понять, как получить правильный ответ. Здесь есть решение, но хотелось бы, чтобы кто-нибудь объяснил это лучше?
Есть ли простое правило, чтобы найти повторения или что-то подобное? Спасибо!
Решение
«Общее правило» нахождения повторения состоит в том, чтобы понять, как решение проблемы связано с решением меньших проблем. Но более того, я не думаю, что есть общая процедура, чтобы найти повторение.
Для этого конкретного примера, вот как вы можете найти повторение.
Предположим, что у вас есть большая стена размером N. Теперь просто посмотрите на конец стены. Точнее, с конца стены найдите первое место с «вертикальным разделением», то есть первое место, где вы можете разделить стену на две меньшие стены без L-образной формы.
Пример:
(А) Вот стена:
X ### X # XXX # X
XX # XX # XXXXX
Расщепление с конца дает вам:
X ### X # XXX #X
XX # XX # XXX XX
(Б) Другая стена
X ### X # XXX
XX # XX # XXX
Расщепление с конца дает вам:
X ### X # XXX
XX # XX # XXX
Каков размер небольшого куска стены, который вы можете получить между расщеплением и концом стены? Ну, вы можете иметь 1, 2 или 3, но не больше (в противном случае вы можете сделать наименьшее разделение).
Возможности для маленького куска на самом деле те, что приведены в вашем вопросе (да, 7 маленьких блоков).
Итак, чтобы построить стену размером N, необходимо:
- постройте стену размером N-1 и добавьте к концу небольшой блок размера 1
- или постройте стену размером N-2 и добавьте к концу один из четырех блоков размера 2
- или постройте стену размером N-3 и добавьте к концу один из двух блоков размера 3.
Итак, число T (N) возможных стен с размером N равно
- количество стен с размером N-1 (с размером блока 1 в конце) -> T (N-1)
- плюс количество стен с размером N-2 с 4 возможными концевыми блоками (с размером 2) -> 4 T (N-2)
- плюс количество стен с размером N-3 с 2 возможными концевыми блоками (с размером 3) -> 2 T (N-3)
И там вы получите свое повторение.
Надеюсь, поможет!
Другие решения
Других решений пока нет …