-6

Недавно наткнулся на следующую задачу:

Преобразуйте число в другую систему счисления, если известно, что система счисления 1 < base <10

Каркас к задаче:

function fromDecimal($base, $n) {

}

Подскажите, как преобразовать число $n в систему $base, без использования штатных функции.

4 ответа 4

6

Задача представляет интерес в плане перевода длинных десятичных чисел в другие системы счисления.
Реализовано:

  1. Простейшая обработка знака.
  2. Разделение числа на целую и дробную части.
  3. Рекурсивный перевод целой части в систему с основанием от 2 до 36 (функция entier_from_decimal()).
  4. Рекурсивный перевод дробной части в систему с основанием от 2 до 36 и заданным количеством знаков после запятой (функция frac_from_decimal()).

Специфика текстового формата привела к усложнению обработки дробной части (в частности - потребовалось восстанавливать лидирующие нули, чтобы она не сдвигалась влево).

Программа (PHP):

function entier_from_decimal(&$entier, $base){
    $chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";    // алфавит 36 символов
    $digit = bcmod($entier, $base);         // остаток      
    $entier = bcdiv($entier, $base);        // частное
    if(empty($entier)){                     // если частное нулевое
        return $chars[$digit];              // процесс закончен
    }else{                                  // иначе - рекурсивный вызов + цифра
        return entier_from_decimal($entier, $base, $scale) . $chars[$digit];
    } 
}   
function frac_from_decimal(&$frac, $base, $scale = 0){
    $chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";    // алфавит 36 символов
    if($scale == 0){                        // если дробная часть не нужна
        return "";                          // возвращаем пустую строку
    }                                       
    $len_frac = strlen($frac);              // запомнили длину  
    $frac = bcmul($frac, $base);            // умножили дробную часть на основание
    $digit = 0;                             // по умолчанию цифра нуль
    if(strlen($frac) > $len_frac){              // если произведение длиннее, то 
        $digit = $frac[0];                      // вырезаем первую цифру
        $frac = substr($frac, 1, $len_frac);    // и новая дробная часть - без неё
    }elseif(strlen($frac) < $len_frac){         // а если короче, то
        $frac = str_pad($frac, $len_frac, "0"); // дополняем нулями спереди     
    }

    return $chars[$digit] . frac_from_decimal($frac, $base, $scale-1);
}

function big_from_decimal($dec, $base, $scale = 0){
    if(substr($dec,0,1) == "+"){    // учёт знака "+"
        $dec = substr($dec,1,strlen($dec)-1);
        return "+".big_from_decimal($dec, $base, $scale);           
    } 
    if(substr($dec,0,1) == "-"){    // учёт знака "-"
        $dec = substr($dec,1,strlen($dec)-1);
        return "-".big_from_decimal($dec, $base, $scale);
    } 
    $frac = strstr($dec,".");       // дробная часть с точкой
    if(($frac==false) || (($len_frac = strlen($frac))<2)){
        return entier_from_decimal($dec, $base);
    }
    $frac = substr($frac, 1 , $len_frac -1);                // удаление точки
    $entier = substr($dec, 0, strlen($dec)- $len_frac);     // целая часть
    return entier_from_decimal($entier, $base). "."         // конкатенация
        .frac_from_decimal($frac, $base, $scale);           // результатов
}

$dec = "+12345678901234567890123456789012345678901234567890";
print("<br>В десятичной системе: $dec");
printf("<br>По основанию %s: %s<br>", $base="15", big_from_decimal($dec, $base));
$dec = "14348907";
print("<br>В десятичной системе: $dec");
printf("<br>По основанию %s: %s<br>", $base="3", big_from_decimal($dec, $base));
$dec = "-65536.0625";
print("<br>В десятичной системе: $dec");
printf("<br>По основанию %s: %s<br>", $base="16", big_from_decimal($dec, $base, 4));
$dec = "-0.1";
print("<br>В десятичной системе: $dec");
printf("<br>По основанию %s: %s<br>", $base="2", big_from_decimal($dec, $base, 20));
$dec = bcsub(bcpow("36","9"),"1");
print("<br>В десятичной системе: $dec");
printf("<br>По основанию %s: %s<br>", $base="36", big_from_decimal($dec, $base, 20));
$dec = "+0.3333333333333333";
print("<br>В десятичной системе: $dec");
printf("<br>По основанию %s: %s<br>", $base="3", big_from_decimal($dec, $base, 40));

Результаты:


В десятичной системе: +12345678901234567890123456789012345678901234567890
По основанию 15: +769B8CD2337E37356932B73A09C0C2928432D56360

В десятичной системе: 14348907
По основанию 3: 1000000000000000

В десятичной системе: -65536.0625
По основанию 16: -10000.1000

В десятичной системе: -0.1
По основанию 2: -0.00011001100110011001

В десятичной системе: 101559956668415
По основанию 36: ZZZZZZZZZ

