Стеклянные шарики Опции Подписка на тему Сообщить другу Версия для печати Скачать тему Подписка на этот форум Режимы отображения Переключить на: Древовидный Переключить на: Стандартный Линейный

[ViGOur]

У Мегамозга есть два одинаковых стеклянных шарика. За какое минимальное число бросков можно гарантированно определить, начиная с какого этажа 100-этажного здания шарики разбиваются? 1 и 2 правильными ответами не являются! Пишите решение.

[Litkevich Yuriy]

можно пойти методм половинного деления, залазим на 50 этаж, бросаем один, если не бьётся лезим на половину выше (75 этаж)
Если бьётся то на половину ниже (25 этаж) и т.д.

[ViGOur]

Эээээ, ты видно забыл, что у нас не 100 шариков, а всего 2!

[Litkevich Yuriy]

А что если шарик не разбился им воспользоватся нельзя?
Если так, то за два броска, осталось подумать как, может оба с сотого скинуть

[ViGOur]

Незабывай, что вопрос звучит: За какое минимальное число бросков ...
Так можно пойти с третьего этажа вверх пока не разобьется, но это не будет минимальным.

[kwisp]

За какое минимальное число бросков можно гарантированно определить, начиная с какого этажа 100-этажного здания шарики разбиваются?

исходя их этого броска гарантированно определить можно с 2 бросков. сценарий таков:
на n этоже бросается первый шар и не разбивается, на n+1 второй бросается и разбивается(либо наоборот т.е. разбойный и не разбойный этажи должны быть рядом) - только так можно определить с какого этажа начинают разбиваться шары.
ответ 2 броска - минимальное кол-во бросков.
чисто теоретически возможен вариант что бросающий попадет сразу именно на n этаж значит такое возможно.

это все мысли.
итак первый шар прелагаю кидать с 4 этажа если разобьется то кидаем с 3 если нет то с 6. и так далее в случае не разбиения скачем через один этаж.
получается для точного определения в лучшем случае 2 броска в худшем 98/2=49 + 1(контрольный бросок)= 50 бросков
больше пока в голову ничего не приходит...

[ViGOur]

1. какова вероятность точного попадения на нужный этаж?
2. явно не оптимально.

[kwisp]

1. какова вероятность точного попадения на нужный этаж?
2. явно не оптимально.

1. это да вероятность мала.
2. странно если кидать перескакивая через 2 этажа уже не определишь гарантированно.
хм...... алгоритм поиска однако.

[igor_bogomolov]

минимальное число бросков можно гарантированно определить

Нужно разбить наш дом на интервалы. Начиная с нижней границы интервала, бросаем один из шаров, если не разбился поднимаемся выше, на следующую границу. Т.о. первым шаром мы отыскиваем нужный интервал. Вторым шаром, мы уже проходим по самому интервалу, вычисляя этаж на котором шар разобьется.

Имеем следущее уравнение
x + (100/x) -1 = решение, где х это наш интервал. Т.е. задача сводится к поиску оптимального интервала

    for(int x = 1; x !=100; x++)
        qDebug() << "x =" << x << "res:" << (float)(x + (100.0/x) - 1);

Получаем, что оптимальный интервал = 10. А минимальное гарантированное количество бросков 19

[Novak]

Курсе на третьем вроде ломал голову над задачками про мегамозга с сайта braingames.ru
Потому ещё помню решение.
2 igor_bogomolov
Рядом с решением)) Но кто сказал, что интервал должен быть постоянным?

[igor_bogomolov]

Рядом с решением)) Но кто сказал, что интервал должен быть постоянным?

Ну так ведь нужно минимально-гарантированное решение. Поэтому нужно найти интервал с которым можно исследовать весь дом за наименьшее количество итераций. Минимальный интервал получается 10 этажей. Т.о весь дом можно исследовать за 19 бросков.
Если интервал будет не равномерный, количество итераций увеличится.

[kwisp]

Novak,
после опубликования решения я задумался над постоянство интервала.
более вероятно что шары начнут разбиваться выше(с точки зрения физики). значит интервалы снизу должны быть длинее, а чем выше тем короче.




ширина интервала должна соответствовать вероятности разбиться на искомом этаже.
если взять вероятность разбится на 3 этаже 3/100 на 4 - 4/100 и так далее.
--------------------
может так.
на верхушке здания вероятность самая высокая интервал равен 0.

