Question

Очень Голодная Гусеница составляет себе меню на ближайшие 10 дней. Каждый день она хочет съесть один фрукт. У нее есть такой набор фруктов: груша, 5 яблок и 4 сливы. Сколькими способами она может составить меню так, чтобы никакие два дня подряд не есть фрукт одного и того же вида?

Answer 1

Грушу и четыре сливы можно выложить в ряд пятью способами. Если начинать с яблок то будет пять способов. Если начинать с груши со сливами и чередовать яблоками то тоже будет пять. Итого десять.

Answer 2

Всего 18 способов - см. таблицу (вверху номера дней, слева количество способов)

Answer 3

Давайте разберемся в этой задаче.

У голодной гусеницы есть три варианта фруктов: груша, яблоко и слива. Она хочет составить меню на ближайшие 10 дней так, чтобы никакие два дня подряд не есть фрукт одного и того же вида.

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

Пусть f(n) будет количество способов составить меню на n дней. Тогда у нас есть следующие рекуррентные соотношения:

f(1) = 3 (гусеница может выбрать любой из трех фруктов в первый день) f(2) = 3 * 2 = 6 (гусеница может выбрать любой из трех фруктов в первый день, и любой из двух оставшихся во второй день)

Для n > 2, у нас есть два случая:

1. Если гусеница выбирает фрукт того же вида, что и в предыдущий день, то на n-й день она должна выбрать фрукт из двух оставшихся видов. Таким образом, f(n) = 2 * (f(n-2)).

2. Если гусеница выбирает фрукт другого вида, то на n-й день она может выбрать фрукт из двух оставшихся видов. Таким образом, f(n) = 2 * (f(n-1)).

Итак, мы можем записать рекуррентное соотношение для f(n):

f(n) = 2 * (f(n-1) + f(n-2)), для n > 2.

Используя эти рекуррентные соотношения, мы можем вычислить f(10):

f(1) = 3 f(2) = 6 f(3) = 2 * (f(2) + f(1)) = 2 * (6 + 3) = 18 f(4) = 2 * (f(3) + f(2)) = 2 * (18 + 6) = 48 f(5) = 2 * (f(4) + f(3)) = 2 * (48 + 18) = 132 f(6) = 2 * (f(5) + f(4)) = 2 * (132 + 48) = 360 f(7) = 2 * (f(6) + f(5)) = 2 * (360 + 132) = 984 f(8) = 2 * (f(7) + f(6)) = 2 * (984 + 360) = 2708 f(9) = 2 * (f(8) + f(7)) = 2 * (2708 + 984) = 7384 f(10)