форум kia ceed
Всячина => Рюмочная => Тема начата: CarUser от Апрель 05, 2008, 23:07:09 pm
-
Как говориться, обещанного три года ждут. Простите, у меня ыврубался интернет на неделю :( sux
Но теперь выкладываю, как и обещал.
Итак, задача!
ОАО "Мытищистройкомплект" построило дом в 100 этажей (ГК еще не прошла)
У нас есть два абсолютно одинаковых сортирных бачка из квартир на 1 этаже.
Если сбросить бачок с N-го этажа - он может либо разбиться, либо нет. Если не разбился, то нисколько не попортился (то есть, с N-го этажа можно кидать сколько угодно).
Задача за какое минимальное число попыток для любых двух одинаковых бачков можно определить максимальный номер этажа, с которого можно скинуть бачок так, чтобы он не разбился.
-
Количество "безопасных" этажей + 1 "небезопасный".......Каждый раз подниматься на один этаж и бросать....
Т.е. N+1....Наверное так....
Хотя бачок упав с первого этажа уже разобьется.....
Ну а вообще, кому может понадобиться бросать бачки на головы прохожих? :D
-
Хотя бачок упав с первого этажа уже разобьется.....
ммм...могу поспорить, что не разобьется!!!!!
Сейчас в продаже имеются бачки, которые изготовлены не из керамики (санфарфора), а из пластика. ;)
Такими, как правило, комплектуют места общественного пользования (т.е. бюжетный вариант). :)
-
Чтобы установить число N, которое не известно, имея в своём распоряжении лишь два бачка, кидаем первый с 50-го (или 51) этажа (делим дом пополам). Если разбивается - идем поочередно вторым бачком с первого до 49 (50) включительно. Получаем 50-51 кидание. Если не разбивается - то будет быстрее. Поэтому, думается, надо вводить коррективы.
Если разбить дом на 3 части... Кидаем первый бачок с первой трети. Т.е. с 33 этажа... Если разбивается - "просканировать" вторым бачком займет 33... Если бачок выживает - кидаем его с 66 этажа... Разбирается - "сканируем" опять с 34 по 65. Тут получается гарантированное определение за 34 кидания. О! И т.д. :) Осталось выделить формулу и найти экстремум.
При дроблении на m частей имеем формулу
q = (m-1)+(100/m)
производная q' = 1 + 100 * (-1/ m^2)
Т.е.
100/m^2 = 1
m^2 = 100
m = 10
Итог - при дроблении на 10 частей мы найдем нужный этаж за 19 попыток.
-
СаrUser,а представь,что с тобой сделают ХОЗЯЕВА ЭТИХ БАЧКОВ! У тебя фантазия хорошая,подумай! А надо ли их бросать. :-D
-
И еще подумай,ЧТО потом тебе сделают люди снизу,на чьи головы эти бачки полетят. :-D :-D эх,бедный,бедный СаrUsеr! :-D :-D :-D
-
Флудеры :D
Еще варианты ответов будут? BRiWS дал ответ 19 попыток. Кто меньше? ;)
-
Флудеры :D
Еще варианты ответов будут? BRiWS дал ответ 19 попыток. Кто меньше? ;)
При бесконечном числе бачков теоретически возможный минимум - 7 попыток (log(2)100 - методом деления пополам)
-
Нет. За 7 попыток найти искомый этаж не реально.
-
Нет. За 7 попыток найти искомый этаж не реально.
Реально, имея бесконечный запас бачков :) Кидаем с 50-го... Разбился - кидаем с 25го... Не разбился - с 75... Затем, соответственно с 12-13, 37-38, 62-63 и 87-88... Каждый раз делим промежуток пополам. Всего за семь бросков сканируется 100-этажный дом.
На таком принципе базируется поиск по индексам типа binary-tree (бинарное дерево) в базах данных.
-
анекдот в тему вспомнил.
два кирпича лежат на крыше многоэтажки. Один из старой кладки, второго только вчера положили.
Внизу ходят люди. Молодой спрашивает:
1- ну,что вон мужик идёт, падаем?
2- не, неинтересно.
1- а вон второй?
2- не, не пойдёт. А вон на того в жёлтой каске падаем!
1- так мы же разобьёмся? толк какой?
2-Эх, молодёж, всему вас учить надо. Эй, мужик!
мужик в каске, поднимая голову вверх - чё?
всего навсего две попытки. После первой придёт прораб и вставит всем люлей, да так, что оставшийся бачок придёться вернуть на 1 этаж =)
beer
-
анекдот в тему вспомнил.
два кирпича лежат на крыше многоэтажки. Один из старой кладки, второго только вчера положили.
Внизу ходят люди. Молодой спрашивает:
1- ну,что вон мужик идёт, падаем?
2- не, неинтересно.
1- а вон второй?
2- не, не пойдёт. А вон на того в жёлтой каске падаем!
1- так мы же разобьёмся? толк какой?
2-Эх, молодёж, всему вас учить надо. Эй, мужик!
мужик в каске, поднимая голову вверх - чё?
всего навсего две попытки. После первой придёт прораб и вставит всем люлей, да так, что оставшийся бачок придёться вернуть на 1 этаж =)
beer
Прикольно! :D
-
Мне кажется, что правильный ответ 16.
-
У мну 14.
-
В 14 верится с трудом.
Как ни пробовал, даже с 15-ти попыток в худшем случае не получается.
-
У меня тоже 14.
-
14(если учитывать что бачков немерыно, и можно их крушить.....а если всего 2, как сказанов начале, то 50
-
...если учитывать что бачков немерыно..
...тогда вообще 7.
-
Молодцы. Правильный ответ - 14. Теперь рассказывайте, как дошли до этого ответа ;)
-
Если, все-таки, у нас, физически, всего 2 бачка, то:
Делим 100 этажей предположим на 5 частей - получаем:
5 интервалов по 20 этажей, начинаем кидаться с максимального этажа в интервале, т.е. с 20-го, 40-го, 60-го, 80-го 100-го - это уже 5 попыток.
Если бачек попался крепкий, то разобъется он упав с 100-го этажа, таким образом у нас остался 1 бачек и 19 этажей в последнем интервале.
получаем итоговое количество попыток 5+19 = 24.
Теперь делим 100 этажей на 10 частей - получаем:
10 интервалов по 10 этажей, начинаем кидаться с максимального этажа в интервале, т.е. с 10-го, 20-го, 30-го ... 100-го - это уже 10 попыток.
Если бачек попался крепкий, то разобъется он упав с 100-го этажа, таким образом у нас остался 1 бачек и 9 этажей в последнем интервале.
получаем итоговое количество попыток 10+9 = 19.
Теперь делим 100 этажей на 20 частей - получаем:
20 интервалов по 5 этажей, начинаем кидаться с максимального этажа в интервале, т.е. с 5-го, 10-го, 15-го ... 100-го - это уже 20 попыток.
Если бачек попался крепкий, то разобъется он упав с 100-го этажа, таким образом у нас остался 1 бачек и 4 этажа в последнем интервале.
получаем итоговое количество попыток 20+4 = 24.
Получаем оптимальный интервал ЦЕЛОЧИСЛЕННОГО деления дома - 10 этажей. И количество попыток 19.
PS Пока писал свое сочинение - CarUser дал правильный ответ :(
Но на 14 никак не смог выйти...
-
Hot_Tab, этот вариант решения уже предлагался. Подсказка. Кто сказал, что интервал должен быть постоянным? Ведь можно, например, прибавлять каждый раз разное число этажей. Допустим каждую четную итерацию - 10, каждую нечетную - 5. Т.е. можно швырять первый бачок с 10, потом с 15, 25, 30, 40, 45, 55 и т.д.
-
Hot_Tab, этот вариант решения уже предлагался. Подсказка. Кто сказал, что интервал должен быть постоянным? Ведь можно, например, прибавлять каждый раз разное число этажей. Допустим каждую четную итерацию - 10, каждую нечетную - 5. Т.е. можно швырять первый бачок с 10, потом с 15, 25, 30, 40, 45, 55 и т.д.
При твоем раскладе средняя размерность интервала = 7.5
100 / 7.5 = 13.5
Т.е. уже 14 бросков.
А максимальное расстояние между "зарубками" - все равно 10 (ты же не можешь гарантировать, что попадет в ту, где 5). Таким образом имеем 24 броска при приведенном выше раскладе. Никак не 14.
А... Понял раскладку. Да 14. Хитро. Осталось понять, как математически на неё выйти.
-
Поздравляю. До правильного ответа я сам не допер, пока подсказку не дали :D
А выйти на неё математически не сложно.
-
Ну что все замолчали?