посчитать кол-во битов для написания дня рождения

[Hi4ko]

Задача:

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

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

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

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

[Maslov]

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

[Hi4ko]

Maslov в сообщении #497221 писал(а):

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

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

[Pavia]

Откуда 9 я понимаю. Но этот ответ не правильный, правильный ответ 2 бита.

[Hi4ko]

Pavia в сообщении #497234 писал(а):

Откуда 9 я понимаю. Но задача не правильная правильный ответ 2 бита.

Поподробней

[Maslov]

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

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

[Pavia]

Два бита вот откуда
Возьмем месяц, у нас в месяце максимум 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 бита.

[Maslov]

Pavia в сообщении #497245 писал(а):

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

Следуя Вашей логике, это тоже неправильный ответ. Правильный ответ будет 0 бит. Вполне можно договориться, что 1-е число и N-й месяц вообще не передаются.

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

[Pavia]

Maslov в сообщении #497247 писал(а):

Pavia в сообщении #497245 писал(а):

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

Следуя Вашей логике, это тоже неправильный ответ. Правильный ответ будет 0 бит. Вполне можно договориться, что 1-е число и N-й месяц вообще не передаются.

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

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

[Hi4ko]

Есть вариант, что для каждого месяца 9 бит?

[Maslov]

Hi4ko в сообщении #497250 писал(а):

Есть вариант, что для каждого месяца 9 бит?

Почему 9?
Скучно с Вами: на вопросы не отвечаете, вместо этого занимаетесь гаданием.

Pavia в сообщении #497249 писал(а):

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

В чем Вы видите противоречие между определением информации по Шенному и сообщением нулевой длины? Это же чисто способ кодирования.

[Hi4ko]

Maslov в сообщении #497243 писал(а):

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

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

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

[Maslov]

Hi4ko в сообщении #497259 писал(а):

Я вам должен переслать любое значение от 1 до 31. Это 5 бит.

Судя по приведенному примеру, автор задачи имел в виду именно такой способ.

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

Hi4ko в сообщении #497259 писал(а):

потому что мин-е значение дня - 2

Загадочное утверждение. А что, первые числа месяца отменили?

[Pavia]

Цитата:

В чем Вы видите противоречие между определением информации по Шенному и сообщением нулевой длины?

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

[Hi4ko]

Maslov в сообщении #497262 писал(а):

Hi4ko в сообщении #497259 писал(а):

Я вам должен переслать любое значение от 1 до 31. Это 5 бит.

Судя по приведенному примеру, автор задачи имел в виду именно такой способ.

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

Hi4ko в сообщении #497259 писал(а):

потому что мин-е значение дня - 2

Загадочное утверждение. А что, первые числа месяца отменили?

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