"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.

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

Главная | О проекте | Все задачи-1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C | Добавить задачу



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

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

Поиск на сайте





запомнить меня
Зарегистрироваться


Задачи

Логические
Математические
С подвохом
Переправа
Переливания и взвешивания
Даты
Физика вокруг
Последовательности
Честные и лжецы
Слова и буквы
Теорвер, комбинаторика
Геометрические
Вопросы на эрудицию
Стратегии
Шахматы
Задания на наблюдательность
требуется помощь
Чисто поржать
Детские с подковыркой
Спички
Детективные
Ребусы / Шарады
Программистам
Вопросы к обсуждению


Данетки


Текущие:

  Мой любимый грех (с)
  Математика в архитектуре
  Не сыпь мне соль на рану
  «Геометрическая»
  Высказывание Ломоносова
  Наверное, не про яблоки
  Комерция
  Везде градусы
  Вагончик тронется, вагончик тронется..
  Спасибо медикам и католикам))
  Специальная купюра
  Студенческая смекалка
  Эллипс vs Круг
  Современные технологии. Немецкий стандарт.
  Спортивная
  философская
  Про газету
  печатная монета
  Купюра евро
  Древние изобретения
  Биометрические паспорта
  Новый глава
  В далеком созвездии тау Кита... 8)))
  Огородное
  Средневековое строительство
  Жестокое наказание
  Их нравы - 4
  Европейский стандарт

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

  этот модный тандыр
  Из Что-Где-Когда
  Может ли такое быть?
  Что изображено?
  Да на тебе пахать надо!


Справочная



Признаки делимости
Площади фигур


Реклама






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



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

+ 3 -


Ответ





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





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


ответов: 22

< 1 2 >

не представился 2016-04-22 11:58:33 пишет:
Ааааа, он вообще ничего про зет не знает! Спасибо, что пояснили! теперь понятно!!!

не представился 2016-04-21 19:54:38 пишет:
Ну Z наверное, это подразумевается фамилия. Если они его не знают, так и скажут, что не знают....???? В чем проблема....???
   Админ: Нет, журналист не знает, кто из присутствующих столь широко известен. Задача - его найти. Еще, кстати, надо пояснить почему названное количество вопросов достаточно и минимально.

не представился 2016-04-21 15:54:58 пишет:
Просто спрашивать "Знаете ли Вы зет???". В худшем случае эн минус один вопросов и будет.
   Админ: Присутствующие не знают кого из них Вы называете Z.

KoKos 2016-04-20 21:37:37 пишет:
Хм? Как-то уровень сложности высоковат? N-1 вопрос и необходимо и достаточно. :) Меньше не выйдет, ибо отсеять одним вопросом можно только одного претендента. А достаточность доказывается существованием алгоритма. Первую жертву выбираем наугад. Спрашиваем его/ее про вторую жертву. Если ответ "знаю" - вторую вычеркиваем, продолжаем допрашивать первую. Если мы с первой попытки попали на Z , то накопив N-1 ответ "знаю" обретем в этом уверенность. Если нет, то на некоторой жертве мы получим ответ "не знаю" - вычеркиваем нашу текущую жертву и переходим к допросу новой, которой не знала текущая. Пойду смотреть, над чем головы ломают. 8))
   Админ:

Гидон 2016-04-20 17:04:38 пишет:
Ой, затупил, задав свой вопрос :( Ответа не требуется :)

K2 2016-04-20 16:11:48 пишет:
ПС: хе-хе - каким я оказывается был глупым и забавным два года назад-то - уже и забыл совсем об этой задаче :)))

K2 2016-04-20 16:06:51 пишет:
предположу что ЭН_минус_один вопрос, так как каждый вопрос убирает нам одну "цель", либо "знаю" - тогда "такой-то" не зет, либо "не_знаю" - тогда спрашиваемЫй не зет, ибо он знает всех. Остаётся только не повторяться - но это не так уж и сложно - можно обливать "выбывших" пуншем, и спрашивать только чистых о чистых :)
   Админ:

Гидон 2016-04-20 15:02:17 пишет:
Если всем надо задавать один и тот же вопрос, то к чему тогда в условии указано, что можно задавать одному человеку несколько вопросов? Какой смысл задавать один и тот же вопрос кому-либо несколько раз?

K2 2014-03-31 13:21:23 пишет:
ой, извиняюсь, наврал, не факториал - поменьше: (N-3) + (N-2) + (N-3) ... (N-N+2) - да, думаю что именно так - заканчиваем двойкой... на Этот раз хоть правильно?... %)
   Админ: есть более короткий путь

K2 2014-03-31 13:18:47 пишет:
У меня Почему-то получается эн-минус-три-факториал... чужие ответы пока не хочу смотреть - подожду результата :)

не представился 2014-03-30 09:07:28 пишет:
Известно: "в компании есть человек Z, он знает всех членов компании, но его не знает никто". 1. - Нам не известны свойства других членов компании. 2. - Не исключено, что некоторые не знают не только Z, но и ещё кого-то... задача НЕ РЕШАЕМА при таких условиях, т.к. "все правдивы" не есть "все знают".

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 пишет:
1

Вася Пупкин 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 вопрос.
Правда нужна предобработка - составление списков ;)
   Админ:

< 1 2 >

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

Комментарий:

Пожалуйста, введите символы с картинки:
(подтверждение не требуется для зарегистрированных пользователей)



 





Обсуждаем

  Задача Разрезанный треугольник:
http://lprobs.ru/img/yes.gif : [скрыто]
Гостевая книга:
не представился : Это было в 1913 году. Одиннадцатилетняя девочка, пансионерка Московской Ржевской гимназии очень прос...
Задача Гора.:
Xuzke : [скрыто]
Гостевая книга:
не представился : В школе все казалось правильным. Из математики следует физика, из физики следует химия, из химии сле...
R-2 : Ты решил: Ну, и наконец, то решение, которое тут видимо предполагается в идеале, я не буду говори...
Так, по старой памяти заглянул :) : R-2, условие неплохо бы конкретизировать. ;)) А то так вариантов может быть масса, хотя все обладают...
Задача 4 хода:
колд : [скрыто]
Задача Кот и мышка:
Дмитрий : [скрыто]
Задача Черная Жемчужина:
mskfirst : [скрыто]
Задача Квадратный торт:
не представился : [скрыто]
Задача Задача с ведрами: 9 и 4 = 6.:
ИносОйЧанбин : [скрыто]
Дкгк7 : [скрыто]
Задача Геометрическая 3:
не представился : [скрыто]
Алексей : [скрыто]
Гостевая книга:
R-2 : Дано: листочек бумаги и ручка. На листочке написаны три нуля. О О О Задача: «как из трёх нулей...



Реклама



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