Тази, мисля, че не я видях на първите няколко страници.

Трябва да се определи най-високия етаж на 100 етажна сграда, от който билярдна топка може да се пусне без да се счупи.

* Имаме общо две топки, които можем да пуснем от произволен етаж на небостъргача.

* Ако пусната топка не се счупи, може да се употреби отново, но нямаме право да счупим и двете топки.

С колко най-малко хвърляния можем със сигурност да определим най-високия етаж, от който може да се пусне билярдна топка без да се счупи? Как?

Be free, not cheap.

Редактирано от heptagram на 28.01.15 13:24.

половината, на половината, на половината-------- и така докато ограничиш интервал етажи, след това един по един.

Съдържаниет е скрито
Влезте за да го видите

Да де, ама я си представи че се чупи, примерно още на 10-я етаж. С твоя алгоритъм не можеш да изпълниш задачата, защото ще счупиш и двете топки след втората итерация (пускане от 50-я етаж, и от 25-я).

Be free, not cheap.

Редактирано от heptagram на 28.01.15 13:23.

Точно така, това което казах е като закачка.

Съдържаниет е скрито
Влезте за да го видите

Съдържаниет е скрито
Влезте за да го видите

Редактирано от laplandetza на 28.01.15 14:49.

грешка , минималния брой не е 6, това максимума на тарикатлъка, минималния е 2.

Съдържаниет е скрито
Влезте за да го видите

То, две хвърляния винаги е минималният брой (при счупване на топка след първото хвърляне, пускаме втората от долния етаж, а ако топката остане здрава, я пускаме от горния етаж), ако се случи така, че при първото хвърляне се налучка търсения етаж или този над него.

Въпросът е, колко е най-малкият достатъчен брой хвърляния, за да се определи етажът, който и да е той. Едно или две хвърляния са необходими, но при липса на късмет – недостатъчни. Или казано другояче, колко най-много хвърляния са необходими, за да се намери етажа. 100 хвърляния са достатъчни, но непременно необходими.

Т.е., ти казваш, че са необходими най-много 6 хвърляния за да се определи етажа. Аз казвам, че 6 хвърляния не винаги са достатъчни.

ОК, имаш 6 хвърляния. От кои етажи ще хвърлиш топките тези шест пъти, така че да определиш до кой етаж не се чупят, при условие че този етаж може да е всеки един от 100-те на небостъргача?

Be free, not cheap.

Редактирано от heptagram на 28.01.15 16:23.

Гледай сега, няма такова нещо да съм казал 6 са достатъчни, това е най - лошия случай на късметлията.
Ние не знаем дали изобщо ще се счупи и от 100-ния етаж, но не можем да проверим, имаме само 2 топки.
Минимум необходими опити за всякакви разпределения са според мен така,
първо пробваме на интервали от 9 и това е заради желанието да не приближаваме прекалено до 100., това означава първо 10 етаж, ако не се чупи продължаваме на 19, 28,37,46,55,64,73,82,91 , до тук са десет броя, ако и на 91 не се счупи можем да пробваме през две за да оптимизираме. Ако едната топка се счупи на пробванията през девет, след това ние не можем си позволим да пробваме през две , а трябва едно по едно. В случай при топка чупеща се от 100-ния или 98 етаж, става 10 плюс 5 , а в най-лошия случай при първа топка счупена на 91 и пробите с другата от 83 до 90 , където при 90 се чупи втората, става 9 плюс 8 . максимума необходим за пълно покриване на вероятностите е 17 проби. Малко съм сгрешил от началното предложение.

Съдържаниет е скрито
Влезте за да го видите

Можем още да оптимизираме за сметка на по-малко опити ако се чупят топките преди 10 етаж., изтегляме всичко с примерно два етажа по-долу , почваме от 8 етаж и така по схемата, минималният необходим брой опите за 100 процента покриване на всякакви вероятности пак ми остава 17 опита, и 17 са максималните необходими.

Пак се поправям, можем да намалим максималния брой- минимално необходимия за 100 процента покритие, постигнах 14.
-- първо на 14, после 27,39,50,60,69,76, 82,88,92,96,99 , като при чупене на първата топка продължаваме едно след едно с другата, винаги има не повече от 14 опита.

Съдържаниет е скрито
Влезте за да го видите

Съдържаниет е скрито
Влезте за да го видите

Ако започнеш от 8 етаж и топката се счупи, оставаш с една топка и 7 етажа за проверка - не можеш. В задачата се иска алгоритъма гарантирано да може да определи етажа само с две топки.

Така че не виждам начин да се пропуска повече от 1 етаж. Има някаква уловка.