Перейти к содержанию
Форум города Мытищи
Авторизация  
москалик

Бачки (решена)

Рекомендуемые сообщения

москалик

А как понимать вот это выражение

ну осталось доказать, что за меньшее число попыток нельзя и дело в шляпе 

и что значит

В четных случаях прибавляем по X этажей, а в нечетных по X+5 - все для 100-этажного дома.

ты можешь выражаться яснее, в каких таких случаях.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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 и являлось бы правильным ответом, то такое "доказательство" не могло таковым считаться.

 

 

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

 

 

Более-менее понятно?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Бросайте первый бачок с этажей под номерами:

14,27,39,50,60,69,77,84,90,95,99,100. Ну а второй уже как известно.

Тогда максимально будет нужно 14 бросков.

Доказательство не привожу, думаю, что и так все поймут

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

На самом деле до нее не трудно догадаться. Максимальное количество бросков на втором шаге должно уменьшаться в соответствии с увеличением бросков на первом, тогда общее количество будет одинаковым

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Aland

 

ну да. А то в схеме 10,20, .... 90, 100 при неудаче(разбитие первого бачка) в первом сегменте мы потратим максимум 10 попыток, то при неудаче в последнем -19.

То есть налицо неравномерное, и, следовательно, неэффективное использование попыток.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Похоже что общая формула выглядит так: количество попыток равно целой части от корня квадратного из удвоенного числа этажей.

А может и нет, лень думать

Изменено пользователем Aland

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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, то округляем до большего)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Кому интересно может проверить сам. Кому лень, напишите куда выслать экселевский файл.

Но еще более интересно для автора, что эта формула неверна. Например, она дает ответ 13 для 98 этажей.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Aland

 

>Самое интересное будет, когда я скажу, что результаты подсчетов по моей >формуле (просто ни с того ни с сего всплывшей в голове) и формуле уважаемого >автора совпадают для чисел от 1 до 1000.

 

Неудивительно. sqrt(1+8N)/2 стремится к sqrt(2N) при N -> бесконечности

 

 

>Но еще более интересно для автора, что эта формула неверна. Например, она дает >ответ 13 для 98 этажей.

 

какая формула неверна?

"моя" для 98 этажей выдает результат 14.

 

( не забываем про "если получаем нецелое K, то округляем до большего")

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

15 попыток...

шаг в 10, до 90-го этажа, если и там не разбился - шаг 2...

90 - 9-ая

92 - 10-ая

94 - 11-ая

96 - 12-ая

98 - 13-ая

100 - 14-ая

(например правильный - 99, то минус один(последний унитаз)-ещё шаг, последний)

-минимаьное из максималного.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
:) Изменено пользователем Pupsik

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

Загрузка...
Авторизация  

×
×
  • Создать...