Рейтинг темы:
  • Текущий рейтинг 5.00/5

Автор Тема: Задачка на энтропию  (Прочитано 2698 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Добрая КобраАвтор темы

  • Почетный форумчанин
  • *
  • Сообщений: 4005
  • Пол: Женский
  • На форуме с: 9 Апреля 2011
Задачка на энтропию
« : 7 Июня 2012, 02:40:24 »
Помогите  :'( отгадать загаданное число от 1 до 200, используя пять вопросов. Варианты ответа отвечающего только: Да, нет, не знаю.
Существует три варианта ответа, один из них считается немножко жульническим (но я не знаю ни одного).

Чтобы было понятнее: можно использовать  вопросы типа : Это число находится в промежутке от одного до ста?
И ход рассуждений напишите, пожалуйста :rose:

Оффлайн ruslik

  • Почетный форумчанин
  • Сообщений: 2250
  • Пол: Мужской
  • На форуме с: 11 Апреля 2011
Задачка на энтропию
« Ответ #1 : 7 Июня 2012, 03:22:38 »
Как можно что-то отгадать если на все 5 вопросов отвечающий даст ответ: не знаю ? Чушь какая-то :don-t_mention: Вы точно поняли условие ?
Знаю все английские слова на букву 'X'

AlexK

  • Гость
Задачка на энтропию
« Ответ #2 : 7 Июня 2012, 05:34:11 »
совсем не чушь. очевидно подразумевается, что отвечающий всегда говорит правду.

AlexK

  • Гость
Задачка на энтропию
« Ответ #3 : 7 Июня 2012, 05:42:48 »
похоже я понимаю в каком направлении надо двигаться :)

стандартное решение подобной задачи это бисекция i.e. деление набора чисел на 2. i.e. первый вопрос: это число больше 100? если нет, то след вопрос: это число больше 50? и т.д.
к сожалению таким способом угадать число от 1 до 200 за 5 попыток нельзя. Но это считая, что у отвечающего есть только два варианта ответа "ДА" и "НЕТ".
так что, чтобы решить надо использовать вариант "не знаю".

Для этого можно использовать похожий трюк, но с разбивкой чисел на три части.  отвечающему можно задать такой вопрос: Если число меньше или равно 66 отвечай "ДА", если число между 67 и 133 отвечай "ДА" если больше 133 отвечай "не знаю".

и так далее, каждый раз деля множество чисел на три.   В таком случае 5 попыток будет достаточно.
« Последнее редактирование: 7 Июня 2012, 07:54:14 от AlexK »

Оффлайн ruslik

  • Почетный форумчанин
  • Сообщений: 2250
  • Пол: Мужской
  • На форуме с: 11 Апреля 2011
Задачка на энтропию
« Ответ #4 : 7 Июня 2012, 11:00:15 »
совсем не чушь. очевидно подразумевается, что отвечающий всегда говорит правду.

Серьёзно ? Тоесть отвечающий может знать число, но не знать к примеру в каком интервале оно находится ? Вычурно :drink: Вы наверно имеете ввиду что не знаю можно использовать чтобы не говориь да или нет.

Я склоняюсь к тому что Добрая Кобра недостаточно ясно поняла условия задачи. И что теперь смысл состоит в самостоятельном додумывании и решении ? Мне как-то недосуг :don-t_mention: И вообще при чём тут энтропия ? Добрая Кобра хоть догадывается о значении термина ?

Если следовать Вашей догадке, AlexK, то полный интервал должен быть 66*3=198. Но даже в этом случае на 5-ом шаге Вам придётся выбрать между 2-мя числами, т.е. отгадка не гарантирована :nea:

Оффлайн Добрая КобраАвтор темы

  • Почетный форумчанин
  • *
  • Сообщений: 4005
  • Пол: Женский
  • На форуме с: 9 Апреля 2011
