Главная
Главная Полевая кухня клуба ЧуГуноК


Архив клуба ЧуГуноК
Текущее время: 01 мар 2024, 00:06

Часовой пояс: UTC + 2 часа




Начать новую тему Ответить на тему  [ Сообщений: 13 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Сдай экзамен
СообщениеДобавлено: 31 окт 2008, 15:28 
Не в сети
Администратор

Зарегистрирован: 15 сен 2012, 20:51
Сообщения: 0
Тест состоит из 30 вопросов, на каждый есть два варианта ответа (один верный, другой нет)
За одну попытку Витя отвечает на все вопросы, после чего ему сообщают, на сколько вопросов он ответил верно. Сможет ли Витя деймтвовать так, чтобы гарантированно узнать все верные ответы не позже, чем
а) после 29-й попытки (и ответить верно на все вопросы при 30-й попытке)
б) после 24-й попытки (и ответить верно на все вопросы при 25-й попытке)

(Изначально Витя не знает ни одного ответа, тест всегда один и тот же)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Сдай экзамен
СообщениеДобавлено: 31 окт 2008, 21:55 
Не в сети
Администратор

Зарегистрирован: 15 сен 2012, 20:51
Сообщения: 0
Решение от Златы

Quote ("Злата")
Смотри:
1111 1111 1111 1111 1111 1111 1111 11** - дает N0
1111 1111 1111 1110 0 - дает N1
1111 1000 0000 0001 1
1000 0111 1000 0001 1
0100 0100 0111 0001 0
0010 0010 0100 1100 1
0001 0001 0010 1010 0
0000 1000 1001 0110 0
Дописывать строки до конца - некогда. В каждом столбце должно быть 4 единицы.

По такому принципу создаешь 8 строк ответов (1- "да", 0-"нет").
Получаешь 8 отметок.
Ой, кажется строк 8-мало, надо 9. Плюс - "первый вариант" с одними "да".

На каждый вопрос у тебя получилось 4 раза "да".
Теперь - складываешь все отметки по тем строкам, где ты отвечала "да" на 1-й вопрос. И делишь на 4.
Смотришь - больше или меньше получилась отметка, чем N0
Если больше - надо на этот вопрос отвечать "да".
Аналогично - с остальными вопросами.
Не уверена 100%, но в итоге - после 9 раз - 10-й (сделанный таким способом) получается верным.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Сдай экзамен
СообщениеДобавлено: 01 ноя 2008, 07:20 
Не в сети
Администратор

Зарегистрирован: 15 сен 2012, 20:51
Сообщения: 0
вот такое решение:
1. 1-я попытка ДА на все вопросы. Получаем К очков
2. На 1,2 отвечаем НЕТ, на остальные ДА. ПОлучаем К-2, К, или К+2 очков
3. В случае К-2, или К+2 мы однозначно определяем ответы 1 и 2. Далее, меняя на НЕТ по одному из вопросов, мы определяем его. И к 29-й попытке у нас уже определены все вопросы. С 30-й сдаём экзамен
4. В случае К (один был верный, другой нет), мы возвращаем предыдущий (первый) в ДА, а в НЕТ ставим два следующих (2 и 3). По тому же алгоритму, если получим К-2, или К+2, определим эти вопросы, а далее по цепочке предыдущие, если получаем К, повторяем алгоритм.
5. Действие должно закончиться, как только рядом окажутся два последовательных вопроса с ответами ДА или НЕТ. Что обязательно должно случиться при К не равно 15.
6. Пусть К=15 (первая попытка)
7. Отвечаем НЕТ на первый вопрос и определяем его. - 2-я попытка
8. Отвечаем НЕТ на 2,3 вопросы - 3-я попытка
,,,,,,,,,,,,,,,,
9. отвечаем НЕТ на 28, 29 вопросы - 29 попытка. Получаем К очков
10. Однозначно определяем чередующуюся последовательность ответов по первому вопросу


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Сдай экзамен
СообщениеДобавлено: 01 ноя 2008, 07:25 
Не в сети
Аватара пользователя

Зарегистрирован: 06 янв 2008, 23:16
Сообщения: 0
Ну самый тупой метод дает 30 попыток и гарантированно верный ответ на 31-й

_________________
А кто сказал, что я прав?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Сдай экзамен
СообщениеДобавлено: 01 ноя 2008, 07:47 
Не в сети
Аватара пользователя

Зарегистрирован: 06 янв 2008, 23:16
Сообщения: 0
Алг, при К=15 не проходит ИМХО Для примера две исходных последовательности из а=4 вопросов
1010 и 0101
1111 = 2 и 2
0011 = 2 и 2
1001 = 2 и 2
итого выяснили, что ответы чередуются, но не понятно, что на первом месте нужен еще один 4-й вопрос.

_________________
А кто сказал, что я прав?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Сдай экзамен
СообщениеДобавлено: 01 ноя 2008, 07:54 
Не в сети
Администратор

Зарегистрирован: 15 сен 2012, 20:51
Сообщения: 0
так при к=2 другой алгоритм предлагала

1010 и 0101


1111
0111
1001
обнаружили чередующуюся послед. и знаем первый элемент
однозначный ответ с 4-й попытки


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Сдай экзамен
СообщениеДобавлено: 01 ноя 2008, 08:20 
Не в сети
Аватара пользователя

Зарегистрирован: 06 янв 2008, 23:16
Сообщения: 0
Пардон, ошибся не заметил перехода ко второму алгоритму
110100 101010
111111 = 3 и 3
011111 = 2 и 2
100111 = 3 и 3
110011 = 3 и 3
111001 = 3 и 3
Похоже, что в случае удвоения первых и последних еще по вопросу надо

_________________
А кто сказал, что я прав?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Сдай экзамен
СообщениеДобавлено: 01 ноя 2008, 08:35 
Не в сети
Аватара пользователя

Зарегистрирован: 06 янв 2008, 23:16
Сообщения: 0
А вообще-то теория говорит, что что бы получить 1 бит информации надо задать 1 бинарный вопрос. В условии я пока не вижу скрытой информации в процедуре теста, а если ее там нет, то увы sad

_________________
А кто сказал, что я прав?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Сдай экзамен
СообщениеДобавлено: 01 ноя 2008, 08:43 
Не в сети
Администратор

Зарегистрирован: 15 сен 2012, 20:51
Сообщения: 0
101010 ок
110100 ты прав.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Сдай экзамен
СообщениеДобавлено: 01 ноя 2008, 09:06 
Не в сети

Зарегистрирован: 09 янв 2008, 09:32
Сообщения: 0
Quote (basil0)
А вообще-то теория говорит, что что бы получить 1 бит информации надо задать 1 бинарный вопрос. В условии я пока не вижу скрытой информации в процедуре теста,

Мы получаем каждый раз НЕ бинарную информацию, а число от 0 до 30.
Потенциально - 5 бит.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 2 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB