задача про пиво

[apprentice]

14:37:43 ‹apprentice› есть 5 сортов пива и 3 вида закусок к пиву. за каждый дискретный шаг можно либо выпить кружку пива одгого сорта либо съесть закуску. т.к. закуски мало, то можно после первого шага с кружкой пива выпить а втором шаге еще одну, а вот закусывать 2 раза подряд нельзя. Сколько вариантов последовательностей сортов пива и закуки может быть на 100-м шаге? Можете не давать точный ответ, а написать как решается подобная задача если кто знает
14:40:31 ‹hroft› я так понимаю какая то одна из 3-х формул комбинаторики просто?
14:40:44 ‹apprentice› hroft, не совсем
14:40:58 ‹kent› пиво +1 приращение, закуска -1, поход в санузел стоит дженег, вопрос об оптимальном поведении )
14:41:01 ‹apprentice› нам надо кол-во уникальных последовательностей длиной 100
14:41:21 ‹apprentice› при заданных ограничениях на последовательности
14:41:54 ‹apprentice› kent, оптимально с точки зрения набухаться в сиську или приятно провести время?
14:42:52 ‹hroft› apprentice, последовательность в 100 действий именно из уникальных подпоследовательностей выпить/закусить?
14:43:12 ‹apprentice› угу
14:43:29 ‹hroft› Вот где я еще такое напишу/прочитаю а?
14:43:52 ‹apprentice› ну если нет ограничения на закуску то решается задача просто - есть 8 вариантов на каждом шаге
14:44:05 ‹apprentice› значит кол-во уникальных последовательностей будет 8^100, с ограничением вопрос сложнее
14:45:08 ‹hroft› уточняю: есть пива х1 х2 х3 х4 х5 х6 и закуски у1 у2 у3
14:45:15 ‹apprentice› угу
14:45:21 ‹hroft› я начинаю состовлять цепочку в 100 действий
14:45:38 ‹apprentice› после пива можно пить пиво или закусить, после закуски можно только пить пиво
14:47:40 ‹hroft› которая состоит из подпоследовательностей: х1 х2 у1 х3 у2 х4 х5 у3 (8 элементов), х1 у1 х2 х3 у2 х4 х5 у3 (16 элементов) .......... (допустим последняя подпоследовательность) х1 х2 у1 х3 х4 у2 х5 у3
14:47:57 ‹hroft› последний элемент имеет 100-ый номер
14:48:19 ‹apprentice› да
14:49:37 ‹hroft› ограничения: не больше двух пив подряд; не больше одной закуски подряд;
14:49:55 ‹apprentice› нет, пив подряд можно сколько угодно, главное нельзя больше 1 закуски подряд
14:50:27 ‹hroft› но в любом случае я должен все израсходовать? за одну подпоследовательность? то есть мин длина подпоследовательности 8?
14:51:06 ‹apprentice› hroft, ты должен участвоватьв 100 шагах.

[apprentice]

Решение:
1) находим рекурсию.

Рассчитаем количество варинтов для последовательностей разной длины:
а1 = длина 1 -- 8 вариантов (5 сортов пива и 3 вида закуски)
а2 = длина 2 -- 8^2 - 3^2 - (берем все возможные последовательности без ограничений, и вычитаем последовательности с ограничениями) = 64 - 9 =55

другое объяснение - если первым было пиво, то вторым может быть что угодно - итого для 5 сортов пива имеем по 8 вариантов = 5*8 =40
если первой была еда - значит после нее может быть только пиво, итого 3*5 = 15 вариантов,
всего 15+40 = 55 вариантов.

а3 = длина 3 -- можно представить как сумму варианта когда первым было пиво, и когда первой была еда
-- первой была еда (х3) -- вторым может быть только пиво (х5) - третьим может быть любой вариант последовательности длиной 1 ( х8) = 15*а1 = 15*8 = 120
-- первым было пиво (х5) -- вторым может быть любой вариант последовательности длиной 2 (х55) =5*а2 =5*55=275
всего 275+120=395 или а3=5*a2+15*a1

посмотрим чему равно количество вариантов последовательности длиной 0:
a2=5*a1+15*a0 => 55=5*8+15a0 => a0=1

[genri]

Спасибо за решение. Я вчера расписал решение до 4-го шага, получилось 2800, но формулу вывести не удалось.

[apprentice]

Спасибо за решение. Я вчера расписал решение до 4-го шага, получилось 2800, но формулу вывести не удалось.

осталось еще два шага решения

член рекурсии за номером n имеет вид: a_n = A*(x1^n)+B*(x2^n)
здесь x1 и x2 получаются из характеристического уравнения x^2=5x+15,
а A и B получаются решением системы линеныйх уравнений
n=0: A*(x^0) +B*(x^0) =1
n=1: A*(x^1)+ B*(x^1)= 8
значения А и В однозначно определяют рекурсию по двум первым её членам.