Форум » Вычисление количества информации » Ошибка в условии? » Ответить
Ошибка в условии?
oval: Задача: Для обозначения артикулов товаров в интернет-магазине используются последовательности из 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
Поляков: 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, потом двоичный поиск.
oval: Спасибо. Что бы не пугать функцией ceil(...), задачу свела к нахождению минимального N, при котором 3N<=22N-5
Поляков: oval пишет: Что бы не пугать функцией ceil(...), задачу свела к нахождению минимального N, при котором 3N<=22N-5 Да, это эквивалентно.
полная версия страницы