Сообщение отредактировал kwisp - 9.6.2009, 16:33

[Novak]

Минимальный интервал получается 10 этажей. Т.о весь дом можно исследовать за 19 бросков.

Я и говорю, минимальный постоянный интервал - 10. И тогда искомое количество бросков - 19.

И вероятность тут совершенно ни при чём.
Если вариантов не будет, могу сказать ответ.

[ViGOur]

Если вариантов не будет, могу сказать ответ.

Не нужно, пускай голову поломают

[kwisp]

15?

[Litkevich Yuriy]

Подзагадка, каким минимальным числом постов можно дать (найти, вычислить, угадать) правильный ответ

[igor_bogomolov]

Но кто сказал, что интервал должен быть постоянным?

Тогда 16.
Т.е. разбиваем наш дом на интервалы, по правилу тек.этаж+(16-i)
Получаем следущие контрольные точки: 16, 31, 45, 58, 70, 81, 91, 100
Далее все тоже самое, первым шаром мы ищем интервал, вторым конкретный этаж. Сумма бросков при таком разбиении всегда равна 16.

???

[kwisp]

igor_bogomolov,
говорю достатчочно 15. ведь первые два этажа откидываем сразу

[igor_bogomolov]

говорю достатчочно 15. ведь первые два этажа откидываем сразу

Объясни свой алгоритм, пожалуйста, я так не понимаю, что ты имеешь в виду. И почему первые два этажа откидываем, непонятно?

Сообщение отредактировал igor_bogomolov - 9.6.2009, 23:37

[Litkevich Yuriy]

И почему первые два этажа откидываем, непонятно?

по условию задачи. (см. первое сообщение в теме)

[igor_bogomolov]

по условию задачи. (см. первое сообщение в теме)

Нет такого условия.

За какое минимальное число бросков можно...

1 и 2 правильными ответами не являются!

По другому: 1 и 2 броска, правильными ответами не являются!

[Novak]

говорю достатчочно 15.

А почему не 14?

[Litkevich Yuriy]

Нет такого условия.

начиная с какого этажа 100-этажного здания шарики разбиваются? 1 и 2 правильными ответами не являются!

[igor_bogomolov]

Юрий, читай задание полностью. Речь идет о количистве бросков. Вычислить надо количество бросков, а не этаж.

За какое минимальное число бросков можно гарантированно определить, начиная с какого этажа 100-этажного здания шарики разбиваются?

А почему не 14?

Вот и раскрыл тайну. Я теперь понял, где я ошибся.

Сообщение отредактировал igor_bogomolov - 10.6.2009, 0:11

[kwisp]

начиная с какого этажа 100-этажного здания шарики разбиваются? 1 и 2 правильными ответами не являются!

я думал 1 и 2 это этажи

[igor_bogomolov]

Вот и раскрыл тайну. Я теперь понял, где я ошибся.

Т.е. интервалы будут такие 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99
Количество бросков каждый раз = 14

[kwisp]

igor_bogomolov,
посчитай колличество бросков если шар разобьется только на 100 этаже

[igor_bogomolov]

посчитай колличество бросков если шар разобьется только на 100 этаже

12.
Это исключение. Во всех остальных случаях, будет 14.
Так как нам нужно гарантированное решение, ответом так же является 14.

[D_K]

igor_bogomolov,
посчитай колличество бросков если шар разобьется только на 100 этаже

А зачем считать для конкретного варианта? Можно, например, посчитать, сколько потребуется бросков, если разбивается на 15 этаже или на первом .
За 14 шагов справляемся гарантированно
Меньше никак.
Вопрос в том, как вычислить число 14, а не получить его методом перебора (как я ).
Надо подумать.

[ViGOur]

UP

[scoute]

Между прочим недопонимание этого алгоритма чем-то вяжется с архиваторами ... учёные придумывают алгоритмы для частных случаев методом тыка, но до понимания "идеального" им далеко. Хотя кое-какие изыскания в области хаотичностей имеются ...
Не понятно только, как за минимум усилий определить степень "минимальной хаотичности" ряда нулей и единиц.

И разгадка, (как мне кажется), таится в 3х- или 4х-мерном представлении этого ряда.

А может даже N-мерном представлении.

[scoute]

Есть несколько идей по этому поводу, но формулу пока привести не могу.
Тут фишка в подобии. У нас 2 шарика, значит подобие будет 2-го уровня. Если 3 шарика - то 3-го уровня.