В десятичной системе: +0.3333333333333333
По основанию 3: +0.0222222222222222222222222222222222102222
4

Данная задача без проблем решается при помощи штатной функции base_convert.

5
  • Простите, без штатной функции. 20 янв 2016 в 18:08
  • Данная задача встречается в CodeFigts и там она запрещена. 20 янв 2016 в 18:13
  • 2
    Если без штатной функции, гуглите алгоритм перевода систем счисления. Попытайтесь сами реализовать его на PHP. Не обижайтесь, но делать за Вас задачу, тем более для Вашего теста, вряд ли кто-то будет.
    – Streletz
    20 янв 2016 в 18:30
  • Хорошо, я отвечу на него сам тогда. Просто не понятен алгоритм. 20 янв 2016 в 18:42
  • @VasilyukDmitry Куда уж понятнее?
    – E_p
    20 янв 2016 в 18:54
2

Для простоты можно 2 функции:

1) Перевод в 10ю.

Пример:

111(2й)  = 1 * 2^2 + 1 * 2^1 + 1 * 2^0 = 7(10й);
1234(6й) = 1 * 6^3 + 2 * 6^2 + 3 * 6^1 + 4 * 6^0 = 310 (10й)
...

2) Перевод из 10й.

Пример:

101(10й) -> (6ю)
101/6 = 16 * 6 + 5
16/6  = 2  * 6 + 4
2/6   = 0  * 6 + 2

101(10й) = 245(6й)

т.е: что бы перевести из 3й в 8ю. 3->10->8. Думаю из примеров алгоритм понятен.

1

Доработано по правилам математики и небольшой бонус - возможность "сделать колонку "как в экселе", чтобы 27 номер был 'AA' а не 'A0' и не 'BA'.

И да, с помощью этой функции можно сгенерировать "айдишник как в ютубе". Впрочем для этого бы подошла и штатная base_convert();

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

A1
-- B1
---- C1
---- C2
-- B2
---- C3
---- C4

Кроме того, теперь можно указывать какие символы используются в системе счисления. Можешь сделать хоть 65-тысячную систему счисления, кодируй в восклицательные знаки и дефисы - пофиг. Тяжеловато будет в степень возводить, но теоретически...

Тесты:

<?php

$res = _base_convert_floor(100, '0ABCDEFGHIJKLMNOPQRSTUVWXYZ', '01');
$res2 = _base_convert_floor($res, '01', '0ABCDEFGHIJKLMNOPQRSTUVWXYZ', 0);
var_dump($res); // string(1) "D"
var_dump($res2); // string(3) "100"

$res = _base_convert_frac('.75', '01', '0123456789');
$res2 = _base_convert_frac($res, '0123456789', '01');
var_dump($res); // string(2) ".11"
var_dump($res2); // string(2) ".75"

$res = _base_convert('-10.75', '01', '0123456789');
$res2 = _base_convert($res, '0123456789', '01');
var_dump($res); // string(7) "-1010.11"
var_dump($res2); // string(5) "-10.75"

$res = _base_convert_floor('КУКУЁПТА', '0123456789', 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ');
$res2 = _base_convert_floor($res, 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ', '0123456789');
var_dump($res); // string(1) "495086673543"
var_dump($res2); // string(1) "КУКУЁПТА"

$res = _base_convert_floor(27, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ', '0123456789', -1);
$res2 = _base_convert_floor($res, '0123456789', 'ABCDEFGHIJKLMNOPQRSTUVWXYZ', 0, -1);
var_dump($res); // string(2) "AA"
var_dump($res2); // string(2) "27"

Исходник:

<?php

function _base_convert_floor($floor,
    string $baseCharsTo = null, string $baseCharsFrom = '0123456789',
    int $baseShiftTo = 0, int $baseShiftFrom = 0
) : string
{
    $floor = strval($floor);

    $baseTo = mb_strlen($baseCharsTo);
    $baseFrom = mb_strlen($baseCharsFrom);

    if (! $len = mb_strlen($floor)) return '';
    if ($baseTo < 2) throw new \InvalidArgumentException('Conversion assume `baseCharsTo` to be at least 2 letters: ' . $baseCharsTo);
    if ($baseFrom < 2) throw new \InvalidArgumentException('Conversion assume `baseCharsFrom` to be at least 2 letters: ' . $baseCharsFrom);

    $baseCharsFromIndex = array_flip(mb_str_split($baseCharsFrom));

    for ( $i = 0; $i < $len; $i++ ) {
        if (! isset($baseCharsFromIndex[ mb_substr($floor, $i, 1) ])) {
            throw new \InvalidArgumentException('The `floor` contains char outside `baseCharsFrom`: ' . $floor[ $i ]);
        }
    }

    $baseChars10 = '0123456789';

    if ($baseCharsFrom === $baseCharsTo) {
        return $floor;

    } elseif ($baseCharsFrom === $baseChars10) {
        $result = [];

        $div = $floor;
        if (0 > bccomp(bcadd($div, $baseShiftTo, 0), 0, 0)) {
            throw new \RuntimeException('Unable to convert cause of `baseShiftTo`: ' . $div);
        }

        do {
            $div = bcadd($div, $baseShiftTo, 0);

            $mod = bcmod($div, $baseTo, 0);
            $div = bcdiv($div, $baseTo, 0);

            $result[] = mb_substr($baseCharsTo, (int) $mod, 1);
        } while ( bccomp($div, 0, 1) );

        $result = implode('', array_reverse($result));

    } elseif ($baseCharsTo === $baseChars10) {
        $result = '0';

        for ( $i = 1; $i <= $len; $i++ ) {
            $idx = $baseCharsFromIndex[ mb_substr($floor, $i - 1, 1) ];
            $idx = bcsub($idx, $baseShiftFrom, 0);

            $pow = bcpow($baseFrom, $len - $i);
            $sum = bcmul($idx, $pow, 0);

            $result = bcadd($result, $sum, 0);
        }

    } else {
        $result = $floor;
        $result = _base_convert_floor($result, $baseChars10, $baseCharsFrom, 0, $baseShiftFrom);
        $result = _base_convert_floor($result, $baseCharsTo, $baseChars10, $baseShiftTo, 0);
    }

    return $result;
}

function _base_convert_frac(string $frac,
    string $baseCharsTo = null, string $baseCharsFrom = '0123456789',
    int $scale = null
) : string
{
    $frac = ltrim($frac, '.');

    $baseTo = mb_strlen($baseCharsTo);
    $baseFrom = mb_strlen($baseCharsFrom);

    if (! $len = mb_strlen($frac)) return '';
    if ($baseTo < 2) throw new \InvalidArgumentException('Conversion assume `baseCharsTo` to be at least 2 letters: ' . $baseCharsTo);
    if ($baseFrom < 2) throw new \InvalidArgumentException('Conversion assume `baseCharsFrom` to be at least 2 letters: ' . $baseCharsFrom);

    $baseCharsFromIndex = array_flip(mb_str_split($baseCharsFrom));

    for ( $i = 0; $i < $len; $i++ ) {
        if (! isset($baseCharsFromIndex[ mb_substr($frac, $i, 1) ])) {
            throw new \InvalidArgumentException('The `frac` contains char outside `baseCharsFrom`: ' . $frac[ $i ]);
        }
    }

    $scale = $scale ?? $len;
    $scale = max($scale, 0);

    $baseChars10 = '0123456789';

    if ($baseCharsFrom === $baseCharsTo) {
        return $frac;

    } elseif ($baseCharsFrom === $baseChars10) {
        $result = [];

        $mul = bcadd('0.' . $frac, 0, $scale);

        $limit = $scale;
        while ( $limit-- ) {
            $mul = bcmul($mul, $baseTo, $scale);
            $floor = bcadd($mul, 0, 0);

            $mul = bcsub($mul, $floor, $scale);

            $result[] = mb_substr($baseCharsTo, (int) $floor, 1);

            if (0 === bccomp($mul, 0, $scale)) break;
        }

        $result = implode('', $result);

    } elseif ($baseCharsTo === $baseChars10) {
        $result = '0';

        for ( $i = 1; $i <= $len; $i++ ) {
            $idx = $baseCharsFromIndex[ mb_substr($frac, $i - 1, 1) ];

            $pow = bcpow($baseFrom, -$i, $scale);
            $sum = bcmul($idx, $pow, $scale);

            $result = bcadd($result, $sum, $scale);
        }

        $result = explode('.', $result, 2)[ 1 ] ?? '0';

    } else {
        $result = $frac;
        $result = _base_convert_frac($result, $baseChars10, $baseCharsFrom);
        $result = _base_convert_frac($result, $baseCharsTo, $baseChars10);
    }

    return '.' . $result;
}

function _base_convert($num,
    string $baseCharsTo = null, string $baseCharsFrom = '0123456789',
    int $scale = null,
    int $baseShiftTo = 0, int $baseShiftFrom = 0
)
{
    $isNegative = 0 === mb_strpos($num, '-');

    $numAbs = ltrim($num, '-');
    [ $numFloor, $numFrac ] = explode('.', $numAbs, 2) + [ '0', '' ];

    $scale = $scale ?? mb_strlen($numFrac);

    $result = [];
    if (mb_strlen($numFloor)) $result[] = _base_convert_floor($numFloor, $baseCharsTo, $baseCharsFrom, $baseShiftTo, $baseShiftFrom);
    if (mb_strlen($numFrac)) $result[] = _base_convert_frac($numFrac, $baseCharsTo, $baseCharsFrom, $scale);

    $result = implode('', $result);

    if ($isNegative) {
        $result = '-' . $result;
    }

    return $result;
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.