Моё меню Общее меню Пользователи Правила форума Все прочитано
Вернуться   uForum.uz > БЕСЕДКА > Разминка для мозгов
Регистрация
Знаете ли Вы, что ...
...до того как открыть новую тему, стоит использовать поиск: такая тема уже может существовать.
<< Предыдущий совет - Случайный совет - Следующий совет >>

Разминка для мозгов Загадки, задачи, головоломки - тренируем мозг


Ответить

 
Опции темы Опции просмотра
Старый 14.07.2015 23:09   #1  
Known ID Group uParty Member Ultimate
Аватар для JH
Оффлайн
Сообщений: 10,876
+ 3,660  10,910/4,662
– 584  284/212

Uzbekistan
Разбиваем стакан

Дано: есть 100-этажное здание и два одинаковых стакана неустановленной прочности. Если сбросить стакан с какого-то из этажей, он разобьется об землю. Естественно, при падении с любого из последующих этажей стакан тоже разбивается. При падении со всех предыдущих этажей стакан не бьется. Задача: придумать стратегию, которая позволит с наименьшим количеством попыток гарантированно определить, начиная с какого этажа падение стакана будет приводить к его разбиванию. Примечание: стакан можно кидать с любого этажа, и если он не разбился, то засчитать попытку и пробовать повторно. Когда разобьются оба - игра заканчивается, больше попыток нет.


Если бы стакан был один, то гарантированно можно было бы найти только со 100 попыток, ведь пришлось бы его кидать с каждого этажа, начиная с самого нижнего, при любом другом раскладе, если стакан разобьется, а вы его еще не бросали со всех предыдущих, вы не будете знать точного ответа.

С двумя проще. Например, можно сбросить первый с 50-го этажа. Предположим, разбился. Тогда кидаем второй со всех этажей с 1-го по 49-й, и максимум на 50-й попытке находим искомый этаж.

Значит, нужно найти стратегию с минимальным числом попыток.

Пожалуйста, не гуглим, ответ в сети есть.
Ответить 
Старый 14.07.2015 23:34   #2  
Аватар для shumbola
Оффлайн
Сообщений: 3,324
+ 337  890/588
– 3  31/25

Uzbekistan
Цитата:
Сообщение от JH Посмотреть сообщение
Если бы стакан был один, то гарантированно можно было бы найти только со 100 попыток
Мне кажется достаточно было бы 51 попыток. Бросаем сразу с 50го этажа. Если не разбился поднимаемся вверх и до последнего. Если разбился спускаемся до первого.
Согласно условиям задачи.
__________________
404 Not Found
Ответить 
Старый 14.07.2015 23:35   #3  
Known ID Group uParty Member Ultimate
Аватар для JH
Оффлайн
Сообщений: 10,876
+ 3,660  10,910/4,662
– 584  284/212

Uzbekistan
Цитата:
Сообщение от shumbola Посмотреть сообщение
Цитата:
Сообщение от JH Посмотреть сообщение
Если бы стакан был один, то гарантированно можно было бы найти только со 100 попыток
Мне кажется достаточно было бы 51 попыток. Бросаем сразу с 50го этажа. Если не разбился поднимаемся вверх и до последнего. Если разбился спускаемся до первого.
Согласно условиям задачи.
Но есть решение с намного меньшим количеством попыток. Вот его и надо найти

Про 100 было сказано для случая, когда второго стакана нет.
Ответить 
Старый 14.07.2015 23:44   #4  
Аватар для shumbola
Оффлайн
Сообщений: 3,324
+ 337  890/588
– 3  31/25

Uzbekistan
Цитата:
Сообщение от JH Посмотреть сообщение
Цитата:
Сообщение от shumbola Посмотреть сообщение
Цитата:
Сообщение от JH Посмотреть сообщение
Если бы стакан был один, то гарантированно можно было бы найти только со 100 попыток
Мне кажется достаточно было бы 51 попыток. Бросаем сразу с 50го этажа. Если не разбился поднимаемся вверх и до последнего. Если разбился спускаемся до первого.
Согласно условиям задачи.
Но есть решение с намного меньшим количеством попыток. Вот его и надо найти