Задачка на энтропию
« Ответ #5 : 7 Июня 2012, 12:16:39 »
ruslik,
Цитировать
Я склоняюсь к тому что Добрая Кобра недостаточно ясно поняла условия задачи. И что теперь смысл состоит в самостоятельном додумывании и решении ? Мне как-то недосуг :don-t_mention: И вообще при чём тут энтропия ? Добрая Кобра хоть догадывается о значении термина ?
Догадываюсь, догадываюсь  и о значении термина и о том, что Вы решить задачку не можете ;) Условия я не понимаю, это правда, но  передала я их точно, слово  в слово.
Цитировать
то полный интервал должен быть 66*3=198. Но даже в этом случае на 5-ом шаге Вам придётся выбрать между 2-мя числами, т.е. отгадка не гарантирована
А в условии оговаривается, что вариантов ответа три. Один нашелся, СПАСИБО :rose: Вазу под цветочек не подарю.
AlexK, алгоритм  - класс, ОГРОМНОЕ спасибо  :rose:

Оффлайн sergsl

  • Дебютант
  • Сообщений: 61
  • Пол: Мужской
  • На форуме с: 9 Апреля 2011
Задачка на энтропию
« Ответ #6 : 7 Июня 2012, 12:52:08 »
можно составлять сложные вопросы составляющие взаимоисключающую систему. Что-то типа: " это четное число заканчивающееся на 2 ?" и так далее в зависимости от полученного ответа

Оффлайн ruslik

  • Почетный форумчанин
  • Сообщений: 2250
  • Пол: Мужской
  • На форуме с: 11 Апреля 2011
Задачка на энтропию
« Ответ #7 : 7 Июня 2012, 13:15:18 »
Ну не решил, Добрая Кобра, согласен :ah: AlexK решил в собственном варианте постaновки задачи :yes: Молодец :drink:

Оффлайн Добрая КобраАвтор темы

  • Почетный форумчанин
  • *
  • Сообщений: 4005
  • Пол: Женский
  • На форуме с: 9 Апреля 2011
Задачка на энтропию
« Ответ #8 : 7 Июня 2012, 14:56:35 »
sergsl,
Цитировать
можно составлять сложные вопросы составляющие взаимоисключающую систему. Что-то типа: " это четное число заканчивающееся на 2 ?" и так далее в зависимости от полученного ответа
Замечательная идея, спасибо :rose:

AlexK

  • Гость
Re: Задачка на энтропию
« Ответ #9 : 7 Июня 2012, 18:28:32 »
Если следовать Вашей догадке, AlexK, то полный интервал должен быть 66*3=198. Но даже в этом случае на 5-ом шаге Вам придётся выбрать между 2-мя числами, т.е. отгадка не гарантирована :nea:

отгадка гарантирована т.к. 3^5 > 200.

Оффлайн ruslik

  • Почетный форумчанин
  • Сообщений: 2250
  • Пол: Мужской
  • На форуме с: 11 Апреля 2011
Re: Задачка на энтропию
« Ответ #10 : 8 Июня 2012, 13:58:20 »
отгадка гарантирована т.к. 3^5 > 200.

Признаюсь я не понял при чём тут 3^5 и возможно я не понял Вашего решения. Вот что я понял. Вы делаете разбивки каждый раз на три интервала:

шаг 1    1-66     67-132    133-200  в третьем интервале не 66 цифр, а 68, но давайте брать всегда первый.
шаг 2    1-22    23-44        45-66
шаг 3    1-7        8-14        15-22  третий интервал содержит не 7 цифр, а 8, ну Бог с ним берём первый.
шаг 4    1-2        3-4            5-7    третий интервал содержит не 2 цифры, а 3, ну Бог с ним берём снова первый.

Итак на 5-ом шаге (последнем как я понял) Вам предлагается выбрать между цифрой скажем 1 и 2. Как я могу это угадать на 100 % ?

Что в моём рассуждении не верно ? Всё ? :lol: :lol: :lol:

AlexK

  • Гость
Задачка на энтропию
« Ответ #11 : 8 Июня 2012, 20:21:17 »
замечаний два

1) на первом шаге непонятно зачем разбивать на 66, 66 и 68 чисел. проще разбить на 66, 67 и 67
2) в худшем случае на конечном шаге остается даже не 2, а 3 цифры и один (5й) вопрос.
Но никаких проблем здесь не вижу, используется тот же трюк. Честно говоря, удивлен что вы тут не смогли догадаться.

