На опашка за работа

[Bibi]

Някакъв HR всеки ден вика на интервюта за работа N човека.
По колко начина може да се подредят, но така, че да няма две каки една след друга?

[SetCombG.com]

[Krusteva]

 
На тоя какъв му е проблема?! 

[prt]

N   бр. "добри наредби"
1   2
2   3
3   5
4   8

Правилно ли съм разбрал задачата?

[Bibi]

Да, съвсем правилно!
В 4 през нощта обикновено е така - или изобщо не можем да мислим, или мислим брилянтно

[SetCombG.com]

[Wise]

Да, съвсем правилно!
В 4 през нощта обикновено е така - или изобщо не можем да мислим, или мислим брилянтно

Я малко и за тези, дето не можем да мислим - примерно 6 батковци и 2 каки чакат за интервю.
Или 8 човеци /ако броим и каките/

[Bibi]

8 човеци - може например да са само батковци, не е ясно кои колко са.
Е, ясно е, че не може да са 8 каки.

Ако са по 4, това може да се случи по два различни начина: бкбкбкбк или кбкбкбкб.
Но понеже каките може да са по-малко, още не е готов случая за N = 8.

Сега по-добре ли е?

[prt]

Всяка добра наредба с 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
...
Това стига ли или трябва още?

[Bibi]

Формално погледнато е вярно, да.
Но като се загледаш в чисълцата, които си написал, не ги ли познаваш от някъде?

[SetCombG.com]

[Wise]

Формално погледнато е вярно, да.
Но като се загледаш в чисълцата, които си написал, не ги ли познаваш от някъде?

Фибоначи ни обуначи....

[prt]

Познати, ама знаеш ли дали няма да станат непознати при малко по-дълга опашка...

С помощ от приятел:
F(N) = F(N-1) + (завършващи на б добри комбинации с N-1 кандидати) =
= F(N-1) + (добри комбинации с N-2 кандидати) =
F(N-1) + F(N-2)

[Bibi]

И аз това имах предвид
Изненадвам се как този Фибоначи изниква буквално на всяка крачка!
Наскоро четох нещо за пчелите. Оказва се, че те редовно практикуват "непорочното зачатие" - когато пчелата иска да си роди синче, не й трябва мъж за целта. Използва мъж само ако иска щерка.
Та седнах да си нарисувам родословно дърво на една мъжка пчела и то също е по тази редица.
Както и да е...

@prt,
твой ред е да намериш някоя интересна задачка.

[prt]

Една лесна:
http://forum.setcombg.com/index.php/topic,55631.new.html#new

[SetCombG.com Forum]