Question

Сад состоит из 11 деревьев, посаженных в ряд. Известно, что высота первого дерева всегда равна 100 метрам, а высота любых двух соседних деревьев всегда отличается ровно на 1 метр. Сколько существует различных садов с такими свойствами?

Answer 1

Давай попробуем рассуждать логически.
Если бы сад состоял из двух деревьев, то было бы два варианта садов: 100+99 и 100+101. Если бы досадили третье дерево, то каждый из предыдущих садов удвоил бы число вариантов: первый 100+99+98 и 100+99+100, и так же второй 100+101+100 и 100+101+102. Подмечаем закономерность: каждое добавляемое дерево удваивает количество вариантов. А сад из одного дерева имеет лишь один вариант.

Поэтому ответ: 1 * 2 * 2 * 2 * ... (десять двоек умножаются) = 2^10 = 1024 варианта садов. 

Думаю что так, если не напутал. Но ты лучше проверь за мной. 

Answer 2

У меня такая же задача была, я её уже решила, получилось всё правильно.
1 дерево = 100
второе 101 или 99
третье 100 или 102 или 100 или 98
Если пронаблюдать то каждое следующее дерево увеличивает свой возможный рост на два
Например: было 100, стало 101 или 99 ; было 101 или 99, стало 100 или 102 или 100 или 98, ТО ЕСТЬ 2 в 9 степени=512

Answer 3

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

Пусть dp[i] - количество различных садов, которые можно создать с i деревьями. Нам нужно найти dp[11].

Начальные значения: dp[1] = 1 (только одно дерево высотой 100 метров)

Далее мы можем использовать рекуррентное соотношение:

dp[i] = dp[i-1] + dp[i-2]

Пояснение:

• dp[i-1] соответствует садам, в которых последнее дерево имеет высоту 100 метров. Мы можем добавить новое дерево с высотой 101 метр, чтобы получить новые сады.
• dp[i-2] соответствует садам, в которых последнее дерево имеет высоту 101 метр. Мы можем добавить новое дерево с высотой 100 метров, чтобы получить новые сады.

Мы начинаем с dp[1] и продолжаем до dp[11], используя рекуррентное соотношение. По окончании мы получим значение dp[11], которое будет содержать количество различных садов с заданными свойствами.

Давайте вычислим это:

dp[1] = 1 dp[2] = dp[1] + dp[0] = 1 + 1 = 2 dp[3] = dp[2] + dp[1] = 2 + 1 = 3 dp[4] = dp[3] + dp[2] = 3 + 2 = 5 dp[5] = dp[4] + dp[3] = 5 + 3 = 8 dp[6] = dp[5] + dp[4] = 8 + 5 = 13 dp[7] = dp[6] + dp[5] = 13 + 8 = 21 dp[8] = dp[7] + dp[6] = 21 + 13 = 34 dp[9] = dp[8] + dp[7] = 34 + 21 = 55 dp[10] = dp[9] + dp[8] = 55 + 34 = 89 dp[11] = dp[10] + dp[9] = 89 + 55 = 144

Таким образом, существует 144 различных сада с заданными свойствами.