А решение на конечном шаге такое, если осталось числа a, b, и c, то задается вопрос "Если это число a отвечай "Да", если  b то "Нет", если c то "Не знаю".

Оффлайн ruslik

  • Почетный форумчанин
  • Сообщений: 2250
  • Пол: Мужской
  • На форуме с: 11 Апреля 2011
Задачка на энтропию
« Ответ #12 : 8 Июня 2012, 21:40:34 »
Ага, ясно. Вообще довольно дебильная задача. Ну да и хрен с ней :don-t_mention:

AlexK

  • Гость
Задачка на энтропию
« Ответ #13 : 8 Июня 2012, 22:18:01 »
задачка хорошая. стандартная задача предполагает ответ "да" или "нет". Здесь есть третий вариант ответа, но ответ "не знаю" сбивает с толку т.к. на первый взгляд кажется, что не несет никакой информации. 

Оффлайн дядя Сережа

  • Ветеран форума
  • *
  • Сообщений: 5923
  • Пол: Мужской
  • На форуме с: 4 Апреля 2011
Задачка на энтропию
« Ответ #14 : 9 Июня 2012, 23:00:01 »
1) на первом шаге непонятно зачем разбивать на 66, 66 и 68 чисел. проще разбить на 66, 67 и 67
Разбивать можно на любые интервалы и любым способом (и решений тут не 5, а фигова туча, если за одтельное решение принимать каждое новое разбиение множества 1..200), важно, чтобы в результате получалось при примерно одинаковые множества. И тогда имеем максимальное покрытие: 3 в пятой степени.

Но есть одна непонятка: все решения заставляют отвечать "не знаю", хотя отвечающий четко знает. Если настаивать именно на незнании, тогда все становится гораздо менее очевидным.

Оффлайн ruslik

  • Почетный форумчанин
  • Сообщений: 2250
  • Пол: Мужской
  • На форуме с: 11 Апреля 2011
Задачка на энтропию
« Ответ #15 : 9 Июня 2012, 23:12:43 »
Ну я так понимаю, дядя Сережа, это не не знаю, а третье квантовое состояние квантового компа. Тоесть ни 1 ни 0, а не знаю. Если у компа будет 200 квантовых состояний тогда ответ может быть получен за один шаг. А реально даже меньше чем за один шаг если брать комбинации состояний. В смысле потребуется меньше чем 200 состояний.

AlexK

  • Гость
Re: Задачка на энтропию
« Ответ #16 : 10 Июня 2012, 10:02:22 »
Разбивать можно на любые интервалы и любым способом

серьезно? ок, если можно на любые то делаю так:
1 шаг: {1}, {2}, {>2}, допустим число в 3м интервале (>2), тогда на 2м шаге разбиваю этот интервал на
{3}, {4}, {>4}, и т.д. в итоге на пятом шаге может оказаться что число в интервале { от 9 до 200}.

И как за 1 оставшийся вопрос узнать какое из чисел от 9 до 200 было загадано?

Оффлайн ruslik

  • Почетный форумчанин
  • Сообщений: 2250
  • Пол: Мужской
  • На форуме с: 11 Апреля 2011
Задачка на энтропию
« Ответ #17 : 10 Июня 2012, 11:12:59 »
Разбивать можно на любые интервалы и любым способом (и решений тут не 5, а фигова туча, если за одтельное решение принимать каждое новое разбиение множества 1..200), важно, чтобы в результате получалось при примерно одинаковые множества. И тогда имеем максимальное покрытие: 3 в пятой степени.

Но есть одна непонятка: все решения заставляют отвечать "не знаю", хотя отвечающий четко знает. Если настаивать именно на незнании, тогда все становится гораздо менее очевидным.

AlexK, тут опечатка, имеется ввиду три, а не при.

Короче дядя Сережа имел ввиду что такие разбиения как:

(1-20;40-60;80-106)   (21-39;61-79;107-132)   (133-200) это суть эквиваленты решаемые таким же способом и гарантирующие ответ за 5 шагов. Таких разбиений на подмножества действительно дофига что он, видимо, и имел ввиду :yes:

Короче разбиение идёт не на 3 непрерывных интервала, а на три группы произвольным образом сконструированных подмножества с одним лишь условием что суммарное число элементов в них должно было одинаковым насколько это возможно в случае 200 элементов (на первом шаге; на других соответственно ALL/3), к примеру 66,67,67.

AlexK

  • Гость
Задачка на энтропию
« Ответ #18 : 10 Июня 2012, 12:39:48 »
ок. понятно!

Оффлайн дядя Сережа

  • Ветеран форума
  • *
  • Сообщений: 5923
  • Пол: Мужской
  • На форуме с: 4 Апреля 2011
Задачка на энтропию
« Ответ #19 : 10 Июня 2012, 15:57:07 »
AlexK, извиняюсь за неточную формулировку. Точная: разбивать можно на любые множества. Интервалы тут совершенно ни при чем.

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

Оффлайн Добрая КобраАвтор темы

  • Почетный форумчанин
  • *
  • Сообщений: 4005
  • Пол: Женский
  • На форуме с: 9 Апреля 2011
Задачка на энтропию
« Ответ #20 : 10 Июня 2012, 16:51:12 »
дядя Сережа,
Цитировать
Точная: разбивать можно на любые множества.
Пожалуйста, не сочти за труд показать на примере :rose:

Например, с цифрой 36.

Оффлайн ruslik

  • Почетный форумчанин
  • Сообщений: 2250
  • Пол: Мужской
  • На форуме с: 11 Апреля 2011
Задачка на энтропию
« Ответ #21 : 10 Июня 2012, 18:14:13 »
дядя Сережа, я имел ввиду что в принципе квантовый комп может решать такое с использованием меньшего числа логик. Да не важно, я в этом в общем не спец. Показалось просто.

Оффлайн дядя Сережа

  • Ветеран форума
  • *
  • Сообщений: 5923
  • Пол: Мужской
  • На форуме с: 4 Апреля 2011
Задачка на энтропию
« Ответ #22 : 11 Июня 2012, 21:01:01 »
Добрая Кобра, не понял, а при чем тут 36?

Оффлайн Кот Учёный

  • Помощник
  • Ветеран форума
  • *
  • Сообщений: 5249
  • Пол: Женский
  • Не белая, но пушистая.
  • На форуме с: 17 Марта 2011
Re: Задачка на энтропию
« Ответ #23 : 11 Июня 2012, 21:18:50 »
Добрая Кобра, В смысле, если ты загадала цифру 36?
Давай попробуем. Я пробовала на бумажке вчера названный тут троичным метод.

1) от 1 до 66 - да     от 67 до 133 - нет     от 134 до 200 - не знаю.
Ответ - да.

2) от 1 до 22 - да     от 23 до 44 - нет     от 45 до 66 - не знаю.
Ответ - нет.

3) от 23 до 30 - да     от 31 до 37 - нет     от 38 до 44 - не знаю.
Ответ - нет.

4) от 31 до 33 - да     от 34 до 36 - нет     от 37 - не знаю.
Ответ - нет.

5) 34 - да        35 - нет         36 - не знаю.
Ответ - не знаю.


Все, пять шагов и ответ ты вычисляешь просто.
Молодая, красивая, умная, сексуальная. Готовлю отлично. Голова не болит. Никого не ищу, - просто хвастаюсь!  :angel: :angel: :angel:

Оффлайн дядя Сережа

  • Ветеран форума
  • *
  • Сообщений: 5923
  • Пол: Мужской
  • На форуме с: 4 Апреля 2011
Re: Задачка на энтропию
« Ответ #24 : 11 Июня 2012, 21:36:58 »
Кот Учёный, а у меня квантовый компьютер (по руслику) и он выдает правильный ответ за один шаг:

1) от 1 до 35 - нет, 36 - да, от 37 до 200 - не знаю. Ответ: да.
Все, задача решена  :dirol:

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