[Архив!] Чистая математика, физика, химия и т.п.: задачки для тренировки мозгов, никак не связанные с торговлей - страница 356
Вы упускаете торговые возможности:
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Регистрация
Вход
Вы принимаете политику сайта и условия использования
Если у вас нет учетной записи, зарегистрируйтесь
Одинаковые они по прочности. Цвета имеют принципиальнейшее значение: их перекрашивать никак нельзя, т.к. это эксклюзивный каприз заказчика для кодера. Шарика только два.
P.S. Задачка действительно серьезная. Я и не подозревал, что подобные задачки дают в качестве испытательных.
Для случая "100 этажей, 2 шарика" можно обойтись в худшем случае шестнадцатью бросками
// сначала думал, что понадобится девятнадцать, но после твоих интенсивных намёков на засаду, сообразил что "есть варианты".. :)
Стратегия:
Сначала бросаем красный шарик (каприз программера) :
Этажи: 16, 31, 45, 58, 70, 81, 91, 100
На каком бы этаже красный шарик не разбился, кидаем синий начиная с предыдущего "уцелевшего в красном списке +1", и кидаем до "красного-разбитого -1".
Итого в худшем случае ==16.
// для общего случая формулу выведу когда просплюсь. если кто-то не опередит. идея в общем ясна.
Вы наняли человека рубить лес. Рубить его он будет неделю (7 дней). У вас есть кусочек золота в 7 грамм и каждый день вы должны платить ему ровно 1 грамм. Но разрубить кусочек вы можете только дважды. Как вы будете ему платить?
Но, вопрос как так точно разрубить не имея измерительных приборов. А если таковые приборы есть в наличие, то есть и другой способ: разделать кусочек в 7 грамм 1-м или 2-мя рубками, предварительно разхреначив и изогнув кусочек на пеньке :)
-
Mathemat, какие у вас впечатления от парада победы?
Хотя нет не самый худший. мы можем бросить шарик на 1-м этаже и он разобьется, тогда все дальше нет смысла перебирать. Максимум 100 (не разбился).
Второй шарик дает нам шанс использовать деление попалам. пока он не разобьется, что сокращает касимальное количество, первый бросаем на 50 этаже. Разбился идем с 1-го до 49. Не разбился, бросаем на 25 и т.д
получаем мин 2 шага, максимум. 50.
Невижу смысла в цветах. если нет условия. Типа на каком максимальном этаже красный шар неразобьется
хотя, конечно, виной всему условие задачи, если бы написали, что есть цепочка из семи звеньев и разрубить можно только одно, то было бы более определеннее..
правильно ли я понял, что самый худший вариант. перебор. бросаем шарик на 1, 2 и т.д. этаже, пока он не разобьется. и в принципе 2-й шарик не нужен. Да ?
самый худший это бросать шарик через два этажа, двигаясь снизу вверх, пока не разобьется и бросить этажом ниже второй
Richie, зачем усложнять задачу, когда в ней нет никакого намека на то, что нужно думать, как его разрубить? Пеньки какие-то, нагревы. У нас есть возможность разрубить кусок на любые две части с любой точностью два раза. Задача уже решена Вами.
MetaDriver правильно движется. Просто найденный вариант еще не оптимален.
Красный: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 98 // последний ход (98 вместо 99) позволяет сэкономить один худший бросок, в случае если с 95 не разбит
Синий: заполняет последний неразбитый промежуток красного, как и в прошлый раз.
Richie, зачем усложнять задачу, когда в ней нет никакого намека на то, что нужно думать, как его разрубить? Пеньки какие-то, нагревы. У нас есть возможность разрубить кусок на любые две части с любой точностью два раза. Задача уже решена Вами.
Уговорил. Вот вариант с 14 бросками.
Красный: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 98 // последний ход (98 вместо 99) позволяет сэкономить один худший бросок, в случае если с 95 не разбит
Синий: заполняет последний неразбитый промежуток красного, как и в прошлый раз.
Да, интересно. В решении, приведенном там, где нашел, наилучший написанный вариант был почти таким же (с 99), но все равно выходит 14. Проблема в доказательстве. Почему мы не сможем решить задачу для любого случая за 13 шагов?
Я знаю, что доказательства тут не любят (особенно ты, Володя), да и самому кажется, что это оптимальное решение. Но чего-то не хватает. Почему именно такой алгоритм - наилучший?
P.S. При данном алгоритме доказать, что 14 - нинимальное, несложно. ОК, замяли. Для общего случая будем решать или нет?