Комментарии 27
100 этажей, 1 шар. Шар остался целым при падении с 99го. Вы утверждаете, что эксперимент закончен. Хотя нет. Это вовсе не означает, что разобьётся с 100го. Итог при k=1 максимальное кол-во экспериментов n, а не n-1.
Всё, позанудствовал.
Всё, позанудствовал.
Как вы думаете, какую часть этих рассуждений вы бы смогли сделать за 15-20 минут на собеседовании на работу своей мечты?
Я в свое время на собеседовании на работу моей мечты за 15-20 минут дошел (не включая) до «разворота» задачи — до ввдения g.
Задачка интересная, но действительно, не для устного собеседования. С натягом её можно дать «надом».
Совсем недавно проходил собеседования в одной крупной компании и меня очень порадовало, что ни на одном этапе не было ни одного вопроса про люки, шарики, «сколько девяток в числах от 1 до 100» и прочего «волк коза и капуста». Хотя лет десять назад такой вопрос задавали в любой подворотне. Про шарики я первый раз увидел где-то в середине девяностых.
Совсем недавно проходил собеседования в одной крупной компании и меня очень порадовало, что ни на одном этапе не было ни одного вопроса про люки, шарики, «сколько девяток в числах от 1 до 100» и прочего «волк коза и капуста». Хотя лет десять назад такой вопрос задавали в любой подворотне. Про шарики я первый раз увидел где-то в середине девяностых.
Так же как alexeykuzmin0, минут за 15 выписал рекуррентную формулу для наименьшего числа испытаний и понял алгоритм поиска. Правда перед этим я довольно долго возился с задачей про радиоактивные шары, где формальный подход, в принципе, тот же. Ну и решал не в экстремальных условиях собеседования, а в спокойной обстановке.
Вообще говоря, не обрадовался бы услышать подобную задачку при приеме на работу. В частном случае: сто этажей и два шара — она всё-таки значительно проще.
Вообще говоря, не обрадовался бы услышать подобную задачку при приеме на работу. В частном случае: сто этажей и два шара — она всё-таки значительно проще.
тут по моему ошибка
должно быть
g(m, k) = g(m – 1, k – 1) + g(m – 1, k) + 1
то есть + попытка броска на этаже «a»
g(m, k) = g(m – 1, k – 1) + g(m – 1, k)
должно быть
g(m, k) = g(m – 1, k – 1) + g(m – 1, k) + 1
то есть + попытка броска на этаже «a»
Я еще раз проверил формулу, но ошибок не нашёл.
Значение функции g — это не количество бросков, а количество этажей, которое мы можем исследовать за m бросков с помощью k шаров.
«Плюс 1» за бросок с этажа a, о котором вы говорите, очень важно не забыть при выводе рекуррентного соотношения для функции f (см. формулу 1). Единичку действительно легко потерять, сам столкнулся с этим при первом выводе формулы.
Значение функции g — это не количество бросков, а количество этажей, которое мы можем исследовать за m бросков с помощью k шаров.
«Плюс 1» за бросок с этажа a, о котором вы говорите, очень важно не забыть при выводе рекуррентного соотношения для функции f (см. формулу 1). Единичку действительно легко потерять, сам столкнулся с этим при первом выводе формулы.
метод поиска «делением отрезка пополам»
В худшем случае понадобится ⌈log2n⌉ испытаний и такое же количество шаров (вдруг они каждый бросок будут разбиваться).
Это называется бинарный поиск, здесь нет худшего случая — кол-во испытаний всегда равно.
Испытаний — да, но вот шары могут как разбиваться на каждом шаге, так и нет 0- следовательно их затраты будут разными.
И даже для количества бросков ваше утверждение неверно, если этажей не 2^k + 1 (в данной постановке, когда заранее известно что при броске с последнего этажа шар разобьётся). Пример — 4 этажа. Понадобится или 1 или 2 броска. Дерево просто будет несбалансировнное.
Как вы при 4-х этажах с первого броска определите точно этаж?
Вы правы, я ошибся. Надо рассмотреть 3 этажа, а не 4. И 2^k+1 заменить на 2^k.
Три этажа (честных: он может как разбиться с первого, так и не разбиться. Как разбиться с третьего, так и не разбиться. 4 «нечестных» этажа сводятся к трем честны. Если он заведомо не может разбиться еще и с первого — то к можно свести к двум этажам):
1 бросок: 2 этаж.
2 бросок: 1 или 3.
2 броска всегда
4 честных этажа:
1: 2 этаж
2: 1 и победа или 3
3: 4 этаж, если он не разбился ни на втором, ни на третьем
Итого: здесь при нечетном количестве этажей всегда одинаковое число, при четном — разнится на один. И равно в худшем варианте, вроде как, n / 2+1, округленное до большего целого.
1 бросок: 2 этаж.
2 бросок: 1 или 3.
2 броска всегда
4 честных этажа:
1: 2 этаж
2: 1 и победа или 3
3: 4 этаж, если он не разбился ни на втором, ни на третьем
Итого: здесь при нечетном количестве этажей всегда одинаковое число, при четном — разнится на один. И равно в худшем варианте, вроде как, n / 2+1, округленное до большего целого.
Всё правильно. Я отвечал пользователю Veratam, который утвеждал, что количество бросков всегда одинаково, и слова «в худшем случае» лишние. На самом же деле количесво броском может отличаться на единицу.
Нет, не n / 2 + 1, ошибся.
Проверю себя же
13 этажей, разбивается на 4, «+» — не разбился, »0» — разбился:
1. 7 +
2. 3 —
3. 5 +
4 .4 — определили.
1. 7 +
2. 3 —
3. 5 +
4 .4 — определили.
Если k фиксировано, а m растёт, то в сумме биномиальных коэффициентов Cm0+...+Cmk почти весь вклад даёт последний член, потому что он растёт как (mk/k!)(1+O(1/m)), все остальные — как меньшие степени m, так что Cm0+...+Cmk=(mk/k!)(1+O(1/m)) и при фиксированном k асимптотически m0=(k!n)1/k+O(1). Например, для упомянутых в статье n=400, k=4 выражение (k!n)1/k равно 9.898… Если хочется именно оценок, а не асимптотики: например, Cm0+...+Cmk>Cmk>(m-k+1)k/k!, откуда m0≤(k!n)1/k+(k-1) (можно вычесть единицу из n за счёт Cm0 в сумме, но это уже незначимые мелочи).
Можно взять чуть более точную оценку: c(m,k) оценить, как (m-(k-1)/2)^k/k! Тогда получится m=(k!n)^(1/k)+(k-1)/2. Для n=2^40, k=10 получится 76.95.И надо будет проверить только, хватит ли 76 бросков, или надо 77.
Спасибо, такая красивая и очевидная оценка биномиального коэффициента снизу!
Я сравнил ее со своей. Для достаточно больших k (т.е. близких к m) она немного хуже, но для остальных (что нам, в принципе, более актуально) — лучше.
Проведу еще немного численных экспериментов и попробую отразить ваши идеи в самом посте, если не возражаете.
Что касается асимптотики — хорошая идея. Меня останавливают два фактора:
1. Насколько корректно при выводе формулы наименьшего числа испытаний исходить из предположения, что k — фиксировано, а m стремится к бесконечности?
2. Можно ли оценить ошибку асимптотической оценки наименьшего числа испытаний для конкретных заданных n и k? И не получится ли она сравнимой с тем диапазоном, который мы получаем с помощью изложенного в посте подхода (возможно, модернизированного с учетом вашей идеи)?
Эти вопросы адресованы и Mrrl. Такое точное попадание — 76.95 при правильном ответе 76, конечно, впечатляет! Но насколько можно доверять полученному результату, когда мы не знаем ответа?
Я сравнил ее со своей. Для достаточно больших k (т.е. близких к m) она немного хуже, но для остальных (что нам, в принципе, более актуально) — лучше.
Проведу еще немного численных экспериментов и попробую отразить ваши идеи в самом посте, если не возражаете.
Что касается асимптотики — хорошая идея. Меня останавливают два фактора:
1. Насколько корректно при выводе формулы наименьшего числа испытаний исходить из предположения, что k — фиксировано, а m стремится к бесконечности?
2. Можно ли оценить ошибку асимптотической оценки наименьшего числа испытаний для конкретных заданных n и k? И не получится ли она сравнимой с тем диапазоном, который мы получаем с помощью изложенного в посте подхода (возможно, модернизированного с учетом вашей идеи)?
Эти вопросы адресованы и Mrrl. Такое точное попадание — 76.95 при правильном ответе 76, конечно, впечатляет! Но насколько можно доверять полученному результату, когда мы не знаем ответа?
1. k есть в формулировке задачи. Если формулировку дополнить словами «давайте рассматривать поведение при фиксированном k», то корректно. Если пытаться выяснить зависимость от k тоже, то формально все равенства из моего комментария остаются верными, но асимптотические становятся бесполезными из-за того, что неявные константы внутри O() зависят от k.
2. Верхняя оценка есть в моём комментарии выше. Нижняя оценка: C_m^0+...+C_m^k \le 1+...+m^k/k! \le (m+k)^k/k! (можно раскрыть по формуле бинома и сравнить коэффициенты при степенях m), откуда m_0 \ge (k!n)^(1/k)-k.
При фиксированном k и растущем n, или, хотя бы, если k растёт медленнее логарифма n, эта оценка заведомо точнее, чем изложенный в посте подход: оценка Чернова даёт правильный порядок, только если k по порядку сравнимо с m (что примерно соответствует тому, что k растёт пропорционально логарифму n). Если же m существенно больше k, то сумма биномиальных коэффициентов определяется несколькими наибольшими, и оценки из комментариев точные по порядку.
Кстати, ещё чуть более точное «попадание» в случае, когда k растёт медленнее логарифма, можно получить, если включить второй член асимптотики после m^k: вместо m^k/k! точнее будет приближение C_m^k = m(m-1)...(m-k+1)/k! = (m^k — (1+...+(k-1))m^(k-1) + O_k(m^(k-2)))/k! = (m^k — m^(k-1)k(k-1)/2)/k! + O_k(m^(k-2)), C_m^(k-1) = m^(k-1)/(k-1)! + O_k(m^(k-2)), остальные члены суммы попадают в остаточный член, окончательно (m^k — m^(k-1)k(k-3)/2)/k! + O_k(m^(k-2)) = (m — (k-3)/2)^k/k! + O_k(m^(k-2)), откуда m_0 \approx (k!n)^(1/k) + (k-3)/2.
2. Верхняя оценка есть в моём комментарии выше. Нижняя оценка: C_m^0+...+C_m^k \le 1+...+m^k/k! \le (m+k)^k/k! (можно раскрыть по формуле бинома и сравнить коэффициенты при степенях m), откуда m_0 \ge (k!n)^(1/k)-k.
При фиксированном k и растущем n, или, хотя бы, если k растёт медленнее логарифма n, эта оценка заведомо точнее, чем изложенный в посте подход: оценка Чернова даёт правильный порядок, только если k по порядку сравнимо с m (что примерно соответствует тому, что k растёт пропорционально логарифму n). Если же m существенно больше k, то сумма биномиальных коэффициентов определяется несколькими наибольшими, и оценки из комментариев точные по порядку.
Кстати, ещё чуть более точное «попадание» в случае, когда k растёт медленнее логарифма, можно получить, если включить второй член асимптотики после m^k: вместо m^k/k! точнее будет приближение C_m^k = m(m-1)...(m-k+1)/k! = (m^k — (1+...+(k-1))m^(k-1) + O_k(m^(k-2)))/k! = (m^k — m^(k-1)k(k-1)/2)/k! + O_k(m^(k-2)), C_m^(k-1) = m^(k-1)/(k-1)! + O_k(m^(k-2)), остальные члены суммы попадают в остаточный член, окончательно (m^k — m^(k-1)k(k-3)/2)/k! + O_k(m^(k-2)) = (m — (k-3)/2)^k/k! + O_k(m^(k-2)), откуда m_0 \approx (k!n)^(1/k) + (k-3)/2.
Вот уж не думал, что пригодятся мои школьные изыскания…
Правда я по-другому ответ получил.
nightmare4all.narod.ru/100/100.htm
Правда я по-другому ответ получил.
nightmare4all.narod.ru/100/100.htm
Да-да, я же сослался на вашу статью в разделе "«Явная» формула подсчета наименьшего числа испытаний". Теперь, когда буду вносить в пост коррективы, укажу ее автора.
Не пробовали по изложенному в работе принципу рассмотреть случай k шаров?
Не пробовали по изложенному в работе принципу рассмотреть случай k шаров?
Да… Точно… Не заметил ссылки. :)
Не пробовал. Я когда получил это решение, подумал, что, видимо, есть способ гораздо более простой, потому как решение этой задачи всегда приводится без вывода, а, значит, очевидно. Ну, а раз не нашёл простого способа решения задачи, то и за обобщения не стал браться.
Не пробовал. Я когда получил это решение, подумал, что, видимо, есть способ гораздо более простой, потому как решение этой задачи всегда приводится без вывода, а, значит, очевидно. Ну, а раз не нашёл простого способа решения задачи, то и за обобщения не стал браться.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Задача про стеклянные шары — решение в общем случае