Нахождение рекуррентного соотношения и возведения матрицы в степень

Я пытаюсь найти рекуррентное отношение для этой проблемы на Codechef:

http://www.codechef.com/problems/BWALL

Я знаю, что как только я найду его, я смогу легко решить его, используя матричное возведение в степень. Но мне трудно понять, как он получает правильный ответ. Здесь есть решение, но я хотел бы, чтобы кто-нибудь объяснил его лучше?

введите здесь описание изображениявведите здесь описание изображения введите здесь описание изображения

Есть ли простое эмпирическое правило для поиска повторений или что-то в этом роде? Спасибо!


c c++ recurrence algorithm matrix
person Bruce    schedule 29.01.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

Для этого конкретного примера, вот как вы можете найти повторение.

Предположим, у вас есть большая стена размера N. Теперь просто посмотрите на конец стены. Точнее, от конца стены найдите первое место с вертикальным разделением, т.е. первое место, где можно разделить стену на две меньшие стены без Г-образной формы.

Пример:

(А) Вот стена:

Х###Х#XXX#Х

ХХ#ХХ#XXXXX

Разделение с концом дает вам:

Х###Х#ХХХ #Х

ХХ#ХХ#ХХХ ХХ

(Б) Другая стена

Х###Х#ХХХ

ХХ#ХХ#ХХХ

Разделение с концом дает вам:

Х###Х# ХХХ

ХХ#ХХ# ХХХ

Каков размер небольшого куска стены, который вы можете получить между расщеплением и концом стены? Ну, можно 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)

И вот вы получаете свой рецидив.

Надеюсь, поможет!

person Dr_Sam    schedule 29.01.2013