Python-сообщество

“Саша, не сделал домашнюю работу, зато купил шоколадку. И, по глупости, начал распечатывать ее прямо на уроке… Шелест золотинки услышала учительница. Она хотела вызвать в школу родителей, но Саша уговорил ее не вызывать их, а дать дополнительное задание.

Учительница внимательно посмотрела на шоколадку (она была размером 3х4 плиток), разделила на кусочки по две плитки и угостила всех, кто сделал домашнюю работу. А Сашу попросила написать программу, которая определяет, сколько существует способов деления шоколадки размером 3×N плиток на кусочки по две плитки.

Для выполнения задания Саше нужна помощь.

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

Уже сижу 3 сутки пытаясь вычислить алгоритм. Есть ли способ решить это без использования рекурсии?

Novelette
Есть ли способ решить это без использования рекурсии?

Отредактировано py.user.next (Июль 21, 2019 11:21:03)

Там при вводе 4, должно выходить 11, что не выходит у меня ни при каких расчетах.

Добрые,люди объясните какую формулу комбинаторики использовали , или как цикл физически моделирует деление??

Не знаю как кто решает. Сам я не смог додуматься.
В первый раз встретился с этой задачей ещё до изучения динамического программирования. Не понял как её решать и просто взял приведённое тут решение.

Теперь снова встретился с этой задачей, после 14 лекции по алгоритмам от Тимофя Хирьянова.
Подумал что это однозначно на ДП задача. Сидел пол дня и не выдержав полез в инет. Как всегда наткнулся на это решение, но оно меня совсем не устраивало, т.к. не совсем понятен ход мыслей автора.

Приведу пример который написал сам после того как я узнал следующую закономерность:

 ЭЛЕМЕНТ[X] = 4 * ЭЛЕМЕНТ[X-2] - ЭЛЕМЕНТ[X-4]

 n = int(input())
res = 0
all_date = [0] * (n+1)
if n != 0 and not(n % 2):
    all_date[0] = 1
    all_date[2] = 3
    if n > 2:
        all_date[4] = 11
    for i in range(6, n+1, 2):
        all_date[i] = 4 *all_date[i-2] - all_date[i-4]
    
    res = all_date[n]
print(res)

Отредактировано Overload127 (Март 21, 2020 19:30:47)

Тоже столкнулся с этой задачей.
По теме нашел это видео - Разбор задачи 510 acmp.ru Шоколадка. Решение на C++

Попытаюсь объяснить задачу по своему, может кому пригодится.

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
| 10 | 11 | 12 |
| 13 | 14 | 15 |
| 16 | 17 | 18 |
|……………….|

1. Если N=2, то способов деления шоколадки будет 3:
(1 2) (4 5) (3 6), (1 4) (2 3) (5 6), (1 4) (2 5) (3 6).
2. Если N=4, то разбиваем задачу на 2 подзадачи: когда мы делим плитку на 2 части 3*2 и когда не делим (другими словами варианты в которых есть кусочки (4 7), (5 8) и (6 9)). Для первой подзадачи способов деления будет f(2)*f(2) = 3*3 = 9, для второй 2 способа:
(1 2) (4 7) (3 6) (5 8) (10 11) (9 12), (1 4) (2 3) (6 9) (5 8) (7 10) (11 12)
обращаем внимание на то, что эти способы симметричны (то есть можно посчитать к-во способов деления с кусочком например (4 7), а потом умножить на 2). Итого f(4) = 9 + 2 = 11.
3. N=6, снова разбиваем на 2 подзадачи: первая - делим плитку на 2 части 3*2 и 3*4, способов деления будет f(2)*f(4) = 3*11 = 33; а вот вторую в этот раз тоже придется разбить на 2 подзадачи: когда мы отделяем часть 3*2 (с 13 по 18) и когда нет, получится 2*(3 + 1). Итого f(6) = 33 + 8 = 41.
4. В принципе уже видно закономерность и можно вывести общую формулу:
f(N) = f(2)*f(N-2) + 2*(f(N-4) + f(N-6) + … + f(0))
f(8) = f(2)*f(6) + 2*(f(4) + f(2) + f(0)) = 3*41 + 2*(11 + 3 + 1) = 153

Формулу можно укоротить:
f(N) = 3*f(N-2) + 2*f(N-4) + 2*(f(N-6) + … + f(0))
для N-2 соответсвенно:
f(N-2) = 3*f(N-4) + 2*(f(N-6) + f(N-8) + … + f(0))
отсюда получаем, что
2*f(N-4) = f(N-2) - f(N-4) - 2*(f(N-6) + f(N-8) + … + f(0))
подставляем в первую формулу и сокращаем до:
f(N) = 4*f(N-2) - f(N-4)