В гирлянде 29 лампочек, каждая может гореть или не гореть. Какое наибольшее возможное количество различных
состояний может быть у гирлянды, если в ней не могут быть выключенными две соседние лампочки? Например, у гирлянды из двух лампочек три возможных состояния: обе горят; первая горит, а вторая не горит; первая не горит, а вторая горит.
Знаешь ответ?
Чтобы оставить ответ, войдите или зарегистрируйтесь.
Ответ или решение 1
Абылкасым
Например, пусть в гирлянде имеется n лампочек, необходимо обозначить выключенную лампочку как 0, а включенную как 1. Нам необходимо найти число f(n) возможных гирлянд, для которого два нуля не будут идти подряд. Исходя из этого, f1=2 и f2=3, при условии, что n>=3. Состояния лапочек оканчивается или на 1, либо на 10, а перед этим записывается состояние гирлянды,длина которой n-1 или n-2, где два нуля не встречается.
Следовательно, здесь необходимо применить рекуррентную формулу f(n)=f(n-1)+f(n-2) при n>=3.
Следует, что это числа Фибоначчи, т.е. каждое следующее равно сумме двух предыдущих. Вычисляем число 31, оно равно 3524578
Следовательно, здесь необходимо применить рекуррентную формулу f(n)=f(n-1)+f(n-2) при n>=3.
Следует, что это числа Фибоначчи, т.е. каждое следующее равно сумме двух предыдущих. Вычисляем число 31, оно равно 3524578
Новые вопросы в разделе Информатика
s3129502@gmail.com
16.02.2024, 13:53
Информатика
7-9 класс
Адинела
05.10.2022, 08:15
Гаязутдин
05.10.2022, 01:10
Алайбек
05.10.2022, 01:05
Акияма
05.10.2022, 01:00
