Задача достаточная простая. Интересно, насколько просто (коротко) можно изложить решение. Известно, что тарелка всегда разобьется, если её сбросить с некоторой определенной высоты и выше; но никогда не разобьётся, если её сбросить с меньшей высоты. Имеется М штук одинаковых тарелок и здание высотой N этажей, при броске с крыши которого тарелка заведомо разбивается. Можно неограниченное число раз бросать тарелку с любого этажа, пока она не разбилась. Требуется найти минимальное число бросков для определения номера максимального этажа, при броске с которого тарелка не разбивается. задан 1 Сен '13 22:33 behemothus |
Пусть $%f(N)$% -- искомое минимальное число бросков для $%N$%-этажного здания. Ясно, что $%f(1)=1$%, так как требуется проверить, разбивается ли тарелка при бросании с первого этажа. Удобно также положить $%f(0)=0$%. Пусть $%N > 1$%, и первый раз тарелку бросили с $%k$%-го этажа. Если она не разбилась, то проверке подлежат $%N-k$% этажей, расположенных выше. Если разбилась, то $%k-1$% этажей, расположенных ниже. Одно из этих чисел не меньше $%\lceil\frac{N-1}2\rceil$%, где скобки означают округление до ближайшего целого в сторону увеличения. По смыслу задачи ясно, что функция $%f$% является неубывающей, откуда вытекает неравенство $$f(N)\ge1+f\left(\left\lceil\frac{N-1}2\right\rceil\right).$$ Отсюда по индукции нетрудно вывести неравенство $%f(N)\ge\lceil\log_2(N+1)\rceil$%. При $%N=1$% это очевидно, а при $%N > 1$% выполнено двойное неравенство $%2^{d-1}\le N < 2^d$%, где $%d=\lceil\log_2(N+1)\rceil$%, и при этом $%d\ge2$%. Из свойств неравенств легко следует, что $%2^{d-2}\le\lceil\frac{N-1}2\rceil < 2^{d-1}$%, откуда по предположению индукции получаем $%f(N)\ge1+(d-1)=d$%. С другой стороны, для чисел вида $%N=2^d-1$% хватает $%d$% бросаний, если первую тарелку сбросить со среднего этажа. Отсюда следует, что полученная выше оценка точна, то есть при всех $%N$% имеет место равенство $%f(N)=\lceil\log_2(N+1)\rceil$%. отвечен 1 Сен '13 23:43 falcao А как Вы учитываете число тарелок? Их может не хватить!
(1 Сен '13 23:46)
DocentI
Да-да, без ограничения на кол-во тарелок эта задача становится слишком легкой.
(1 Сен '13 23:48)
chameleon
falcao. Тепло. Но все проще.
С этого момента - индукция и рекурсия.
(2 Сен '13 0:08)
behemothus
Прошу прощения: я неправильно истолковал условие задачи. При ограничении на количество имеющихся тарелок всё обстоит, конечно, иначе.
(2 Сен '13 0:19)
falcao
Да без проблем.
Скажите лучше, что именно ввело Вас в заблуждение.
Если действительно неоднозначность в условии - уточнения принимаются.
Я писал с листа, уточняя "бытовуху".
(2 Сен '13 0:27)
behemothus
@behemothus: у Вас условие сформулировано совершенно корректно. Если меня что-то и сбило с толку, то характеристика задачи как "достаточно простой". Я подумал, что речь идёт о бинарном поиске, а вопрос состоял только в оформлении. Для общего случая задача с двумя параметрами, на мой взгляд, достаточно нетривиальна. Я, кстати, позже вспомнил, что для случая M=2 и какого-то конкретного N типа 100 когда-то с ней сталкивался.
(2 Сен '13 0:41)
falcao
показано 5 из 6
показать еще 1
|
Мы давали вариант этой задачи на студенческой олимпиаде в 2010 году. Только у нас были стеклянные шарики. Я обрабатывала решения для издания (все олимпиады по 2010 г). Беру оттуда, не меняя: Задача. Имеется k одинаковых стеклянных шариков. Их кидают с некоторых этажей 1000 этажного дома. Требуется за наименьшее число бросаний X определить самый нижний этаж, при бросании с которого шарики разбиваются (или убедиться, что таких этажей в доме нет). Вычислить X а) для k = 2; б) для k = 3. Решение. Нам требуется по числу этажей в доме найти необходимое число бросков. Попробуем решить обратную задачу: по числу бросков найти этажность, для которой гарантированно можно определить самый нижний этаж разбития шаров. Обозначим через $%p(k, n)$% максимальную этажность дома, для которого это можно сделать k шарами за $%n$% бросаний. Можно считать, что $%p(k, 0) = 0$%. Пусть теперь шариков больше, чем 1. Бросим первый шарик с этажа $%s_n$%. Если он разбился, то у нас остается $%k – 1$% шарик, $%n – 1$% бросок и $%s_n – 1$% непроверенных этажей. Значит, $%s_n – 1\le p(k –1, n – 1)$% и максимальное $%s_n = p(k –1, n – 1) + 1$%. В частности, $%s_1 = p(k –1, 0) + 1 = 1$%. Более высокие, чем $%s_n$%, этажи проверять не надо, так что $%p(k, n) \ge s_n$%. Если же при первом бросании шар остался цел, то мы имеем в распоряжении еще $%(n – 1)$% попытку и снова $%k$% целых шара. За $%n – 1$% попытку мы можем проверить $%p(k, n – 1)$% этажей, начиная с номера $%s_n + 1$% (все более низкие проверять уже не надо). Поэтому мы можем определить нужный этаж во всем интервале от 1 до $%s_n + p(k, n – 1)$%. Итак,
$$p(k, n) = s_n + p(k, n – 1) = s_n + s_{n–1} + p(k, n – 2) = … = \sum_1^{n}s_i$$
Как мы показали выше, $%s_n = p(k –1, n – 1) + 1$%. а) Пусть у нас есть два шарика. Имеем $%s_n = p(1, n – 1) + 1 = n$%. Тогда $%p(2, n) = \sum_1^n i =\frac{n(n+1)}{2}$%. Итак, за 44 броска можно проверить не более 990 этажей, а за 45 – уже 1035. Значит, 45 бросков хватит. б) Для трех шариков имеем $%p(3, n) = \sum_1^n s_i $%, где $%s_i = p(2, i – 1) + 1 = \frac{i(i-1)}{2} + 1$%. Суммируя по i от 1 до n, получим $%p(3, n) = \frac16 (n^3 + 5n)$%. Поскольку $%\frac16(183 + 5\cdot 18) < 1000 < \frac16(193 + 5\cdot 19)$%, то $%X = 19$%. Думаю, из этого решения легко сделать обще, для произвольных M и N. отвечен 2 Сен '13 0:28 DocentI Кстати, если кому интересно, вот ссылка на пособие по олимпиадам, там pdf-файл.
(2 Сен '13 0:32)
DocentI
Гм... А в одну строчку можете написать? Идею алгоритма хотя бы? Если нет, я дам свое решение, за которое меня закидали тухлыми яйцами, а Вы оцените, насколько оно "зачотное", ОК?
(2 Сен '13 0:36)
behemothus
Ключевая фраза - "Попробуем решить обратную задачу: по числу бросков найти этажность, для которой гарантированно можно определить самый нижний этаж разбития шаров.". Если Вы шли по тому же пути, то ваше решение "зачотное" ;)
(2 Сен '13 0:39)
chameleon
В одну строчку? .. Это трудно. Помню, нам принесли задачу с решением, и я с первого раза ничего не поняла, дома думала. А потом еще сколько думала при подготовке к печати. Думаю, основная идея - оценивать число этажей через число бросков, а не наоборот. Ну, а формула рекуррентная выписана: $$p(k,n)=\sum_{i=1}^n(p(k-1,i-1)+1) = \sum_{i=1}^{n-1}p(k-1,i)+n$$ Я в этой задаче шла от чужого решения (отчасти). Может, с чистого листа получилось бы по-другому. Пишите ваше решение, посмотрим, интересно.
(2 Сен '13 0:41)
DocentI
Только то, что это был я. )))
На самом деле я совершенно равнодушен к славе (до мазохизма им. Перельмана), но вот собственная самооценка у меня резко выросла - и тут мне никто не помешает. Гордыня - страшный грех, но в моем положении это как глоток воздуха воздуха... Жить захотелось.
Ладно, проехали. )))
(3 Сен '13 1:45)
behemothus
|
У этой задачи есть два варианта решения: житейский и математический. Такое активное обсуждение, разговоры про рекуррентную формулу, поэтому отправляю пока это незаконченное решение. Пища для ума, так сказать. отвечен 2 Сен '13 0:09 chameleon Да. Вот это по первым строкам похоже на правильное решение. Осталось сократить текст до необходимого минимума - и написать реккурентную формулу. Из неё следует алгоритм.
(2 Сен '13 0:14)
behemothus
Ну, рекуррентная формула, можно считать, готова. $$f(N,1)=N$$ $$f(1,M)=1$$ $$f(N,M)=\min_k(1+\max(f(k-1,M-1),f(N-k,M)))$$ Но я всё ещё надеюсь, что от этого k можно избавиться :) У меня самого мозги уже немного сварены для этого.
(2 Сен '13 0:29)
chameleon
Минимумы Вам зачем вообще? Запишите формулу для максимальной высоты здания, которую можно "решить" за М тарелок и К бросков.
(2 Сен '13 0:40)
behemothus
Да, умная идея, но она уже записана выше, мне незачем пересчитывать это заново.
(2 Сен '13 0:47)
chameleon
|
Пусть N(K,M)- максимальная высота здания, которую можно "решить" за К бросков М тарелок. После первого броска остается найти либо N(K-1,M) либо N(K-1,M-1), Отсюда N(K,M)=N(K-1,M)+N(K-1,M-1)+1. Всё. Если я, конечно, не выжил из ума... Просто я "решил" эту задачу раньще чем дочитал (забыл только "в уме" единицу - и показалось, что там ряд Фиббоначи). Был на 100% уверен, что именно это и требовалось по задумке. Но то, что тут (и не только тут) понаписали, несколько поколебало мое самомнение... Но я таки не вижу, что тут не так... отвечен 2 Сен '13 1:03 behemothus Да, это правильно, только надо в рекуррентной формуле подправить второе слагаемое. Для величины $%N(k,m)$% справедлива при этом следующая формула: $$N(k,m)=C_k^1+C_k^2+\cdots+C_k^m.$$ А если мы знаем только $%N$% и $%M$%, то для числа $%k$% уже, скорее всего, не будет какой-то хорошей явной формулы.
(2 Сен '13 1:42)
falcao
А зачем что-то подправлять? Логика нарушена? Если нет, то не вижу причин делать из простого сложное. Я потрясен, как легко вы оперируете математическим редактором. Для меня это все равно, что пахать без лошади. А! Там -1 была пропущена. Но это понятно, я поправил.
(2 Сен '13 1:49)
behemothus
Имелось в виду, что там была описка. Формула в виде суммы сочетаний сразу следует из приведённой Вами рекуррентной формулы, если рассуждать по индукции. Там надо использовать свойство треугольника Паскаля: $%C_k^m=C_{k-1}^{m-1}+C_{k-1}^m$%. Оно отличается отсутствием добавочного слагаемого, равного 1.
(2 Сен '13 2:08)
falcao
А какая необходимость в таком упрощении? Никто ведь не ставит задачу довести до конкретного числа. Алгоритмическое решение за конечное число ходов... При желание можно, конечно и через сумму записать, но зачем? И если "упрощать" то оба слагаемых.... А, Вы хотите вообще без рекурсии записать, через сумму? Тогда да. И там действительно треугольник Паскаля. Это я ступил. Но я не ставил такой задачи. Вопрос был, будет ли понятно решение, записанное в две строчки. Спасибо, короче. Но если есть еще, что-то "вкусненькое" - давайте.
(2 Сен '13 2:16)
behemothus
А численно ваша формула совпадает с другими предложенными? Вообще эта задача очень странная, как задумаешься - в голове звон начинается. Пока не могу понять, почему два числа надо именно складывать, хорошо бы добавить какие-то слова.
(2 Сен '13 14:13)
DocentI
@DocentI: да, формула совпадает с ответом. Получается нечто вроде треугольника Паскаля, но к двум соседним числам предыдущей строки добавляется ещё 1. Возникают суммы сочетаний. В Вашем решении было сначала $%k=С_k^1$% (при $%M=1$%), потом $%k(k+1)/2$% (при $%M=2$%), что есть $%C_k^1+C_k^2$%, а при $%M=3$% будет $%C_k^1+C_k^2+C_k^3$%, что как раз и есть $%k(k^2+5)/6$%. И так далее. Складываются числа потому, что находится максимальная этажность, а она равна максимальной этажности снизу и сверху, плюс один этаж, с которого бросили. Это максимум, которого можно достичь.
(2 Сен '13 15:20)
falcao
DocentI, Не знаю, что тут еще добавить... Ну давайте так. Пусть в указанных обозначениях известна оптимальная стратегия. Делаем первый бросок с этажа L. Пусть шарик разбился. Это значит, что осталось М-1 тарелка на К-1 бросков и k-1 этажей, которые ниже этажа L. Отсюда Пусть шарик не разбился. Это значит, что осталось М тарелок на К-1 бросков и N(K-1,M-1)-L этажей, которые выше этажа L. Отсюда
(2 Сен '13 15:25)
behemothus
Хорошо! Жалко только, поздно исправлять уже изданный вариант пособия. Ну ладно, может будет переиздание, учту Ваше решение.
(2 Сен '13 16:16)
DocentI
Не, вот это не обязательно.
(2 Сен '13 16:44)
behemothus
Чего им не понравилось? Объяснение или ответ? (или, может, у вас были до этого натянутые отношения? впрочем, меня это не касается)
(3 Сен '13 0:42)
DocentI
показано 5 из 10
показать еще 5
|
А зачем дано ограничение на число тарелок? Вдруг их не хватит?
Я что-то подобное решала, поищу...
Вот, нашла. У меня есть решение для M от 1 до 3. Но там не так просто. Через рекуррентную формулу.
Их хватит. Если осталась лишь одна тарелка - ее можно бросить сначала с первого этажа, потом со второго... Когда разобьется, будем знать ответ.
Ну да. Рекуррентную. Она мгновенно обобщается на N и М тарелок.