Задача про стену и кирпичи. Как решить? Добрый день!
Задали на юниорском собеседовании такую задачу, на которой я застрял.
Вот задача, подскажите куда копать? Все решение которые мне в голову приходят требуют огромного количества памяти и жутко неоптимальны:(
Сама задача:
Есть два вида кирпичей: длиной 3 и 4. Из этих кирпичей нужно построить стену длиной 25 и высотой 10 рядов. Дополнительное условие - в двух последовательных рядах щели между кирпичами не должны создавать вертикальные линии. То есть, к примеру стену длиной 8 и высотой в два ряда не построить(1 ряд (4,4), 2 ряд (4,4) - щель по середине).
Требуется посчитать, сколько всего возможных комбинаций кирпичей при постройке стены такого размера.
Заранее спасибо за помощь
Задача про стену и кирпичи. Как решить? Добрый день!
Задали на юниорском собеседовании такую задачу, на которой я застрял.
Вот задача, подскажите куда копать? Все решение которые мне в голову приходят требуют огромного количества памяти и жутко неоптимальны:(
Сама задача:
Есть два вида кирпичей: длиной 3 и 4. Из этих кирпичей нужно построить стену длиной 25 и высотой 10 рядов. Дополнительное условие - в двух последовательных рядах щели между кирпичами не должны создавать вертикальные линии. То есть, к примеру стену длиной 8 и высотой в два ряда не построить(1 ряд (4,4), 2 ряд (4,4) - щель по середине).
Требуется посчитать, сколько всего возможных комбинаций кирпичей при постройке стены такого размера.
Заранее спасибо за помощь
Задали на юниорском собеседовании такую задачу, на которой я застрял.
Вот задача, подскажите куда копать? Все решение которые мне в голову приходят требуют огромного количества памяти и жутко неоптимальны:(
Сама задача:
Есть два вида кирпичей: длиной 3 и 4. Из этих кирпичей нужно построить стену длиной 25 и высотой 10 рядов. Дополнительное условие - в двух последовательных рядах щели между кирпичами не должны создавать вертикальные линии. То есть, к примеру стену длиной 8 и высотой в два ряда не построить(1 ряд (4,4), 2 ряд (4,4) - щель по середине).
Требуется посчитать, сколько всего возможных комбинаций кирпичей при постройке стены такого размера.
Заранее спасибо за помощь
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Привет! Для решения данной задачи можно воспользоваться динамическим программированием.
Давайте создадим массив dp, где dp[i] будет обозначать количество способов построить стену высотой i.
Изначально dp[0] = 1 (если стена нулевой высоты, то способов построить ее всего один - ничего не делать).
Далее, для каждой высоты i (от 1 до 10) будем перебирать возможные способы построить стену. С каждым кирпичом добавляемым к текущей стене, будем обновлять значение dp[i] суммируя dp[i-3] (если добавляем кирпич длиной 3) и dp[i-4] (если добавляем кирпич длиной 4).
В конце алгоритма, dp[10] будет содержать искомое количество способов построить стену высотой 10.
Таким образом, необходимо написать код на Python, который решит данную задачу. Ниже привожу пример такого решения:
def count_ways_to_build_wall(height):dp = [0] * (height + 1)
dp[0] = 1
for i in range(1, height + 1):
if i >= 3:
dp[i] += dp[i-3]
if i >= 4:
dp[i] += dp[i-4]
return dp[height]
total_ways = count_ways_to_build_wall(10)
print(total_ways)
Этот код подсчитает количество возможных способов построить стену высотой 10 рядов при условиях задачи. Надеюсь, это поможет вам продвинуться к решению задачи :)