2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 посчитать кол-во битов для написания дня рождения
Сообщение29.10.2011, 22:26 
Задача:

Пафнутий и Иван забыли когда в этом году надо отпраздновать день рожденья их друга Афанасия. Однако, Иван помнит число, а Пафнутий — месяц рождения друга. Задумались об этом 1 числа N-ого месяца 2011 года и точно знают, что в этом году они еще не праздновали.
Задача. Какое минимальное количество битов информации им нужно переслать друг другу, чтобы обоим восстановить день рожденья Афанасия?

Потоки. Входной поток содержит одно натуральное число N≤12. Выходной поток должен содержать одно целое число.

Пример
Входной поток:
1
Выходной поток:
9

Смысла вообще не понимаю.
Даже не представляю, почему 9 бит(

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение29.10.2011, 22:36 
Иван должен сообщить Пафнутию число в месяце. В каком диапазоне может меняться это значение и сколько битов надо на его передачу?

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение29.10.2011, 22:52 
Maslov в сообщении #497221 писал(а):
Иван должен сообщить Пафнутию число в месяце. В каком диапазоне может меняться это значение и сколько битов надо на его передачу?


Ну как я думаю:
если 1 числа N месяца, то мин. кол-во байт Иван -> Пафнутий - 2(ну после 1 идёт 2 день, я думаю, что это - минимальный день и затрачивается мин-е кол-во бит)
В примере берётся 1, 1 можно использовать только один бит
т.е 1+2=3 бита
откуда 9? Для меня загадка

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение29.10.2011, 23:00 
Аватара пользователя
Откуда 9 я понимаю. Но этот ответ не правильный, правильный ответ 2 бита.

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение29.10.2011, 23:01 
Pavia в сообщении #497234 писал(а):
Откуда 9 я понимаю. Но задача не правильная правильный ответ 2 бита.


Поподробней

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение29.10.2011, 23:16 
Hi4ko,
допустим, день рождения у Афанасия 23-го ноября, а дело происходит 1-го января, как в Вашем примере.
Таким образом, Иван должен сообщить Пафнутию информацию, позволяющую тому выбрать одно конкретное значение из 31 варианта. Вы утверждаете, что для этого достаточно двух бит.

Предположим, Вы Иван, я Пафнутий. Пересылайте.

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение29.10.2011, 23:20 
Аватара пользователя
Два бита вот откуда
Возьмем месяц, у нас в месяце максимум 31 день.
Номер каждого дня мы можем закодировать числом бит.
первый день 1
второй день 11
третий день 111
четвёртый день 1111
и так далее

Для месяцев, аналогично но счёт идет от текущего месяца (N).
N-ный месяц 1
N+1 месяц 11
и так далее
Отсюда минимальное будет если у него первого числа N-ого месяца итого
1 бит перешлёт Иван -> Пафнутию и 1бит Пафнутий -> Ивану
Итого 2 бита.

Что касается 9 бит, то видимо составитель не учёл что информацию можно кодировать по разному.
И видимо решил её кодировать в двоичном формате как показано ниже.
1 день 00000
2 день 00001
3 день 00010
и так далее
Откуда имеем для кодирования тридцати одного дня надо 5 бит $= \left\lceil log_2{(31)} \right\rceil$.

Что касается месяцев. Для кодирования 12 месяцев в таком формате надо 4 бита.
Итого 4+5=9
У нас в задаче на перёд известен текущий месяц, то тут можно сократить число бит, если вычесть
К примеру если начальный N=5 то остаётся всего 12-5=7 месяцев, а их уже можно кодировать 3 битами.

Напоминаю правильный ответ будет 2 бита.

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение29.10.2011, 23:26 
Pavia в сообщении #497245 писал(а):
Напоминаю правильный ответ будет 2 бита.
Следуя Вашей логике, это тоже неправильный ответ. Правильный ответ будет 0 бит. Вполне можно договориться, что 1-е число и N-й месяц вообще не передаются.

Но задача не об этом.

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение29.10.2011, 23:30 
Аватара пользователя
Maslov в сообщении #497247 писал(а):
Pavia в сообщении #497245 писал(а):
Напоминаю правильный ответ будет 2 бита.
Следуя Вашей логике, это тоже неправильный ответ. Правильный ответ будет 0 бит. Вполне можно договориться, что 1-е число и N-й месяц вообще не передаются.

Но задача не об этом.

Договориться можно, то тогда это будет противоречить определению информации по Шенону, которая является обще принятой.

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение29.10.2011, 23:33 
Есть вариант, что для каждого месяца 9 бит?

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение30.10.2011, 00:08 
Hi4ko в сообщении #497250 писал(а):
Есть вариант, что для каждого месяца 9 бит?
Почему 9?
Скучно с Вами: на вопросы не отвечаете, вместо этого занимаетесь гаданием.

Pavia в сообщении #497249 писал(а):
Договориться можно, то тогда это будет противоречить определению информации по Шенону, которая является обще принятой.
В чем Вы видите противоречие между определением информации по Шенному и сообщением нулевой длины? Это же чисто способ кодирования.

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение30.10.2011, 00:26 
Maslov в сообщении #497243 писал(а):
Hi4ko,
допустим, день рождения у Афанасия 23-го ноября, а дело происходит 1-го января, как в Вашем примере.
Таким образом, Иван должен сообщить Пафнутию информацию, позволяющую тому выбрать одно конкретное значение из 31 варианта. Вы утверждаете, что для этого достаточно двух бит.

Предположим, Вы Иван, я Пафнутий. Пересылайте.

если вы про этот вопрос,то:
Я вам должен переслать любое значение от 1 до 31. Это 5 бит. Но минимальное значение-то 2 бита(потому что мин-е значение дня - 2, передать можно 2 битами(чисто моя логика)).
По-другому я не знаю как.

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение30.10.2011, 00:45 
Hi4ko в сообщении #497259 писал(а):
Я вам должен переслать любое значение от 1 до 31. Это 5 бит.
Судя по приведенному примеру, автор задачи имел в виду именно такой способ.

Теперь осталось только с месяцем разобраться. Хотя разбираться особо нечего, потому что Pavia Вам уже готовое решение написал. Осталось только запрограммировать :)

Hi4ko в сообщении #497259 писал(а):
потому что мин-е значение дня - 2
Загадочное утверждение. А что, первые числа месяца отменили?

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение30.10.2011, 00:50 
Аватара пользователя
Цитата:
В чем Вы видите противоречие между определением информации по Шенному и сообщением нулевой длины?

Перечитал Шенона. Да Я ошибся. Тогда и правда 0 получается. Шенон требовал хотя бы одного сообщения, но не говорил про его длину. Правда у него сообщение 0 длины как-то не упомянуты, он больше писал о том что информация должно быть сохранена (store), передана.

 
 
 
 Re: посчитать кол-во битов для написания дня рождения
Сообщение30.10.2011, 00:51 
Maslov в сообщении #497262 писал(а):
Hi4ko в сообщении #497259 писал(а):
Я вам должен переслать любое значение от 1 до 31. Это 5 бит.
Судя по приведенному примеру, автор задачи имел в виду именно такой способ.

Теперь осталось только с месяцем разобраться. Хотя разбираться особо нечего, потому что Pavia Вам уже готовое решение написал. Осталось только запрограммировать :)

Hi4ko в сообщении #497259 писал(а):
потому что мин-е значение дня - 2
Загадочное утверждение. А что, первые числа месяца отменили?


Нет, видимо я с условием не до конца разобрался :)
Спасибо вам)

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group