Давно ли вы ходили в походы? Если не очень, то должны помнить, что в походе бывают нужны спички. Нормальные сухие спички. И вот по этому поводу вспомнилась задачка. (Впрочем, деталей оригинальной задачки я все равно не помню, так что додумывал сам.)
У вас есть три коробка по 20 спичек в каждом. Однако известно, что какой-то один из них полностью состоит из хороших спичек, а в двух других половина (10 штук) спичек бракованные и непригодны для использования. Однако на ощупь брак никак не опознается, поэтому различать коробки вы не умеете.
Вы можете попытаться поджечь любую из спичек. С бракованной спичкой, естественно, ничего не случится, а хорошая загорится. Беда в том, что после этого ее уже нельзя будет взять в поход. Такую операцию назовём тестированием спички. Вы можете тестировать столько спичек, сколько захотите.
1. Какое (в худшем случае) количество хороших спичек вам удастся взять в поход? (Брать в поход бракованные спички ни в коем случае нельзя.)
2. Попробуйте придумать алгоритм, который позволяет отобрать это количество, затратив при этом наименьшее (в среднем) число тестирований.
У вас есть три коробка по 20 спичек в каждом. Однако известно, что какой-то один из них полностью состоит из хороших спичек, а в двух других половина (10 штук) спичек бракованные и непригодны для использования. Однако на ощупь брак никак не опознается, поэтому различать коробки вы не умеете.
Вы можете попытаться поджечь любую из спичек. С бракованной спичкой, естественно, ничего не случится, а хорошая загорится. Беда в том, что после этого ее уже нельзя будет взять в поход. Такую операцию назовём тестированием спички. Вы можете тестировать столько спичек, сколько захотите.
1. Какое (в худшем случае) количество хороших спичек вам удастся взять в поход? (Брать в поход бракованные спички ни в коем случае нельзя.)
2. Попробуйте придумать алгоритм, который позволяет отобрать это количество, затратив при этом наименьшее (в среднем) число тестирований.
в худшем случае у нас в руках окажется хороший коробок и на проверку этого мы потратим 11 спичек, останется всего 9
ОтветитьУдалитьесли же у нас сначала в руках окажется бракованный коробок, то в худшем случае мы потратим все его 10 хороших спичек на проверку, после чего у нас останется два непротестированных коробка
Если жечь по одной спички из каждого коробка (round-robin) и отбрасывать коробок если одна спичка не зажжётся - в худшем случае мы сожжём 31 спичку (11 из хорошего коробка и по 10 из плохих) и 9 спичек останется.
ОтветитьУдалить