Matematiksel sorun: döngü veya özyinelemeli

6 Cevap php

Ben bir şekilde (php) sayıların bir diziye bir dizi kırmaya çalışıyorum ki örneğin:

  • 25 olur (16, 8, 1)
  • 8 olur (8)
  • 11 olur (8, 2, 1)

Ben doğru terim olduğunu bilmiyorum, ama ben fikir açık olduğunu düşünüyorum.

Bir döngü ile benim çözüm oldukça basittir:

   $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;
   }

Ben de bir özyinelemeli çözüm var ama global bir değişken (istemiyorum) kullanmadan işe alamazlar, aşağıdaki yakındır ama diziler diziler sonuç geliyor:

   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);

Ancak, pow(floor(log())) gibi bir şey kullanarak bu gibi basit bir sorun için biraz fazla gibi görünüyor.

Bu sorun bazı çok basit matematik ile bir özyinelemeli çözüm aramaları, ama ben sadece görmüyorum gibi geliyor bana.

Herhangi bir yardım apreciated olacaktır.

Edit: İkili çok teşekkürler tüm anahtarıdır!

6 Cevap

Sen şu (denenmemiş) fonksiyonu ile giriş sayının her bir biti kontrol edebilirsiniz.

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

Bu ikilik VE işlevini kullanarak değişken $ var içinde $ pos biraz denetler. Ben kısalık için 4-bit numaraları size göstereceğim.

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

Ben pozisyon 0 sayısının 3 (sağdaki bit) kontrol etmek isterseniz, ben bu gibi işlevi çağırır:

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

İçten, kontrol biti ben bir 0 geçirilen çünkü sol 0 kez 1 sabit degisecek. Yana 3 = 0011 ve 1 = Daha sonra. Ben geçirilen sayı, 3 ile sonuç bitsel gidiyor VE (&) oluyor 0. bit bitsel AND operatörü için her iki argümanın ayarlanır beri 0001 sonuç doğrudur.

Sadece sayının ikili gösterimini alabilir - 1 aracı 2 güç, sıfır aracı olmadığını içerir

yani


$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} ";
  }
}

Bu test edilmiş ve bu iş tamam ama PHP söz dizimi yapmanın muhtemelen daha iyi yolları vardır edilir.

Bu yineleme döngü daha fazla yükü olduğunu benim deneyim oldu, ben senin loop çözüm ile sopa öneririm.

If you just do a bit-wise and (like "num & 0x0001" for example), and check the value of that operation for zeroness, it should be trivial to trip thru the bits, like so: (I know this is in java, but I don't know php, and it's not really a php-specific problem anyway)

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

Böyle bir şey herhangi bir dilde yapmak için önemsiz olmalıdır.

2 güçlerin içine bir tamsayı kırmak için başka bir yolu 2'ye bölünüp kalan bulma tutmak olacaktır.

For example: 25/2 = 12 R 1, power = 2^0 = 1

12/2 = 6 R 0, güç = 2 ^ 1 = 2

6/2 = 3 R 0, güç = 2 ^ 2 = 4

3/2 = 1 R 1, güç = 2 ^ 3 = 8

1/2 = 0 R 1, güç = 2 ^ 4 = 16

Yani, burada bu kalan 1 olduğu tek yer = 1 + 8 + 16 25 çünkü.

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;
}

Lütfen numaralar (yani number_array küçük olacak) çok seyrek sürece, tüm güçleri ile çalışmaya muhtemelen daha hızlı. Tabanı 2 ile kalıyorum:

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;
}

etiketler