| [Форум] [Помощь] [Поиск] [Выйти] |
Добро пожаловать, ![[info]](userinfo.gif){kind=small} User
|
|
|
| ||
| Дано: Здание в N этажей и 2 одинаковых стеклянных шара. При сбрасывании шара с определенного этажа здания он может или разбиться, или не разбиться. Неразбившийся шар можно использовать повторно. Найти: алгоритм, позволяюший вычислить минимальное количество сбрасываний шаров для определения этажа, с которого они (шары) начинают разбиваться. Доказать оптимальность алгоритма. Например, 100 этажей в здании. Сколько нужно сбрасываний? |
| ||
| Завтра утром решение напишу... Если надо... |
| ||
| Date: Tue, 18 Feb 2003 00:09 +0300 Nork ответил(а) на Ваше сообщение на форуме WEB форумы на jedi.kosnet.ru. Ответом было: ---------- Лажа!!! 8 класс!!! ---------- Не надо, коли лажа. |
| ||
| Условие не очень точное. Скажем, все упирается опять же в вероятности. В идеальном случае интервал из N этажей надо разбить на 3 ~равные части и и сбрасывать с этажей граничащих на этих частях. Причем сначала надо сбросить с 1 и с последнего этажей. Если на каком-то этаже шар разбился, делим оставшийся нижний интервал на 2 (т.к. шар уже 1). общее число сбрасываний будет ~равно logN/log3 ---- Если же задачка реальная, т.е. внизу асфальт, этажи по 2.5-3 метра, то первый шар сбрасываем с 1 этажа, второй - с третьего, если на 3 разбился - сбрасываем на 2, если нет, тогда поднимаемся на 5 и сбрасываем с него. И т.д. общее число сбрасываний будет ~равно N/2+1 |
| ||
| 1) Разбиваем 100 этажей на 3 части и получаем 33 этажа. Сбрасываем с первого - не разбивается. Сбрасываем с 33-го - разбивается. Сбрасываем с 16-го - разбивается. Ответ не найден, т.е. не определен этаж, с которого шары начинают разбиваться. 2) асфальт и высота этажей роли не играют. Шар или разбивается, или нет. Почему поднимаемся на 5? PS: ~равно N/2+1 - слишком много попыток, можно за меньшее. |
| ||
| Можно за 35 попыток. |
| ||
| Можно и за меньше. Но в задаче спрашивался алгоритм. |
| ||
| N/2+1 это самый худший случай. |
| ||
| Нужен не худший, а лучший. |
| ||
| ИМХО самое простое скакать через этаж. Кинули на 1-м, выжил - поднялись на 3-й, выжил - поднялись на 5-й, разбился - опустились на 4-й и кинули второй. Выжил - критический этаж = 5, разбился - 4 :) |
| ||
| Да нет... Сейчас вспомню самый лучший |
| ||
| Идея Патрола здравая. Доработаем. Кидаем со 2, 5, 8, 1 + 3k, 97, 100-го этажей. Как разбился, кидаем второй с этажа под ним, если второй шар разбился - нашли этаж, если не разбился, значит искомый на один ниже. Итого ~ N/3 + 1 = 34. Лифта в доме нет, долго бегать :) Думаем дальше. Будем скидывать с каждого десятого, если разбился на 10k-том, значит искомый этаж находится между 10(k-1) и 10k - допроверяем оставшимся шаром (9 попыток). Итого N/10 + 9 = 19. Число 10 некрасивое, не круглое :) Дальше. Резать дом на равные части не умно, так как если первый шар разобьется на низком этаже, то из 18 попыток останутся неиспользованные. Значит секции которые ниже, должны быть больше. А верхняя - минимальна, из 1 этажа. Отсчитывая сверху: 100, 99(2 пропускаем), 97 (3 пропускаем), 94(4), 90(5), .. , 27(13), 14-ый этаж, все, дальше подвал. Начинаем ронять шар с 14, 27, etc, как только разбивается, проверяем секцию, кидая второй шар. Итого бросков всегда будет 14 максимум. Для произвольного N нужно найти такое k, что 1 + 2 + ... + k > 2N, то бишь решить k*k + k - 2N = 0. Тут я пас :) Ээ.. Паш, не надо больше, а :) я после того генерала зарекся, а ты опять за свое. Спать же хочется.. П.С. Для 3х шариков придумал, объянить смогу на пальцах, а вот для M уже трудновато так вот сходу.. ты знаешь? |
| ||
| Вроде оно... В виде n=32 предлагалась в 1997 году в Кировском ЛМШ на вступительном задании... |
| ||
| Покопался специально.. При N=15 и при шары=орехи, дом=дерево, человек=белка, давалось в той же школе для 6-ого класса.. Но это сути не меняет. Тебе не помогло ;) |
| ||
| А вариант три кокоса, и пять попыток (новое ограничение) вроде было на ТЮМ (турнир юных математиков) этого года. Если надо спрошу Колю Ч. в пятницу (самому вспоминать в лом) |
| ||
| В смысле не помогло? |
| ||
| > Резать дом на равные части не умно Очень правильная идея :) 5 баллов. > Для произвольного N нужно найти такое k, что 1 + 2 + ... + k > 2N, то бишь решить k*k + k - 2N = 0. Тут я пас :) Это называется треугольное число :) Но бросков не всегда будет 14, может быть и меньше, конечно. Важно то, что не больше 14-ти (конкретные числа - только о конкретном примере, конечно). Про М шариков не знаю, не думал еще. PS: а как там мехматовцы в лице 125-го админа и сотоварищей? :) |
| ||
| Сейчас подумал, ведь что алгоритм оптимальный я не доказал. Хотя подсказки есть ;) Так что они могут еще поучавствовать, надо только им свистнуть. Кста, и про М шариков тоже. Решил, но там махровая математика уже, это нужно на бумажке, сюда степени рисовать не удобно ;) |
| ||
| Доказательства оптимальности у меня тоже нет пока... Это уже высшая математика :) |
| ||
| Да ну? Для двух шаров - абзац, не больше.. Раз уж загадал, сам теперь думай ;)) Сроку до завтра ;) |
| ||
| Я математиков подожду :), а то что-то давно Азарика не появлялась :( |
Отправил