Логические задачи : Поиск неизвестного

	"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.
Задачи на логику и сообразительность
Главная \| О проекте \| Все задачи-1, 2, 3, 4, 5, 6, 7, 8 \| Добавить задачу

О сайте
Гостевая книга
ЧаВо

Пользователи
RSS

Задачи

Переливания и взвешивания

Задания на наблюдательность

требуется помощь

Чисто поржать

Данетки

Текущие:

  Неожиданный труп 8)
  открытый урок
  ДаНетка с хорошим концом
  Три мертвеца (для разнообразия 8)))
  Загадка от Леонардо да Винчи
  Дом
  Толстяк
  данетка - спасительная
  данетка - теплая
  данетка - холодная
  Жалюзи

Разгаданные недавно:

  Убийца

Справочная

Признаки делимости

Реклама

задача: Поиск неизвестного

В компанию из N человек пришел журналист. Ему известно, что в этой компании есть человек Z, который знает всех остальных членов компании, но его не знает никто. Журналист может к каждому члену компании обратиться с вопросом: "Знаете ли вы такого-то?" Найдите наименьшее количество вопросов, достаточное для того, чтобы наверняка найти Z. (Все отвечают на вопросы правдиво. Одному человеку можно задавать несколько вопросов.)

Ответ

Решение задачи

Ваши ответы на задачу

ответов: 11

Jeka*T 2012-04-15 09:16:47 пишет:

"знаете ли вы всех на этом корабле? " В наихуд. Сл. вы опросите (n-1)людей.значит n-1 вопросов

Наталья Стрекаловская 2012-03-28 09:06:10 пишет:

0 вопросов. Ведь можно просто сказать:"Назовите тех людей, которых Вы знаете." А это не является вопросом.:-)

Админ: нееееее

Дмитрий 2012-02-10 19:23:31 пишет:

если этот вопрос менять нельзя, то в худшем случае, для определения, "наверняка", Z вычисляется n - 1 количеством вопросов

Админ: надо обосновать

Дмитрий 2012-02-10 19:20:26 пишет:

Можно уточнение Вопрос менять нельзя?

Админ: нельзя

Дмитрий 2012-02-10 19:19:29 пишет:

возможно но, не наверняка

Дмитрий 2012-02-10 19:18:31 пишет:

Вася Пупкин 2011-08-16 20:14:47 пишет:

Админ, означает ли незачет решения мне и Алексею(или, вернее, в хронологическом порядке -- Алексею и мне) -- что Вы знаете решение оптимальнее, чем за N-1?

Админ: Уже зачтено. Просто, мне надо было подумать :)

Вася Пупкин 2011-08-15 03:18:37 пишет:

Пронумеруем чуваков. Назначим первого кандидатом в Z, и начнем опрос по следующему алгоритму:участника номер К спрашиваем, знает ли он К+1, K+2 и т.д до первого отрицательного ответа. Все, о ком был дал положительный ответ -- не Z. Если мы дошли до конца списка, а отрицательных ответов не получили, то опрашиваемый и есть Z. На первом же отрицательном ответе мы понимаем, что опрашиваемый не есть Z, a тот, относительно которого был дан отрицательный ответ, становится новым кандидатом в Z, и мы начинаем опрашивать его обо всех, следующих за ним по номеру(все идущие перед ним -- не Z, в этом мы уже убедились, поскольку либо их кто-то знает, либо они кого-то не знают). Если таковых нет -- он и есть Z. Итого, надо задать N-1 вопрос(о каждом из участников, кроме первого).

Админ:

Алексей 2011-08-14 20:24:51 пишет:

Составим два списка - "белый" и "черный". Сначала "белый" содержит всех сотрудников а "черный" пуст. Спрашиваем у первого из "белого" списка про каждого другого из "белого"списка. Те, кого он знает, точно не являются Зэтом, заносим их в "черный список". Как только обнаружили, что он не знает хотя бы кого-нибудь, процедуру прекращаем и заносим ответчика самого в "черный список". Если же в "белом" списке никого не осталось - ответчик и есть наш Зэт. Если он не Зэт, то подходим к любому из "белого списка" и повторяем процедуру опроса. Тот, на ком "белый" список "закончится" и есть искомый сотрудник. Для того, что бы перевести сотрудника из "белого" списка в "черный" нужен всего один вопрос. Итого нам нужно задать всего лишь N-1 вопрос. Правда нужна предобработка - составление списков ;)

Админ:

344 2011-08-14 20:04:07 пишет:

отпишитесь пожалуйста насчет моего решения

Админ: см. ниже

344 2011-08-11 20:13:09 пишет:

оптимальное количество вопросов сказать не могу, могу рассказать стратегию как вычислить: пронумеруем человек и начиная с первого будем спрашивать знает ли он следующего а последнего спросим знает ли он первого(задали N вопросов) далее ищем тех кого не знает предыдущий но он знает следующего (искомый окажется в этой группе) повторяем тест опять выбирая тех кого не знают предыдущие и он знает остальных, по идее худший случай когда будет по 50% отсеиваний в каждом тесте значит на первом этаме это N вопросов на втором N/2 и так далее всего по идее 2N-2

Админ: найти так нужного человека, безусловно, можно. Но совсем не оптимальный вариант.

Добавьте комментарий:

Обсуждаем:

Реклама

© 2009 - 201х Логические задачи

Задачи на логику и сообразительность

Задачи

Данетки

Справочная

Реклама

задача: Поиск неизвестного

Ответ

Решение задачи

Ваши ответы на задачу

Обсуждаем:

Реклама