Математическая задача: цикл или рекурсия

Я пытаюсь разбить число на массив чисел (в php), например, так:

  • 25 становится (16, 8, 1)
  • 8 становится (8)
  • 11 становится (8, 2, 1)

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

Мое решение с циклом довольно простое:

   $number = rand(0, 128);    
   $number_array_loop = array();

   $temp_number = $number;
   while ($temp_number > 0) {
       $found_number = pow(2, floor(log($temp_number, 2)));
       $temp_number -= $found_number;

       $number_array_loop[] = $found_number;
   }

У меня также есть рекурсивное решение, но я не могу заставить его работать без использования глобальной переменной (не хочу этого), следующее приближается, но приводит к массивам в массивах:

   function get_numbers($rest_number) {

       $found_number = pow(2, floor(log($rest_number, 2)));

       if ($found_number > 0) {
           $temp_array[] = get_numbers($rest_number - $found_number);
           $temp_array[] = $found_number;
       }

       return $temp_array;
   }

   $number_array_recursive = array();
   $number_array_recursive = get_numbers($number);

Однако использование чего-то вроде pow(floor(log())) кажется слишком сложным для такой простой задачи.

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

Любая помощь будет оценена.

Редактировать: Двоичный код — это ключ, всем большое спасибо!


php loops recursion math
person jeroen    schedule 17.02.2009    source источник

Ответы (6)


arrow_upward
3
arrow_downward

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

function checkBit($var, $pos)
{
    return ($var & (1 << $pos));
}

Он проверяет бит в позиции $pos в переменной $var с помощью побитовой функции AND. Для краткости я покажу вам 4-битные числа.

  • 1 = 0001
  • 2 = 0010
  • 4 = 0100
  • 8 = 1000

Если я хочу проверить позицию 0 (самый правый бит) числа 3, я бы вызвал функцию следующим образом:

$number = 3;
checkBit($number, 0);

Внутри checkBit сдвинет константу 1 влево 0 раз, потому что я передал 0. Затем он будет выполнять побитовое И (&) с результатом, который я передал, 3. Поскольку 3 = 0011 и 1 = 0001 результат истинен, поскольку в обоих аргументах побитового оператора И установлен 0-й бит.

person Bill the Lizard    schedule 17.02.2009
comment
Спасибо за тестирование. Прошло бы еще несколько часов, прежде чем я смог бы это сделать. - person Bill the Lizard; 17.02.2009
comment
Я попытался немного разъяснить, как это работает. Надеюсь, это поможет. - person Bill the Lizard; 17.02.2009

arrow_upward
7
arrow_downward

Вы можете просто получить двоичное представление числа — 1 означает, что эта степень двойки включает в себя, а ноль — нет.

i.e.


$binary_number = decbin($test_number);
$binary_string = "${binary_number}";
for ($i = 0; $i < strlen($binary_string); $i++) {
  if ($binary_string[strlen($binary_string) - $i - 1] == "1") {
    $num_out = pow(2, $i);
    print "${num_out} ";
  }
}

Это проверено и работает нормально, но, вероятно, есть лучшие способы синтаксического выполнения в PHP.

person Brendan    schedule 17.02.2009
comment
хех, только что написал, сейчас проверю - person Brendan; 17.02.2009
comment
Я знал, что это должно быть легко! Большое спасибо. - person jeroen; 17.02.2009

arrow_upward
3
arrow_downward

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

person Scott    schedule 17.02.2009
comment
Спасибо, это полезно знать на будущее (кажется, здесь я могу обойтись и без того и другого...) - person jeroen; 17.02.2009

arrow_upward
1
arrow_downward

Если вы просто делаете побитовое и (например, «num & 0x0001») и проверяете значение этой операции на нулевое значение, должно быть тривиально споткнуться по битам, например так: (я знаю, что это в java , но я не знаю php, и в любом случае это не проблема, специфичная для php)

    int number=25;
for (int i = 0; i < 16; i++)
{
    if ((number & 0x0001) != 0)
    {
    System.out.println("" + Math.pow(2, i));
    }
    number = number >> 1;
}

Что-то подобное должно быть тривиально на любом языке.

person dw.mackie    schedule 17.02.2009

arrow_upward
1
arrow_downward

Другой способ разбить целое число на степени двойки — продолжать делить на 2 и находить остаток.

Например: 25/2 = 12 R 1, мощность = 2^0 = 1.

12/2 = 6 R 0, мощность = 2 ^ 1 = 2

6/2 = 3 R 0, мощность = 2 ^ 2 = 4

3/2 = 1 R 1, мощность = 2^3 = 8

1/2 = 0 R 1, мощность = 2 ^ 4 = 16

Итак, здесь 25 = 1 + 8 + 16, потому что это единственные места, где остаток равен 1.

function powers_of_2($n)
{
    $powers = array();
    $base = 1;
    while ($n > 0)
    {
        if ($n % 2 == 1)
        {
            $powers[] = $base;
        }
        $n = (int)$n/2;
        $base *= 2;
    }
    return $powers;
}
person Venkat D.    schedule 18.02.2009
comment
Спасибо, именно такое математическое решение я изначально искал, но оказалось, что его можно сделать еще проще. - person jeroen; 18.02.2009

arrow_upward
0
arrow_downward

Если ваши числа не очень разрежены (т.е. number_array будет маленьким), вероятно, быстрее работать со всеми полномочиями. Оставаясь с базой 2:

function get_powers_of_2($n) {

  // $max_pow = 31;       // faster if you know the range of $n
  $max_pow = log($n, 2);  // safe
  $powers = array();

  for($i = 0; i <= $max_pow; $i++) {
    $pow = 1 << $i;
    if($n & $pow) $powers[] = $pow;
  }
  return $powers;
}
person Mark    schedule 17.02.2009