xxxWandeRxxx 0 Жалоба Опубликовано 1 февраля, 2006 москалик А как понимать вот это выражение ну осталось доказать, что за меньшее число попыток нельзя и дело в шляпе и что значит В четных случаях прибавляем по X этажей, а в нечетных по X+5 - все для 100-этажного дома. ты можешь выражаться яснее, в каких таких случаях. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
москалик 0 Жалоба Опубликовано 1 февраля, 2006 xxxWandeRxxx хорошо, давайте пройдем по пунктам. Что представляло из себя прозвучавшее здесь решение? Мы рассмотрели схемы (последовательный список этажей, к которых мы будем сбрасывать бачки, до тех пор пока первый не расколется (дальше идем по каждому этажу)) с постоянным шагом, то есть такие: 1, 2, 3, ... 99, 100 ..... 10, 20, 30, 40, ..., 90, 100 11, 22, 33, 44, ....., 88, 99 .... 20, 40, 60, ................100 ..... и т.д. (шаг от 1 до 100) и доказали, что среди схем с ПОСТОЯННЫМ шагом наилучшей будет такая: 10, 20, 30, 40, ..., 90, 100 (шаг =10) и число попыток (в худшем случае) будет 19. Так ? А теперь делаем финт ушами. Возьмем схему НЕ С ПОСТОЯННЫМ шагом: 10, 15, 25, 30, 40, 45, 55, 60, 70, 75, 85, 90, 100 (прибавляем то 5, то 10 этажей , а не одинаковое число) и замечаем, что под наше доказательство о схемам с пост-м шагом она НЕ ПОПАДАЕТ. Отсюда следует, что во-первых, доказательство о схемах частного вида (с постоянным шагом) не покрывает все множество существующих схем (их миллиарды!) и, следовательно, ничего не доказывает для всей задачи А во-вторых, отсекая 99,99999% схем (все схемы с непостоянным шагом), мы с большой вероятностью пропускаем оптимальное решение. Даже если число 19 и являлось бы правильным ответом, то такое "доказательство" не могло таковым считаться. А насчет "ну осталось доказать, что за меньшее число попыток нельзя и дело в шляпе" - Никак не мог предположить, что люди "не заметят" схемы с непостоянным шагом (это ведь дико частный случай). так что это больше походило на сарказм , ибо доказывать с производными остальные схемы (с непостоянным шагом) - это полный беспредел. Более-менее понятно? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
Aland 0 Жалоба Опубликовано 1 февраля, 2006 Бросайте первый бачок с этажей под номерами:14,27,39,50,60,69,77,84,90,95,99,100. Ну а второй уже как известно.Тогда максимально будет нужно 14 бросков.Доказательство не привожу, думаю, что и так все поймут Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
москалик 0 Жалоба Опубликовано 1 февраля, 2006 УРА! А вот и правильная схема. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
москалик 0 Жалоба Опубликовано 1 февраля, 2006 может кто-то докажет, что за 13 нельзя и заодно формулу для N этажей построит? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
Aland 0 Жалоба Опубликовано 1 февраля, 2006 На самом деле до нее не трудно догадаться. Максимальное количество бросков на втором шаге должно уменьшаться в соответствии с увеличением бросков на первом, тогда общее количество будет одинаковым Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
москалик 0 Жалоба Опубликовано 1 февраля, 2006 Aland ну да. А то в схеме 10,20, .... 90, 100 при неудаче(разбитие первого бачка) в первом сегменте мы потратим максимум 10 попыток, то при неудаче в последнем -19.То есть налицо неравномерное, и, следовательно, неэффективное использование попыток. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
Aland 0 Жалоба Опубликовано 1 февраля, 2006 (изменено) Похоже что общая формула выглядит так: количество попыток равно целой части от корня квадратного из удвоенного числа этажей.А может и нет, лень думать Изменено 1 февраля, 2006 пользователем Aland Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
москалик 0 Жалоба Опубликовано 1 февраля, 2006 Aland Вообщем, докажем, что за 13 попыток нельзя: От противного. Пусть мона за 13 попыток. Тогда первый бросок должен быть не выше, чем с 13 этажа, так как иначе, если первый бак разбился с 14-го, то нуна пробросать второй бак с 1 по 13-й этаж - а это +13 попыток к одной уже совершенной, то есть уже 14. Второй бросок должен совершиться не выше, чем с 25 этажа (иначе, в случае разбития с 26 этажа, к 2 совершенным попыткам добавим 12 и получим 14) Третий бросок - не выше, чем с 36-го этажа. и т.д. (46, 55, 63, 70, 76, 81, 85, 88, 90, 91 и все) Каждый раз прибавляется число, на единицу меньшее, чем предыдущее прибавление. Получим, что за 13 попыток мона "пройти" только 1+2+3+..+13=91 этажей. => 100 этажей пройти за 13 попыток нельзя. По построению получаем общую формулу: нуна K попыток таких, что сумма первых K натуральных чисел будет не меньше, чем число этажей. Эта сумма считается как K * (K+1) / 2 >= N => K^2 + K >= 2*N => решая квадратное уравнение получим K >= (-2 + sqrt(1+8*N)) / 2 (если получаем нецелое K, то округляем до большего) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
[NoBoDy] 0 Жалоба Опубликовано 1 февраля, 2006 Aland интересно ))) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
Aland 0 Жалоба Опубликовано 1 февраля, 2006 Самое интересное будет, когда я скажу, что результаты подсчетов по моей формуле (просто ни с того ни с сего всплывшей в голове) и формуле уважаемого автора совпадают для чисел от 1 до 1000.Кому интересно может проверить сам. Кому лень, напишите куда выслать экселевский файл.Но еще более интересно для автора, что эта формула неверна. Например, она дает ответ 13 для 98 этажей. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
москалик 0 Жалоба Опубликовано 2 февраля, 2006 Aland >Самое интересное будет, когда я скажу, что результаты подсчетов по моей >формуле (просто ни с того ни с сего всплывшей в голове) и формуле уважаемого >автора совпадают для чисел от 1 до 1000. Неудивительно. sqrt(1+8N)/2 стремится к sqrt(2N) при N -> бесконечности >Но еще более интересно для автора, что эта формула неверна. Например, она дает >ответ 13 для 98 этажей. какая формула неверна? "моя" для 98 этажей выдает результат 14. ( не забываем про "если получаем нецелое K, то округляем до большего") Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
старшина 0 Жалоба Опубликовано 17 февраля, 2006 15 попыток...шаг в 10, до 90-го этажа, если и там не разбился - шаг 2...90 - 9-ая92 - 10-ая94 - 11-ая96 - 12-ая98 - 13-ая100 - 14-ая(например правильный - 99, то минус один(последний унитаз)-ещё шаг, последний)-минимаьное из максималного. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
старшина 0 Жалоба Опубликовано 17 февраля, 2006 хотя нет.. если не выше 90-го, то шаг придётся делат +1, тогда 17! Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
москалик 0 Жалоба Опубликовано 17 февраля, 2006 старшина эээ ответ уже нашли - за 14 попыток Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
старшина 0 Жалоба Опубликовано 17 февраля, 2006 хых.. перелистнул и облажалсо...бувает. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
москалик 0 Жалоба Опубликовано 17 февраля, 2006 не страшно заходите еще Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
xxxWandeRxxx 0 Жалоба Опубликовано 22 февраля, 2006 москалик закрой тему Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты
Pupsik 0 Жалоба Опубликовано 24 апреля, 2008 (изменено) Изменено 24 апреля, 2008 пользователем Pupsik Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты