Так например, fp-сообществу понравилась эта задачка, придуманная в нашем отделе.
По мотивам Top 25 Oddball Interview Questions Of 2010 и особенно вопроса, задаваемого в UBS
sqrt(2000) = ?
вспомнилась классическая задача, задаваемая у нас:log2(1000000) = ?
Не предполагается, что ответ будет с точностью до какого знака после запятой (точки) - достаточно оценить с точностью до единицы.
5 комментариев:
sqrt(2000) ~ 45 (45*40=1800, 45*5=225, 45^2=2025)
log2(1m) ~ 20 (2^20=1024*1024)
@GrAndSE: это уж очень грубая оценка, но пойдёт)
Владимир, в задании то с точностью до единицы :) Потому и первое что приходит на ум :) Разумеется, что можно помозговать и придумать более элегантные/точные обоснования и/или решения (хотя для log2(1m) для программиста 20 наверное самое очевидное :) ) А какие бы Вы сами предложили решения?
log2(1M) = log2(10^6) = 6 * log2(10)
log2(8) = 3 < log2(10)
т.е если очень грубо - то
18 < log2(1M) < 20 (используя ваш под подход)
если точнее, то
log2(10) = log2(8 * (10/8)) = 3 + log2(10/8) = 3 + log2(1 + 1/4) = (первый член ряда Маклорена) ~= 3.25
т.е log2(1M) ~= 6 * 3.25 = 19.5
Фу-фу-фу. 19.5 - более грубая оценка, чем 20.
Если бы мне понадобилось дать оценку точней - я бы начал с первоначальной оценки 20, а потом искал бы поправку:
1e6 = 2^20/A
A = 1.024*1.024 = 1.048576 (ну, в уме бы считал, как 1.05)
logb(1e6) = 20 - logb(A)
Ну а тут или logb(A) считал бы как ln(A)/ln(2) ~= 0.05/ln(2) ~= 0.07
logb(1e6) ~= 20-0.035 = 19.93
либо выписал бы цепочку
A, A^2, A^4, A^8 и так далее и получил бы 1/logb(A), сложив степени членов последовательности, дающих в сумме 2.
Отправить комментарий