Математические и логические задачи
-
В скандинавских древних сказах
Есть забавные примеры.
Гномы падки до алмазов,
Что найдут — несут в пещеры.Так как знал лесной народец,
Что поблизости их нету,
То построили заводец,
Спрятанный в горе от света.Там алмазного конвейра
Было вечное гуденье,
А народ благоговейно
Думал, что землетрясенье.Но однажды злые тролли
Дождались-таки момента:
Все приборы раскололи
Испытательного стенда.Чтоб камней проверить прочность
И никто не видел чтобы,
Гномы стали тёмной ночью
Их бросать из небоскрёба —Выяснять этаж, с какого
(Значит, выше и подавно)
Камень, брошенный с балкона,
Будет биться постоянно.Но алмаз — на вес алмаза,
Жалко бить такие камни.
Добровольцам дали сразу
Только два для испытаний.Пусть на каждое бросанье
Полагается минута.
Сколько в стоэтажном зданьи
Гномы максимум пробудут,Если под покровом ночи,
Пока люди не глазеют,
Каждый гном до смерти хочет
Сделать это побыстрее? -
Постоянно они могут не биться даже с сотого этажа, но как это определить ? Или сделать погрешность для определения" постоянно"- допустим 90% случаев ( или 95), тогда уже можно посчитать, сколько статистически экспериментов для этого нужно ( но очень долго и долго счяитать придется).
Если принять условие, что они бьются "постоянно"( 100% случаев) с какого-то уровня ( хотя на практике этого не будет), упростив задачу, то можно попробовать посчитать.. -
самая близкая степень двойки для 100-это 7, т.е двоичный логарифм из 100 окгругляем до 7. Можно еще прибавить 1 попытку на проверку нижнего( верхнего ) этажа на всяукий случай( хотя это не нужно). Те. ответ 7 ( или 8
) -
@xajik ответ неверный
-
Участник @xajik написал в Математические и логические задачи:
Если принять условие, что они бьются "постоянно"( 100% случаев) с какого-то уровня
Это и имелось в виду, скорее всего
-
Спрашивается, сколько гномы пробудут максимум, если действуют оптимально.
Подразумеваем также, что гномы стараются минимизировать матожидание времени пребывания в доме.Определения
Назовём этаж плохим, если его номер не ниже номера уже проверенного этажа, с которого разбился алмаз.
Назовём этаж хорошим, если его номер не выше, чем наивысший уже проверенный этаж, с которого алмаз не разбился.
Назовём остальные этажи подозрительными - они выше всех хороших и ниже всех плохих.
Примечание: если первый алмаз ещё не кидался, то хороших или плохих этажей нет - все подозрительные.
Примечание: если первый алмаз разбился сразу, то хороших этажей нет - все или плохие (с какого разбился и выше), или подозрительные (ниже этажа, с какого разбился).
Примечание: если подозрительных этажей нет - это значит, что эксперимент закончился успешно (не значит оптимально) - гномы точно знают, где проходит граница между хорошими и плохими этажами. Если остались подозрительные этажи, это значит, что их задача не решена.Разобьём время пребывание гномов в доме на два этапа: первый этап длиной T1, когда они кидают первый алмаз и второй этап длиной T2, когда первый алмаз потрачен, и они кидают второй.
Если представить себе, что первый алмаз уже потрачен, то гномы обязаны, тут никуда не денешься, второй алмаз кидать с каждого подозрительного этажа по порядку, начиная с нижнего подозрительного (иначе есть вероятность потратить и второй алмаз, не получив точного ответа). В этом случае T2 равно максимум количеству оставшихся подозрительных этажей. Теперь задача гномов сводится к тому, чтобы оставить как можно меньше подозрительных этажей для второго этапа и в то же время не растягивать по времени первый этап.
Они могут на первом этапе, например, действовать методом дихотомии, а именно кинуть с 50-го этажа, потом с 75-го, потом с 87-го и т.д. Т.е., делить оставшийся отрезок примерно пополам. Не факт, что именно этот метод оптимален - нужно проверять. Допустим, мы знаем оптимальный метод для первого этапа. Тогда можно найти T1 как наиболее вероятное кол-во сделанных попыток до разбивания первого алмаза, а как найти T2 - см. выше. Останется сложить T1 и T2.
На самом деле я знаю, что есть неточность в рассуждениях выше - "оптимизировать" на самом деле нужно оба этапа одновременно.
Дальше я продолжать сейчас не буду, потому что нужно работать. -
Ну так оптимально по- "дихотомии" ( двоичному разбиению) и должно быть. Двоичный логарифм( по основанию два) от 100 будет приерно 7.(6,644)-столько бросков нужно сделать ( столько алмазов потратить, если они такие дорогие). Но гномов можно поставить одновременно, и если алмазов не жалко и можно отследить результаты каждого броска при одновременном бросании- то можно сделать это сразу одновременно за 1 минуту, но тогда все 100 алмазов.
Иначе я не понимаю одно из условий( легко запутаться при таком количестве текста и нечеткости ). Часто пропускаю такие длинные условия, например, не понял, что вычисляется затраченное время, а не количество алмзов, но все равно не ясно четко условие... -
Метод дихотомии неправильный, если кинуть сразу с 50 этажа, потом 49 раз кидать? многовато
-
Метод дихотомии- деление пополам. Если сначала кинуть с 50, то потом ( если разбилось) - с 25 этажа ( или другого, близкого к середине отрезка от нуля до 50). Пример. Кидаем с 64-32-16-8-4-2 этажей. И каждый раз , предположим, будет разбиваться.Бросили 6 раз, и предположительно, на 1 этаже может не разбиться, но мы должны и это проверить, поэтому не менее 7 бросков ( затрат алмазов) в теоретически самой длиннй серии попыток мы должны использовать. В случае, если где-то в серии не разбивается, мы делаем попытку "дихотомии" наверху отрезка, который еще не исследовали ( например на 16 этаже уже не разбилось, поэтому наш следующий бросок- середина от 32 и 16- то есть 24 этаж и так далее), продолжая делить его пополам- и те же 7 максимальных попыток ( часто 6).
Если есть зависимость цены времени от цены алмазов ( то тоже по логарифму, но уже с другими основаниями можно быстро вычислить число одновременных попыток), то мы можем кидать разное число камней одновременно ( тогда это будет троичное и так далее разбиения). Можно кинуть сразу 100 одновременно со всех 100 этажей и потом тупо посчитать количество целых камней, если время 1 минута времени намного ценнее стоимости 99 алмазов.
Н я, возможно, просто не понял условий полностью. В чем сложность подобных приукрашенных условий- часто непонятно, что требуется найти и при каких ограничениях. -
@xajik по условию алмаза ровно два. Можно разбить оба, но не больше.
-
Добровольцам дали сразу
Только два для испытаний.
я понял, что каждому из добровольцев ( а их несколько) дали по 2 камня, те. камней не 2
хотя условие нечектое, о чем я уже предупредил хотя бы сам себя -
если всего 2, то просто кидаем со 2-го, потом с 4-го, максимальная последовательность 50
-
Участник @xajik написал в Математические и логические задачи:
Добровольцам дали сразу
Только два для испытаний.
я понял, что каждому из добровольцев ( а их несколько) дали по 2 камня, те. камней не 2Если было бы так, то решение простое - 100 добровольцев - по 1 на каждый этаж и каждому по алмазу. Занимает ровно минуту.
-
Это если стоимость минуты времени намного ценнее стоимости 99 алмазов, а если нет?
Пусть Химичка потом уточнит, сколько алмазов. Всего 2?
А , я понял, если 2 всего, то кидаем сначала на 33 этаже. и потом снизу если разбился-33 попытки. Если не разбился- то на 66 и так далее.
34 попытки должно выходить максимально.
Тогда это разбиение на 3, и достаточно частый случай, наверно, в общем случае это переформулируется на разбиение на "эн плюс 1" в подобных примерах. Наример, задача взвесить 27 монет на весах. найти 1 бракованную монетку из той же серии. -
@xajik можно и меньше, чем 33
Да, два алмаза на все опыты -
Пусть х- количество частей. на которые мы отсекаем" 100 ( делим). Тогда 100/х количество оставшихся попыток, когда первый камень разобьется. Уравнение ( функция) х+100/х и нам надо решить ее минимально, Блин, тут надо вспоминать производные ))
Так что ль? Может быть лучше есть метод, но я пока на этот только смог надумать.
В Вольфрам Альфа, чтобы никаких производных не вспоминать, сказано. что локальный минимум при х=10, т.е максимальное количество попыток 19
Но я не уверен., что правильно.
На всякий случай, поясню метод. Мы кидаем с того этажа, который после оптимального "разбиения/отсечения из уравнения. Если оптимально 10, то делим 100 на 10-10 этаж. При разбитии камня, нам остается 10 попыток пробежаться снизу по всем отсеченным этажам. Если не разбился, то идем на 10 этажей выше и повторяем. -
@xajik ответ 19 неправильный
-
Ну тогда я не решил
И сегодня вряд ли решил бы, задачка сложная и плюс трудный день).
Там еще хитрость, что на последнем этапе "вверху" когда могут остаться 2 камня перебрать получается быстрее, чем по одному этажу. И еще я банально ошибся в уравнении-делить надо на х-1, т. е 100/(х-1)+х решаем
локальный минимум 11 и тогда ответ 17
но хитрость последних двух камней может перечеркнуть и это, и я не уверен, что нет метода получше
методом перебора решать не хочу. а пока ничего больше на ум не приходит
подумал, что надо решать "с последних этапов- к первым", и что-то типа рекурсивным методом, ведь соотношение- разбились, не разбились дает разную скорость при разбитых и неразбитых камнях, но это нужно время и мозги , которых у меня пока не предвидится -
чтоб не оставялть на потом, последняя попытка. если не решил, то сдаюсь
))
Рекурсивным методом решаю, это не перебором, но достаточно муторно-но надежнее( вряд ли ошибусь сильно), на последнем этапе должно остаться ( оптимально ) 4 этажа, тогда нам нужно всего 2 минуты ( 2 попытки)
Тогда приходим к такому методу-сначала бросаем на 15 этаже, если не разбился- то повышаем на 15-1 этаж и бросаем выше-т.е на 29, потом на 42-54-65-75-84-92 этажах ( каждый раз повышая на последнее повышение минус 1), если где-то камень разбивается, то последним за суммарные 15 попыток проходим по одному снизу оставшиеся. В идеале, здание должно иметь 109 этажей, тогда точно 15 попыток требуется( если ни один камень не разбился, то в последний раз можно сбросить оба, сэкономив время)
ответ при таком методе 15
хотя если начать с 14 тем же методом, то получится 14 всего, странно
, опять криво решал, кароче , ответ 14 и сдаюсь -
@xajik ответ 14, ход мыслей кривоват, но близок, начинать надо не с 14-го этажа
На 109 действительно нужно уже 15
С ходом мыслей помогу: если разрешается сделать N бросаний, какова максимальная этажность здания, для которого эта задача имеет решение? -
Если начинать с 13, то не получается у меня таким методом. 13-25-36-46-55-63-70-76-81-85 сделали 10 бросков ( попыток), осталось 3 ( до полных 13) и надо 15 оставшихся этажей проверить- не сходится.( или 14 если не кидать на 100).
Если отступить на шаг назад -бросили на 81 этаже, осталось проверить 19 этажей за 4 попытки...Мы не можем отсечь больше 3 этажей снизу, ведь если камень первый разбивается, нам не хватит более 3 попыток, чтобы уложиться в 13. Поэтому это тоже безрезультатно. Даже если предположить, что на 100-том кидать не нужно.
Не вижу как улучшить метод, да и подустал от задачи ))
По максимальной этажности здания- пока не могу вывести общую формулу рекурсии. На первом этапе 5 этажей....а, теперь начинаю что-то понимать ; значит, у меня ошибка в подходе была, нам не нужно проверять с точностью все этажи, в формуле рекурсии у меня тогда была ошибка. На первом этапе ( в решении задом наперед) если камень разбился, нам нужно, чтобы осталось 2 этажа и мы кидаем на одном из оставшихся...ТОгда для 2 бросков нам нужно 6 этажей, для 3 бросков-10, 15-4 броска ( минуты)
далее 10-15-21-28-36-45-55-66-78-91-105, те. 12 попыток нужно, т.е. кидать нужно начинать с 12 этажа, потом с 24-35-....
пока не могу изобразить формулу рекурсии ( лень, да и трудновато), из Вольфрам Альфа показана формула a_n = 1/2 (n^2 + 5 n + 6) (for all terms given)
хотя у меня бы другая формула была бы, через эн от эн минус 1А откуда такая задача? Хоть я в математике профан, но все равно сложная....)( ну или хотя бы требующая достаточно времени) Еще и в стихотворной форме, наверно из какого-то сборника взята...
-
Мне кажется, если опять не ошибся, есть "запас" в 3 этажа, поэтому можно начинать бросать хоть с 9, хоть с 12 этажей включительно ( и скорее всего даже с 13, если потом в случае разбития бросать со 2-го вверх), далее прибавляем +13 этажей, потом +12 и т.п, каждый раз минус один этаж к прибавлению ( чтобы в случае разбития первого камня оставалось ровно 12-количество истраченных попыток+1 этаж для пробегания оставшихся , начиная со 2-го снизу еще неисследуемого на каждом из бросаемых последовательностей этажей)
т. е 9-22-34-45-35-64-72-79-85-90-94-97 этажи кидаем если камни не разбиваются, 13 попыток ( 13 минут), соответсвенно можно сдвинуть с 9 до 13 этаж вначале, подстроив все остальное ( сдвинув)
но в этот момент я опять начал сомневаться , поэтому завершаю решение, не уверен в абсолютной точностиС интересом посмотрю за подробным правильным ответом и решением, но я на этом-пас, слишком много времени потратил на задачу ( часа полтора в общей сложности-даже больше), хотя освежил голову- было на пользу даже в случае совершенно неверного решения.))
-
Я решал неправильно, спасибо Химичке)). Хотя метод я понял в общих чертах самостоятельно ( с какой попытки -ужас??
)Но в связи с этой задачей возникла другая формулировка задачи, изменение условий. Все то же самое-2 камня алмаза, 100 этажей, но алмазы обладают тремя качествами- не разбиваются, разбиваются и "светятся"- то есть на каком-то конкретном этаже они от удара начинают светиться( ну или что-то такое...).
На каком-то определенном этаже они светятс. этажом ниже-не разбиваются, а одним этажом выше- уже разбиваются. задание- найти этот "светящийся этаж. И сколько времени ( попыток ) займет? -
@xajik я бы просто снизу вверх кидала, но это не самый оптимальный вариант
-
Жил-был кот у тёти Вали,
Котофеем, помню, звали.
Занял целую террасу
И ни в чём не знал отказу —Ни в сосиске, ни в сметане,
А меж тем под ним в чулане
Жил мышонок-невидимка
В пятикомнатной квартирке.Все пять комнаток, конечно,
Были там попарно смежны,
И из всех своих каморок
Он прогрыз пятёрку норок.Слух у Котофея тонок:
Слыша, как скребёт мышонок,
Он стряхнул с себя дремоту
И помчался на охоту.Два прыжка — и он в чулане;
В нос мышиным духом тянет,
А в стене подряд пять норок,
Не поймёшь, откуда шорох.Где мышонок, кот не знает —
В середине или с краю,
Но, просунув в норку лапу,
Угадает — может сцапать.Если он не угадает,
Мышь всегда перебегает
Из каморки, где сидела,
Рядом вправо или влево.Расскажи, в каком порядке
Надо в норки лазить лапкой,
Если наш котяра хочет
Всё закончить покороче,Ну а мышь дрожит за шкуру
И притом совсем не дура?
Сколько сделает ходов
Самый умный из котов?