Про 100 было сказано для случая, когда второго стакана нет.
Я как раз про случай с одним стаканом говорил. Когда есть 2 стакана, еще не думал. :-)
__________________
404 Not Found
Ответить 
Старый 14.07.2015 23:48   #5  
Аватар для shumbola
Оффлайн
Сообщений: 3,324
+ 337  890/588
– 3  31/25

Uzbekistan
Цитата:
Сообщение от JH Посмотреть сообщение
два одинаковых стакана неустановленной прочности
Два одинаковых, но разных прочностей?
__________________
404 Not Found
Ответить 
Старый 14.07.2015 23:49   #6  
Known ID Group uParty Member Ultimate
Аватар для JH
Оффлайн
Сообщений: 10,876
+ 3,660  10,910/4,662
– 584  284/212

Uzbekistan
Цитата:
Сообщение от shumbola Посмотреть сообщение
Я как раз про случай с одним стаканом говорил. Когда есть 2 стакана, еще не думал. :-)
Если стакан только один, и при падении с 50 этажа он разбился - то вы уже не выясните искомый этаж (например, это 28-й), потому что уже нечем проверять.
Ответить 
2 "+" от:
Старый 14.07.2015 23:49   #7  
Known ID Group uParty Member Ultimate
Аватар для JH
Оффлайн
Сообщений: 10,876
+ 3,660  10,910/4,662
– 584  284/212

Uzbekistan
Цитата:
Сообщение от shumbola Посмотреть сообщение
Два одинаковых, но разных прочностей?
Одинаковой неустановленной прочности.
Ответить 
"+" от:
Реклама и уведомления
Старый 15.07.2015 00:24   #8  
Аватар для shumbola
Оффлайн
Сообщений: 3,324
+ 337  890/588
– 3  31/25

Uzbekistan
Кидаем с 25го.
Если разбился, кидаем второй с 1го по 24й.
Если не разбился, кидаем с 50го. Разбился, кидаем второй с 26го по 49й.
Не разбился, кидаем с 75го и т.д.
__________________
404 Not Found
Ответить 
Старый 15.07.2015 00:26   #9  
Known ID Group uParty Member Ultimate
Аватар для JH
Оффлайн
Сообщений: 10,876
+ 3,660  10,910/4,662
– 584  284/212

Uzbekistan
Цитата:
Сообщение от shumbola Посмотреть сообщение
Кидаем с 25го.
Если разбился, кидаем второй с 1го по 24й.
Если не разбился, кидаем с 50го. Разбился, кидаем второй с 26го по 49й.
Не разбился, кидаем с 75го и т.д.
В худшем случае он на 75-м разбился (это три попытки), плюс еще 24 попытки (с 51 по 74-й), итого 27 попыток.

Есть вариант с меньшим числом попыток.
Ответить 
Старый 15.07.2015 01:33   #10  
Real ID Group
Аватар для Rooslan Khayrov
Оффлайн
Google
software engineer
AKA:Y combinator
Сообщений: 418
+ 114  374/183
– 6  9/8

Switzerland
Придумал схему с 18 попытками максимум и 9,1 в среднем, но сходу доказать, что это оптимально, не получается.

Скрытый текст:
Первый стакан на i-й попытке бросаем с 10 * i этажа, второй соответственно с 10 * i + j на j-ой. Т.е. число попыток — сумма цифр, максимум соответственно достигается если критический этаж — 99-й.
__________________
Написанное здесь отражает только моё личное мнение и может не совпадать с позицией работодателя.

Последний раз редактировалось Rooslan Khayrov; 15.07.2015 в 01:37.
Ответить 
Ответить
Опции темы
Опции просмотра




Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd. Перевод: zCarot
Advertisement System V2.5 By Branden
OOO «Единый интегратор UZINFOCOM»


Новые 24 часа Кто на форуме Новички Поиск Кабинет Все прочитано Вверх