Автор | Сообщение |
|
| постоянный участник
|
Сообщение: 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 бит ??? или я что-то не так делаю?
|
|
|
Ответов - 3
[только новые]
|
|
|
| Администратор
|
Сообщение: 1761
|
|
Отправлено: 03.12.18 23:36. Заголовок: oval пишет: 4N <..
oval пишет: цитата: | 4N < 4N на 5 бит ??? или я что-то не так делаю? |
|
Интересная задачка. Очевидно, что подход Пети когда-то даст преимущество. Поэтому предположение о некорректности условия ошибочно. Вы взяли слишком жёсткую верхнюю оценку На самом деле так: 1) Петя использует количество битов, равное K = ceil(log 2(12 N)), где функция ceil(x) выполняет округление вверх к ближайшему целому 2) условие ceil(log 2(12 N)) <= 4*N - 5 3) преобразуем, используя свойств логарифма: ceil(log 2(12 N)) = ceil(N*log 2(12)) = ceil(N*(2 + log 2(3)))= 2*N + ceil(N*log 2(3)) 4) сравниваем 2*N + N*ceil(log 2(3)) <= 4*N - 5 ceil(N*log 2(3)) <= 2*N - 5 или ceil(log 2(3 N)) <= 2*N - 5 или (спасибо oval) 3 N <= 2 2*N-5 5) минимальное N, при котором выполняется это условие - N = 13. Находится перебором (вариант - двоичным поиском). При ручном переборе проще, конечно, этот огород не городить, а проверить N = 2, потом 10, потом 20, потом двоичный поиск.
|
|
|
|
| постоянный участник
|
Сообщение: 356
|
|
Отправлено: 07.12.18 12:27. Заголовок: Спасибо. Что бы не п..
Спасибо. Что бы не пугать функцией ceil(...), задачу свела к нахождению минимального N, при котором 3 N<=2 2N-5
|
|
|
|
| Администратор
|
Сообщение: 1766
|
|
Отправлено: 07.12.18 13:17. Заголовок: oval пишет: Что бы н..
oval пишет: цитата: | Что бы не пугать функцией ceil(...), задачу свела к нахождению минимального N, при котором 3N<=22N-5 |
|
Да, это эквивалентно.
|
|
|
|