Архив метки: логарифм

Фибоначчи, Haskell, O(log n)

(Внимание: дальше не написано ничего нового, но если вы не знаете о возведении в степень за \(O(\log n)\), можете чуть-чуть почитать.)

Не секрет, что числа Фибоначчи можно вычислить за экспоненциальное время, используя наивную рекурсию; за линейное время, используя более аккуратный способ; и даже за константное время, используя округление \(\frac{\phi^n}{\sqrt5}\) до ближайшего целого и скрещивая пальцы, что знаков хватит.

Так же не секрет, что, не используя floating point, можно обойтись и \(O(\log n)\) с помощью вычисления степени за \(O(\log n)\). Но всё равно опишу это.

Читать далее Фибоначчи, Haskell, O(log n)

Здесь должен быть график. Если вы видите это — значит, вам крупно не повезло.

Опыт с тенями

Выключите в комнате весь свет, оставив только какую-нибудь лампу, дающую рассеянный свет на какую-нибудь стену, стол или другую поверхность, которая в вашем доме сойдёт за хороший экран. Возьмите фонарик и какой-нибудь предмет. Пусть его тень под светом лампы не мешает, направьте свет фонарика так, чтобы тень в его свете не накладывалась на тень от лампы. Заметьте разницу яркостей в тени и вне её. А теперь стрельните чем-нибудь в лампу, чтобы она больше не светила и быстро снова смотрите на яркости в тени и вне тени. Если всё сделано правильно, и вы человек — разность яркостей должна стать больше. Как!? Лампа ведь не светит одинаково на обе области! Фонарик тоже не мог от горя засветиться сильнее.

Читать далее Опыт с тенями