|
12.10.2006, 22:15 | #1 |
Axapta
|
Цитата:
Сообщение от Косых Артём
А вот еще задача, недавно одному знакомому ее на собеседовании задавали...
Есть последовательность из 8 ячеек, в каждой ячейке могут быть либо ноль либо единица (байт и биты если по-нашему). Вопрос: как посчитать количество комбинаций расположения нулей и единиц, в которых нет двух рядом стоящих нулей??? Теорема: для n ячеек число таких способов равно F(n+1), т.е. n+1-му числу Фибоначчи. Докажем ее. Для начала докажем лемму: при расположении, удовлетворяющему условиям задачи, число последовательностей, заканчивающихся на 1 равно F(n), а на 0 - F(n-1). Докажем с помощью метода математической индукции. Предпосылка: для n=2 имеем 1-1, 1-0 и 0-1, Т.е. на 1 оканчиваются F(2)=2, на 0 - F(1)=1. Предположим теперь что это верно для n=k и докажем для n=k+1. Очевидно, что к любому из этих k-значеых "чисел" можно приписать 1 и последовательность по-прежнему будет удовлетворять условию задачи. Т.е. на 1 будут оканчиваться F(k)+F(k-1)=F(k+1). Ноль можно приписать только к последлвательностям, оканчивающимся на 1, т.е. их будет F(k). Таким образом лемма доказана. Из доказанной леммы следует доказательство теоремы: число таких n-значных последовательностей равно числу последовательностей, заканчивающихся на 1 плюс заканчивающихся на 0, т.е. F(n)+F(n-1)=F(n+1). Теорема доказана. P.S. Для n=8, F(n+1)=F(9)=55. Вроде так.
__________________
С уважением, Олег. Последний раз редактировалось oip; 12.10.2006 в 22:22. |
|
12.10.2006, 22:56 | #2 |
Участник
|
Я сделал по другому.
Посчитал возможное число комбинаций, удовлетворяющих условию для 4-х ячеек. Получилось - 8. Вот они. 0101 0110 0111 1010 1101 1011 1110 1111 Начинаются или оканчиваются нулем по три комбинации. Количество комбинаций для 8 ячек будет равно 8*8-3*3=55 Хотя про Фибоначчи, конечно, выглидит солиднее
__________________
Axapta v.3.0 sp5 kr2 |
|
12.10.2006, 22:59 | #3 |
Axapta
|
Браво! Так тоже красиво.
PS Ну почему я не умею искать простые решения...
__________________
С уважением, Олег. |
|
12.10.2006, 23:38 | #4 |
Axapta
|
Кстати, только что осознал замечательный факт:
Любое натуральное число можно представить в виде последовательности нулей и единиц как при двоичной записи, но при это разряды будут не 1,2,4,8, а числа Фибоначчи - 1,2,3,5,8 так, что в полученном представлении не будет двух единиц подряд.
__________________
С уважением, Олег. Последний раз редактировалось oip; 12.10.2006 в 23:40. |
|
17.10.2006, 13:43 | #5 |
Мрачный тип
|
kasрperuk, Dron aka Andy - молодцы , решили .
Даже с неявной неточностью(за которую приношу извинения, писал второпях) - я действительно не указал сторону весового отклонения 1 шара. Без априорно известной стороны отклонения, эту задачу за 2 взвешивания не решить Последний раз редактировалось TasmanianDevil; 17.10.2006 в 13:47. |
|
|
Похожие темы | ||||
Тема | Ответов | |||
Дурацкая задачка | 3 | |||
забавная задачка :) | 7 | |||
Еще одна логическая задачка... | 5 | |||
Задачка на сообразительность | 35 | |||
Сколько я стою? %)) | 194 |
|