На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение
постоянный участник


Сообщение: 355
ссылка на сообщение  Отправлено: 03.12.18 20:42. Заголовок: Ошибка в условии?


Задача:
Для обозначения артикулов товаров в интернет-магазине используются последовательности из N символов.
Известно, что символы берутся из алфавита мощностью в 12 символов.
Петя решил сохранять в памяти артикул следующим образом – записывать подряд независимо код каждого символа артикула, используя для этого минимальное, одинаковое для кодов всех символов количество бит.
Вася решил использовать другой способ – записывать в память код каждого артикула, используя для этого минимальное, одинаковое для кодов всех артикулов количество бит.
Известно, что Вася тратит на запись кода одного артикула на 5 бит меньше, чем Петя. При каком минимальном N это возможно? В ответе укажите целое число.

Решение:

Петя:
12<24
1 символ - 4 бита
на N символов 4N бит

Вася:
на каждом из N мест одна из 12 букв - всего 12N вариантов артикула
12N = 22N * 3N < 22N * 4N = 24N
1 артикул - 4N бит

4N < 4N на 5 бит ???
или я что-то не так делаю?

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 3 [только новые]


Администратор




Сообщение: 1761
ссылка на сообщение  Отправлено: 03.12.18 23:36. Заголовок: oval пишет: 4N <..


oval пишет:
 цитата:
4N < 4N на 5 бит ??? или я что-то не так делаю?

Интересная задачка. Очевидно, что подход Пети когда-то даст преимущество. Поэтому предположение о некорректности условия ошибочно.
Вы взяли слишком жёсткую верхнюю оценку
 цитата:
22N * 3N < 22N * 4N

На самом деле так:
1) Петя использует количество битов, равное K = ceil(log2(12N)), где функция ceil(x) выполняет округление вверх к ближайшему целому
2) условие ceil(log2(12N)) <= 4*N - 5
3) преобразуем, используя свойств логарифма:
ceil(log2(12N)) = ceil(N*log2(12)) = ceil(N*(2 + log2(3)))= 2*N + ceil(N*log2(3))
4) сравниваем
2*N + N*ceil(log2(3)) <= 4*N - 5
ceil(N*log2(3)) <= 2*N - 5
или
ceil(log2(3N)) <= 2*N - 5
или (спасибо oval)
3N <= 22*N-5
5) минимальное N, при котором выполняется это условие - N = 13.
Находится перебором (вариант - двоичным поиском).
При ручном переборе проще, конечно, этот огород не городить, а проверить N = 2, потом 10, потом 20, потом двоичный поиск.

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить
постоянный участник


Сообщение: 356
ссылка на сообщение  Отправлено: 07.12.18 12:27. Заголовок: Спасибо. Что бы не п..


Спасибо.
Что бы не пугать функцией ceil(...), задачу свела к нахождению минимального N, при котором 3N<=22N-5

Спасибо: 1 
ПрофильЦитата Ответить
Администратор




Сообщение: 1766
ссылка на сообщение  Отправлено: 07.12.18 13:17. Заголовок: oval пишет: Что бы н..


oval пишет:
 цитата:
Что бы не пугать функцией ceil(...), задачу свела к нахождению минимального N, при котором 3N<=22N-5

Да, это эквивалентно.

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 298
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет