Архив метки: php

Числа Фибоначчи

Для расчета какого-то числа Фибоначчи необязательно брутфорсить, т.е. перебирать всю последовательность методом сложения. Есть прекрасная Формула Бине. По ней прекрасно можно найти n-й элемент последовательности.

А если воспользоваться еще и асимптотикой, т.е. упрощенной формулой, то легко найти нужное число, как ближайшее целое число к результатам этой функции.

Ну и наконец мы можем таким образом найти n, при котором число Фибоначчи перевалит, например, за 1000 знаков, по формуле: i * Math.log10(phi) + Math.log10(1/Math.sqrt(5)) , где phi — так называемое Золотое сечение. Вычисляется по формуле (Math.sqrt(5) + 1) / 2

Почему формула такая? Да потому что следуем условию, что phi**n/sqrt(5) > 10**999 (** — степень, 10**999 — это первое число, у которого 1000 знаков)

Кстати, все это можно вычислить ручкой на бумаге без калькулятора (приблизительно). Квадратные корни вычисляются делением столбиком. Логарифмы тоже можно посчитать.

Share Button

Преобразовать IP адрес в целое число на PHP

Рассмотрим IP адрес версии 4. Он состоит из 4х октетов, 4 чисел, каждое из которых может быть от 0 до 255. По сути, каждое число имеет тип byte, состоит из 8 битов.

В интернете множество вариантов, как сделать конвертацию (1, 2). Наиболее наглядно, на мой взгляд, рассмотрели проблему здесь.

Сюда же я приведу свой вариант, реализованный на уровне бинарной обработки чисел. Кажется, он как обычно быстрее, чем все это варианты с перемножением и возведением в степень. Стоит упомянуть, что и в PHP, и в СУБД есть средства для конвертации IP в числе и обратно, так что данный пост имеет чисто академический смысл.


$ip = '70.112.108.147';
$arr = explode('.', $ip);

// для наглядности, что получается после смещений
echo decbin($arr[0]<<24) . "\n"; // 24 - это 3 блока по 8 нулей echo decbin($arr[1]<<16) . "\n"; // 16 - это 2 блока по 8 нулей echo decbin($arr[2]<<8) . "\n"; // 8 - это 1 блок по 8 нулей echo decbin($arr[3]) . "\n"; // оставляем как есть // теперь просто склеим все значения. Не просоммируем, а именно применим операцию OR, что-то вроде конкатенации $ipInt = $arr[0]<<24 | $arr[1]<<16 | $arr[2]<<8 | $arr[3]; var_dump($ipInt);

Share Button

Визуализация алгоритмов хранения данных

Пытаетесь понять, как работает бинарное дерево, и не понимаете, что там написано в статье в Википедии?

Тогда загляните на эту страничку. Прекрасный визуальный интерактивный инструмент по различным алгоритмам, как они работают.

Share Button

PHP memory and Zend Memory Manager

Хорошая статья про работу с памятью в среде разработки «для инвалидов», в PHP.
http://jpauli.github.io/2014/07/02/php-memory.html

Zend Memory Manager has nothing to share with ZendGC. ZendGC, appeared in PHP 5.3, is about clearing circular references in PHP variables and that’s absolutely all it does. It then acts on top of ZendMM, for PHP variables containing themselves (circular references).

Share Button

Округление числа в меньшую сторону на PHP

Есть задача округлять дробные положительные числа в меньшую сторону. 2 знака после запятой. В результате:
2.03000 -> 2.03
2.267777 -> 2.26

Используя стандартные средства и из-за особенностей обработки чисел с плавающей точкой в компьютере и PHP в частности получаем такие странные результаты:
php > echo floor(2.26 * 100) / 100;
2.25
php > echo round(2.03600, 2, PHP_ROUND_HALF_DOWN);
2.04

Без использования сторонних библиотек кажется, что единственный и самый простой способ выполнить такую задачу — через преобразования в строку:
// результат = взять целую часть от умножения, удалить последний символ, поделить на 100
$valueArray = explode('.', $value * 1000);
$value = substr(array_shift($valueArray), 0, -1) / 100;

Share Button