Новини
Форум
Актуално
сървърНякакъв HR всеки ден вика на интервюта за работа N човека.
По колко начина може да се подредят, но така, че да няма две каки една след друга?
Някакъв HR всеки ден вика на интервюта за работа N човека.
По колко начина може да се подредят, но така, че да няма две каки една след друга?
N бр. "добри наредби"
1 2
2 3
3 5
4 8
Правилно ли съм разбрал задачата?
Да, съвсем правилно!
В 4 през нощта обикновено е така - или изобщо не можем да мислим, или мислим брилянтно
Я малко и за тези, дето не можем да мислим - примерно 6 батковци и 2 каки чакат за интервю.Първоначално публикувано от Bibi
Да, съвсем правилно!
В 4 през нощта обикновено е така - или изобщо не можем да мислим, или мислим брилянтно
Или 8 човеци /ако броим и каките/
8 човеци - може например да са само батковци, не е ясно кои колко са.
Е, ясно е, че не може да са 8 каки.
Ако са по 4, това може да се случи по два различни начина: бкбкбкбк или кбкбкбкб.
Но понеже каките може да са по-малко, още не е готов случая за N = 8.
Сега по-добре ли е?
Всяка добра наредба с N-1 кандидати, завършваща на б, ще е добра, независимо кой дойде като N-тия кандидат.
Всяка добра наредба с N-1 кандидати, завършваща на к, ще остане добра само ако дойде б, т.е. ще се развали, ако дойде к.
т.е.
Ако F(N) е търсената функция, то F(N)=2 * F(N-1) - x,
където x e броят на добрите наредби при N-1, завършващи на к.
Някой да продължи ...
!Добавено!:
x = F(N-3)
Логиката:
Щом х е броят на добрите наредби при N-1, завършващи на к, то всичките тези наредби завършват на (нещо си)бк (иначе щяха да са лоши наредби)
като (нещо си) също са добри наредби при N-3
F(N) = 2*F(N-1) - F(N-3)
2
3
5
8
13
21
34
55
89
144
233
377
...
Това стига ли или трябва още?
Формално погледнато е вярно, да.
Но като се загледаш в чисълцата, които си написал, не ги ли познаваш от някъде?
Познати, ама знаеш ли дали няма да станат непознати при малко по-дълга опашка...
С помощ от приятел:
F(N) = F(N-1) + (завършващи на б добри комбинации с N-1 кандидати) =
= F(N-1) + (добри комбинации с N-2 кандидати) =
F(N-1) + F(N-2)
И аз това имах предвид :rolleyes:
Изненадвам се как този Фибоначи изниква буквално на всяка крачка!
Наскоро четох нещо за пчелите. Оказва се, че те редовно практикуват "непорочното зачатие" - когато пчелата иска да си роди синче, не й трябва мъж за целта. Използва мъж само ако иска щерка.
Та седнах да си нарисувам родословно дърво на една мъжка пчела и то също е по тази редица.
Както и да е...
@prt,
твой ред е да намериш някоя интересна задачка.
Отговор с цитат
