а если на 14 не разбился, а на 27 разбился, у тебя остается 1 шарик и 27-14=13 этажей
Не совсем так: 14ый и 27-то проверены уже. Осталось 12 этаже между ними. Так что 2 попытки Мне не хватает внимания со стороны окружающих. Обнимите меня, кому не лень. максимум 12 = 14.
Боже, сколько чукчей нечитателей! Лишь бы ляпнуть, 51, 20, 19 попыток. Тыщу раз сказали правильный ответ 14 попыток!
Это теория, а разбиться он может и при падении с первого этажа :) При этом не забываем: шариков всего два Правильный алгоритм будет выглядеть немного подругому
ps уже вижу чуть выше - 20 попыток, алгоритм зачетнее, респект!
14 попыток.
ткинте носом плиз
Ну а прочитать комменты религия не позволяет? :) http://www.yaplakal.com/findpost/31906267/...pic1030989.html Начинаем с 14. Повторяем итерации до тех пор, пока не разобьется, уменьшая шаг (14, 27, 39, 50, 69, 77, 84, 90, 95, 99) Как разбился, начинаем кидать второй, с этажа+1, с которого не разбился первый шар в предыдущем примере. 14 попыток в самом худшем случае. Предположим, что на 14-м не разбился, а на 27 разбился. Начинаем второй кидать с 15, 16 и т.д.
Это сообщение отредактировал WhiskIn - 7 фев 2015 в 14:20
Поднимаясь на каждый четный этаж кидать один шарик. Если он разбился - спуститься на этаже ниже и кинуть второй шарик. Если второй шарик разбился, значит это нужный нам этаж. Если второй не разбился, значит нужный - на этаж выше.
И всё таки! Подвергать минимизации именно кол-во бросков или пройденного пробега по лестницам? Что такое бросок? Высунул руку в окно и разжал пальцы - то есть это не трудно. То есть важнее выяснить - минимальный путь, а не кол-во бросков. Чё-то мне кажется что ответ измениться. Или нет?
И всё таки! Подвергать минимизации именно кол-во бросков или пройденного пробега по лестницам? Что такое бросок? Высунул руку в окно и разжал пальцы - то есть это не трудно. То есть важнее выяснить - минимальный путь, а не кол-во бросков. Чё-то мне кажется что ответ измениться. Или нет?
Выбираем стоэтажное здание, по которому по наружной стене ездит лифт с форточкой. Садимся в него и начинаем гонять по этажам. На нужном выбрасываем шарик. Пробег по лестнице = 0. Профит
Выше товарищ предоставил ссылку http://elementy.ru/problems/843, где подробно расписана логика решения таких задач. Метод перебора оставьте для начальных классов школы, а если будет 569 шариков и 1872738 этажей?
Ответ находится по формуле, где m = мин. число бросков, k = количество шариков, n = количество этажей. В нашем случае ответ m = 14.
Это сообщение отредактировал Twakelme - 7 фев 2015 в 14:55
2 алгоритма , по обоим максимум 51 попытка. 1 кидаем снизу в верх с чётных этажей, после того как шар разбивается. кидаем второй с нижнего нечетного 2 кидаем с 50го . если разбился. то с первого до 50го, не разбился. то с 51го по 100ый
Алгоритм может быть таким, бросаем с каждого 10-и кратного этажа максимум используем 10 попыток.
Допустим первый шар разбился только на последней десятой попытке. Второй шарик мы кидаем с чётных этажей начиная от 92 и заканчивая в худшем случае на 98 этаже. Методом исключения получаем искомый этаж.
Тут люди и 51, и 20 вычислили. Нахуй эти твои выебоны с формулами, без каких либо расшифровок? Что такое "к"? Вот что это такое, я вас спрашиваю, умм?
слушай, умм?ник с выебонами без формул, это вообще то общий алгоритм, а не решение конкретной задачи. Да, с точки зрения кол-ва попыток не самый оптимальный вариант. Если нарисовать без математики и без алгоритмов, то ответ уже дали тут 14, а если учитывать, что на 13-й итерации шарик не разбивается, а 14-й бросок последний, то его и делать не обязательно, т.е. всего бросков можно сделать 13, чтоб определить на каком этаже разобьется шарик, хотя в выходные голова не варит совсем, мог и накосячить 14 - 27 - 39 - 50 -60 - 69 - 77 - 84 - 90 - 95 - 97 - 99 - 100
Это сообщение отредактировал Neskachet - 7 фев 2015 в 14:54
Кидаем с шагом 8. 8-16-24-32-40-48-56-64-72-80-88-96. Если разбился например на 32, кидаем с шагом 1 с 24. Итого максимум 19 бросков. Лучше пока не получается)
какая забавная ветка... правильный ответ уже раз 20 озвучили разжевали и прояснили, но все равно кто-то снова влезет и выдаст хуйню... возможно самому интереснее зарешать, чем просто посмотреть ответ, но все же я вот не решился выдавать свой результат, пока не сверился с остальными..
какая забавная ветка... правильный ответ уже раз 20 озвучили разжевали и прояснили, но все равно кто-то снова влезет и выдаст хуйню... возможно самому интереснее зарешать, чем просто посмотреть ответ, но все же я вот не решился выдавать свой результат, пока не сверился с остальными..
А на ЯПе всегда так. Есть такая категория - "нечитаки". Увидел тему и обязательно надо донести свою ИСТИНУ, не читая комментов. Пусть она даже и не истина вовсе, а ерунда на постном масле
Во первых 14,14 бросков, но это для больших значений! - Считай 15.
Во вторых, из-за дискретности малых величин требуется перепроверка, выше давал расчет, и получается 16 бросков! Доводы для решения делал умозрительно...
Это сообщение отредактировал Berdisheff - 7 фев 2015 в 15:50
какая забавная ветка... правильный ответ уже раз 20 озвучили разжевали и прояснили, но все равно кто-то снова влезет и выдаст хуйню... возможно самому интереснее зарешать, чем просто посмотреть ответ, но все же я вот не решился выдавать свой результат, пока не сверился с остальными..
А на ЯПе всегда так. Есть такая категория - "нечитаки". Увидел тему и обязательно надо донести свою ИСТИНУ, не читая комментов. Пусть она даже и не истина вовсе, а ерунда на постном масле
Есть ещё другой вариант. Бывает откроешь 10-15 тем без комментариев... А когда откомментировал - смотришь, твой комментарий уже на 7-й странице.
Через каждый 10-ый этаж сбрасывать, а потом от предпоследнего десятка вверх по одному этажу. Макс - 20 бросков, мин - как получиться.
Это сообщение отредактировал simonrus - 7 фев 2015 в 16:00
максимум 20 попыток самый длинный алгоритм строится из двух циклов:
1) выбираем шаг 2 этажа с 01 до 10 02 04 06 08 10 если разбился на одном из этажей, то второй шарик кидаем с n-1 этажа и выясняем, какой предел. таким образом, за 6 шагов мы выясняем точный этаж в десятке
2)теперь бьем все этажи на 10 десятков (при условии, что первый шар еще цел)
20 30 40 50 60 70 80 90 100 за 14 шагов мы определили точный десяток
переходим к первому циклу получаем максимум 14+6 шагов = 20 как-то так...
максимум 20 попыток самый длинный алгоритм строится из двух циклов:
1) выбираем шаг 2 этажа с 01 до 10 02 04 06 08 10 если разбился на одном из этажей, то второй шарик кидаем с n-1 этажа и выясняем, какой предел. таким образом, за 6 шагов мы выясняем точный этаж в десятке
2)теперь бьем все этажи на 10 десятков (при условии, что первый шар еще цел)
20 30 40 50 60 70 80 90 100 за 14 шагов мы определили точный десяток
переходим к первому циклу получаем максимум 14+6 шагов = 20 как-то так...
максимум 20 попыток самый длинный алгоритм строится из двух циклов:
1) выбираем шаг 2 этажа с 01 до 10 02 04 06 08 10 если разбился на одном из этажей, то второй шарик кидаем с n-1 этажа и выясняем, какой предел. таким образом, за 6 шагов мы выясняем точный этаж в десятке
2)теперь бьем все этажи на 10 десятков (при условии, что первый шар еще цел)
20 30 40 50 60 70 80 90 100 за 14 шагов мы определили точный десяток
переходим к первому циклу получаем максимум 14+6 шагов = 20 как-то так...
Для вашего алгоритма три шара нужно.
два ко второму переходим при условии, что шар все еще целый
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии. Авторизуйтесь, пожалуйста, или зарегистрируйтесь, если не зарегистрированы.
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
yaplakal.com
bergerug7 фев 2015 в 14:00