Дерево щодня приростає гілками та листочками таким способом. У перший день виростає нова гілка. У другий день на кінцівці цієї гілки виростає 2 нові гілки а на самій гілці – 1 листочок. Кожного наступного дня на кінцівці кожної гілки, що з’явилася в останній день, з’являються по 2 нові гілки, а також по 1 додатковому листочку на кожній гілці, що існувала до цього дня (рис. 1). Скільки листочків буде на дереві по завершенні 10 дня?
Ответы
Це завдання можна вирішити, використовуючи рекурсивний підхід для підрахунку кількості листочків на кожен день.
Умова дає таку послідовність росту:
1. На першому дні - 0 листочків і 1 гілка.
2. На другий день - 1 листочок (від останньої гілки минулого дня) і 2 нові гілки.
3. На третій день - 1 листочок (з попереднього дня) + 2 листочки (по 1 на кожну гілку з попереднього дня) + 4 нові гілки.
Таким чином, кожного дня кількість листочків збільшується на кількість гілок, що існували до цього дня.
Процес можна подати так:
- На першому дні - 0 листочків.
- На другому дні - 1 листочок.
- На третьому дні - 1 (з попереднього дня) + 2 (по 1 на кожну гілку з попереднього дня) = 3 листочки.
- На четвертому дні - 1 (з попереднього дня) + 2 (по 1 на кожну гілку з попереднього дня) + 4 (по 1 на кожну гілку з попереднього-попереднього дня) = 7 листочків.
Здавалося б, кожен наступний день просто подвоює кількість гілок з попереднього дня, а також додає до кількості листочків гілки з попереднього дня. Тож, для 10-го дня:
- На 10-й день кількість листочків = 1 (з попереднього дня) + 2^9 - 1 (сума гілок за 9 днів) = 1 + 512 - 1 = 512 листочків.
Отже, на дереві буде 512 листочків по завершенні 10-го дня.