代码之家 › 专栏 › 技术社区 › jeroen

数学问题:循环或递归

loops recursion math php

jeroen · 技术社区 · 15 年前

我试图将一个数字分解成一个数字数组(在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(地板(log()) 对于这样一个简单的问题似乎有点过分。

在我看来,这个问题需要用一些非常简单的数学进行递归求解,但我看不出来。

任何帮助都将得到重视。

编辑: 二进制是关键,非常感谢!

6 回复 | 直到 15 年前

Bill the Lizard Alexis MP 15 年前

您可以使用以下(未测试)功能检查输入编号的每个位。

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

它使用位与函数检查变量$var中位置$pos处的位。为了简洁起见,我将向您展示4位数字。

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

如果我想检查数字3的位置0(最右边的一位),我会这样调用函数:

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

在内部,checkbit将把常量1向左移动0次,因为我传入了一个0。然后,它将按位与(&)返回我输入的结果,3。由于3=0011和1=0001,结果为真,因为第0位在位和运算符的两个参数中都设置。

Brendan 15 年前

你可以得到数字的二进制表示,1表示包含2的幂,0表示不包含

即


$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中可能有更好的语法方法。

Scott 15 年前

根据我的经验,递归比循环有更多的开销,所以我建议继续使用循环解决方案。

dw.mackie 15 年前

如果只做了一点明智的操作(例如“num&0x001”),并检查该操作的值是否为零,那么通过这些位进行跳变应该是很简单的,如下所示: (我知道这是在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;
}

像这样的事情在任何语言中都应该是微不足道的。

Venkat D. 15 年前

另一种将整数分解为2的幂的方法是继续除以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;
}

Mark 15 年前

除非你的数字非常稀疏(也就是说,数字数组很小),否则在所有的能量下工作可能会更快。保持在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;
}