“Саша, не сделал домашнюю работу, зато купил шоколадку. И, по глупости, начал распечатывать ее прямо на уроке… Шелест золотинки услышала учительница. Она хотела вызвать в школу родителей, но Саша уговорил ее не вызывать их, а дать дополнительное задание.
Учительница внимательно посмотрела на шоколадку (она была размером 3х4 плиток), разделила на кусочки по две плитки и угостила всех, кто сделал домашнюю работу. А Сашу попросила написать программу, которая определяет, сколько существует способов деления шоколадки размером 3×N плиток на кусочки по две плитки.
Для выполнения задания Саше нужна помощь.
Примечание: все плитки в шоколадке пронумерованы, поэтому способы деления, симметричные относительно точки или оси могут будут разными.”
Уже сижу 3 сутки пытаясь вычислить алгоритм. Есть ли способ решить это без использования рекурсии?
Полная версия: Задача на деление шоколадки
NoveletteКомбинаторно можно вычислить.
Есть ли способ решить это без использования рекурсии?
Думаю, будет ((3xN) / 6) * 3. Ну так, на первый взгляд.
http://www.imageup.ru/img92/3431458/chocolate.png.html
Там при вводе 4, должно выходить 11, что не выходит у меня ни при каких расчетах.
n = int(input()) a, b, c = 1, 3, 0 if n%2 == 1: b = 0 else: for i in range(1, n//2): c = 4*b - a a = b b = c print(b)
Добрые,люди объясните какую формулу комбинаторики использовали , или как цикл физически моделирует деление??
Не знаю как кто решает. Сам я не смог додуматься.
В первый раз встретился с этой задачей ещё до изучения динамического программирования. Не понял как её решать и просто взял приведённое тут решение.
Теперь снова встретился с этой задачей, после 14 лекции по алгоритмам от Тимофя Хирьянова.
Подумал что это однозначно на ДП задача. Сидел пол дня и не выдержав полез в инет. Как всегда наткнулся на это решение, но оно меня совсем не устраивало, т.к. не совсем понятен ход мыслей автора.
Приведу пример который написал сам после того как я узнал следующую закономерность:
А вот текст программы:
Остаётся только один вопрос: эта закономерность была обнаружена методом перебора, верно? (Хотел бы я их видеть, но если задача новая, то скорей всего закономерности я не увижу
)
В первый раз встретился с этой задачей ещё до изучения динамического программирования. Не понял как её решать и просто взял приведённое тут решение.
Теперь снова встретился с этой задачей, после 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)
Остаётся только один вопрос: эта закономерность была обнаружена методом перебора, верно? (Хотел бы я их видеть, но если задача новая, то скорей всего закономерности я не увижу
)
Тоже столкнулся с этой задачей.
По теме нашел это видео - Разбор задачи 510 acmp.ru Шоколадка. Решение на C++
По теме нашел это видео - Разбор задачи 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)
| 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)