Но это для линейного поиска(19 бросков), где не нужно всё подгонять под минимум. А вот как применить смещение, я пока не знаю.
Получается, что количество бросков от первого до 14 этажа(наш частный случай) должно ровняться количеству бросков, учитывая подобие.

Прикрепленные файлы

 2_3.png ( 931 байт ) Кол-во скачиваний: 12

 

[scoute]

Ухх ... чисто практически подобрал кое-что, возможно ошибаюсь , поправьте.

Значит 100 этажей лежат между рядами {1+2+3+..+13}(=91) <100<{1+2+3+..+14}(=105). ==> 91<100<105
То есть за 14 бросков можно осилить вплоть до 105 этажа.
Как же дело обстоит с 3 шариками, тут покруче ))

3 шарика за 9(!) бросков осиливают 100 этажный дом ... Итак, найдено подбором:
37,66,88,100. ... потом любое окно по 1-му методу. В этом случае 100 этажей не дают полной картины, т.к ряд немного длиннее:
37,66,88,104,115,122,126,128,129.
Однако вывести зависимость и построить ряд мне так и не удалось.
Если первый ряд геометрически похож на
 5_12.png ( 3.21 килобайт ) Кол-во скачиваний: 2

то есть для 12 этажей понадобится минимум 5 бросков. Что касается 3х шаров, представление типа
 5_13.png ( 1.07 килобайт ) Кол-во скачиваний: 1

катит, но с некоторыми нюансами. Допустим у нас 3 шара и 100 этажей.
Тогда в объёмную пирамиду
*10 ступени - влезет 220 шаров,
*9 ступени - влезет 165 шаров,
*8 ступени - влезет 120 шаров.
*7 ступени - влезет 84 шара.
Казалось бы, раз число 100 находится между 84 и 120, ответ - минимум надо 8 бросков. ОДНАКО
Но тут затаился один нюанс. Из числа шаров, которые влезают в объёмную пирамиду, надо вычесть
число шаров, которые влезают в ПЛОСКУЮ пирамиду, построенной на ступени "минус 1 шар",
поэтому ответ будет не 8, а 9.

Привожу ряды

1) 1,   2,   3,   4,   5,   6,   7,   8,   9,  10 - просто по порядку.
2) 1,   3,   6,  10,  15,  21,  28,  36,  45,  55 - числа для плоской пирамиды.
3) 1,   4,  10,  20,  35,  56,  84, 120, 165, 220 - числа для объёмной пирамиды.

4) 1,   3,   7,  14,  25,  41,  63,  92, 129, 175 - результат для 3х шаров.

Обратили внимание?
Каждый новый ряд получается путём прибавления к текущему числу следующего элемента предыдущего ряда, то есть:
 posled.png ( 1.81 килобайт ) Кол-во скачиваний: 4

А наш искомый ряд получается дополнительным вычитанием из текущего числа предыдущего элемента предыдущего ряда, то есть:
 posled2.png ( 2.03 килобайт ) Кол-во скачиваний: 4

Однако ПОЧЕМУ надо из объёмного ряда вычитать плоский, да ещё и со смещением, этого я, увы, объяснить не могу.
Есть предположения, что когда шара 3 а броска 2, то получается переизбыток шаров, который влияет на дальнейший ряд.
Видимо надо рассматривать больше примеров с большим количеством шаров, бросков и этажей.



Ещё есть идея про треугольники. Представим 2 треуголника в виде холма (пока без фиолетового маленького)
 geo1.png ( 1.15 килобайт ) Кол-во скачиваний: 7

Высота в этом холме - это искомое число этажей, а левый и правый склоны - это балланс
между бросками без рекурсии (то есть после первого броска мы уже не подымаемся выше)
и полной рекурсией, когда приходится подыматься аж до 100го этажа. Углы "альфа" одни и те же.

Третий (фиолетовый) треугольник я пририсовал(но туда ли?) в надежде выявить зависимость для N количества шариков.
Единственное, что мне не нравится в треугольниках, это дробные числа в решении, которые потом надо округлять до целых, +1.
Вариант с шариками гораздо нагляднее и проще.

Возможно это ещё дифференциалами решается ... типо f(x)=f'(x)=f''(x)

Сообщение отредактировал scoute - 28.12.2009, 13:44