Формула для шариков :) | |
---|---|
Extortioner Автор Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Здравствуйте, есть такой сайт braingames.ru, дак вот на нём есть задачка
Исправлено 2 раз(а). Последнее : Extortioner, 01.02.12 11:38 |
Re: Формула для шариков :) | |
---|---|
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005 |
Минимальное-то не известно. Шарики могут разбиться с любого этажа. А шариков всего два.
Например, шарики разбиваются начиная с 99 этажа или с 45-го. Двумя шариками это невозможно узнать точно. ------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. Исправлено 1 раз(а). Последнее : Влад Колосов, 01.02.12 11:48 |
Re: Формула для шариков :) | |
---|---|
Extortioner Автор Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Да, блин, почему неизвестно-то... Для 100 этажей и 2х шариков минимальное число бросков - 19. Ведь если он начинает разбиваться с 99, а мы сейчас на 45, то можно один раз скинуть с 46, второй раз с 47 и так далее, пока он не разобьётся.
Исправлено 2 раз(а). Последнее : Extortioner, 01.02.12 13:03 |
Re: Формула для шариков :) | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Ни фига не понял задание... Обходим 100 этажей по-порядку и бросаем шарик. Начиная с какого-то, шарик должен разбиться. С какого именно - неизвестно, может быть, уже с первого. Тогда минимальное количество бросков - 1. И зачем второй шарик, непонятно? Чтобы каждый раз на низ не бегать?
|
Re: Формула для шариков :) | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Ты даже правильного ответа на задачу с фиксированными параметрами не знаешь (не 19, а 14!) А берёшься решать её в общем случае
Конечно же "общее" решение существует, но для >2 шариков оно IMHO будет слишком сложным. Для 2х шариков и N этажей - напротив тривиальным (если, конечно, ты знаешь верное решение для 100 этажей ). ------------------ WBR, Igor |
Re: Формула для шариков :) | |
---|---|
Extortioner Автор Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
14?!! Это как?!!
Смотрите - как я решал - предполагаем наихудший сценарий: 1 шаг кидаем первый шарик с 10 этажа он не разбивается 2 шаг 20 этаж ... 9 шаг 90 этаж шарик также не разбивается 10 шаг 100 этаж - шарик разбился Берём второй шарик и начинаем кидать с 91 этажа - ведь с 90 он ещё не разбивается 11 шаг 91 этаж - не разбился 12 шаг 92 этаж - не разбился .. 19 шаг 99 этаж - разбился. Ответ - 19 бросков. - это наихудший сценарий, КАК у вас получилось 14 бросков?! |
Re: Формула для шариков :) | |
---|---|
Extortioner Автор Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
а если он по своим характеристикам начинает разбиваться только с 36 этажа? То как тогда? Нужно узнать гарантированное минимальное количество шагов. Самое простое это скинуть с первого этажа шарик - не разбился - забраться на второй, скинуть второй шарик, потом за обоими спуститься и пойти на третий. То есть тогда будет 36 попыток, но это без оптимизации. Вопрос в гарантии и в минимальном количестве. |
Re: Формула для шариков :) | |
---|---|
PaulWist Сообщений: 14621 Дата регистрации: 01.04.2004 |
Да Игорь поделись, как 14 получается, для 2-х шариков имеем два диапазона SQRT(10**2) => 19 бросков.
------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) Исправлено 1 раз(а). Последнее : PaulWist, 01.02.12 13:44 |
Re: Формула для шариков :) | |
---|---|
PaulWist Сообщений: 14621 Дата регистрации: 01.04.2004 |
Ну вот и родилась формУла
Пусть N - число этажей, k - число шариков, тогда число бросков будет = k*N**(1/k) - 1 Для случая 1000 этажей и 3 шарика ?3*(1000)**(1/3) -1 = 29 для 10**4 ?4*(10000)**(1/4) -1 = 39 Для двух шаров и 10000 этажей ?2*SQRT(10000) - 1 = 199 ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) Исправлено 2 раз(а). Последнее : PaulWist, 01.02.12 14:02 |
Re: Формула для шариков :) | |
---|---|
Extortioner Автор Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Блин, а ведь реально... не 19, а 14 попыток Вот жесть-то
Исправлено 1 раз(а). Последнее : Extortioner, 01.02.12 14:07 |
Re: Формула для шариков :) | |
---|---|
PaulWist Сообщений: 14621 Дата регистрации: 01.04.2004 |
Колись
------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Формула для шариков :) | |
---|---|
Goodwin Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
floor(sqrt(99*2)) ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Формула для шариков :) | |
---|---|
Extortioner Автор Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Да после того как Игорь сказал, что 14 тут и колоться нечего
Смотрите - мы теперь точно знаем, что можно решить задачу с 14 бросками, значит максимальный этаж с которого мы можем кинуть - 14. то есть с 14 кинули - разбился, значит надо прокидать вторым шариком с 1го по 13 этаж. Если не разбился, то получается, что следующий бросок должен быть с 27 (14 + 13)этажа Ведь один бросок мы уже использовали то есть 14 + 13 + 12 + ... 1 = 105 это даже больше чем нужно Исправлено 1 раз(а). Последнее : Extortioner, 01.02.12 14:20 |
Re: Формула для шариков :) | |
---|---|
PaulWist Сообщений: 14621 Дата регистрации: 01.04.2004 |
А-а-а, нашел в инете blackka.qwerti.ru
Или ещё, разжевано: Цитата: ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) Исправлено 1 раз(а). Последнее : PaulWist, 01.02.12 14:33 |
Re: Формула для шариков :) | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Прочитав решение, понял задание. Чтоб сразу сообразить, шариков не хватило
|
Re: Формула для шариков :) | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Ну вот, теперь уже можешь попытаться соорудить универсальную формулу
P.S. Впрочем, я так и не представляю каким образом получить формулу для случая > 2 шаров. Если для начала взять "обратную" формулу - сколько этажей можно проверить K шарами за N попыток, то там получается сумма биномиальных коэффициентов (а значит - привет факториалы), и как её "развернуть" чтобы получить именно N... Ибо для 3 шаров получается кубическое уравнение и т.д. Т.е. для K шаров придётся решать уравнение степени K P.P.S. Вот тут собственно говоря и есть искомая формула ru-olymp-math.livejournal.com Через C_n^k автор обозначает "биномиальный коэффициент из n по k" - т.к. "рисовать" любое из его графичкеских изображений в текстовом виде накладно ------------------ WBR, Igor Исправлено 1 раз(а). Последнее : Igor Korolyov, 01.02.12 17:37 |
Re: Формула для шариков :) | |
---|---|
Crispy Сообщений: 18571 Дата регистрации: 16.05.2005 |
Чето мудрено у них там. Мне как-то интуитивно представляется, что можно все намного проще.
Т.е. допустим на примере M шариков и N этажей - всего лишь разбиваем на промежуточные этапы (спрятав пока все шарики кроме двух в карман : 1) по вышеприводившейся формуле k(k+1)/2 = N находим минимальный диапазон, например для 100 этажей и 2 шариков =14; 2) вытаскиваем из кармана третий шарик и теперь в найденном диапазоне 14 по все той же формуле k(k+1)/2 = 14 находим поддиапаззон =5; 3) и т.д. аналогично для любого числа шариков - циклический повтор с "доставанием из кармана" после нахождения поддиапазона высшего уровня каждого следующего шарика и вычислением поддиапазона следующего уровня. Причем такая процедура элементарно пишется и на фоксе. Разве нет? ------------------ В действительности все иначе, чем на самом деле. (Антуан де Сент-Экзюпери) |
Re: Формула для шариков :) | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Нет. Оптимальный диапазон первой попытки для 3-х шаров НЕ совпадает с оптимальным диапазоном для 2-х шаров. Т.е. таким макакром нельзя найти "минимальное число бросков".
Для 3-х шаров формула будет сравнительно несложной - тем не менее это УЖЕ кубическое уравнение. Напоминаю, что для 2-х шаров это было квадратное уравнение ------------------ WBR, Igor |
Re: Формула для шариков :) | |
---|---|
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005 |
мож там полином вида
(k^3+2k^2+k)/3 = N или что-то в таком духе ------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. |
Re: Формула для шариков :) | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Вот функция определяющая максимальное число этажей, которое можно проверить при помощи k шаров, используя n попыток.
[attachment 13022 glass_balls.PNG] Из неё вытекают частные решения: Для 1 шара F = n!/(1!*(n-1)!) = n Т.е. за n попыток одним шаром можно проверить n этажей - соответственно "решая" уравнение относительно n получаем что для проверки A этажей потребуется ровно A попыток, что абсолютно логично. Для 2 шаров F = n!/(2!*(n-2)!) + n!/(1!*(n-1)!) = n*(n-1)/2 + n = n*(n+1)/2 Или n^2+n-2*F=0 Решая это уравнение, получаем что n = (-1+SQRT(1+8*F))/2 - второй корень не имеет смысла, т.к. он будет отрицательным. Проверим для 100 этажей: (-1+SQRT(801))/2 = 13.65 - т.к. число попыток явно должно быть целым, округляем вверх и получаем те самые 14 попыток. Подставив обрутно в формулу это самое решение, можно увидеть что реально за 14 попыток можно проверить 105 этажей. Для 3 шаров F = n!/(3!*(n-3)!) + n!/(2!*(n-2)!) + n!/(1!*(n-1)!) = n*(n-1)*(n-2)/6 + n*(n-1)/2 + n Или n^3+5*n-6F=0 То самое кубическое уравнение - оно вышло несложное (даже приводить к "решабельному виду" не нужно), но это уже выход за рамки школьного курса математики AFAIR Его решение я приводить не буду, ибо лень - а википедия под рукой у интересующегося. ------------------ WBR, Igor |
© 2000-2024 Fox Club  |