Генерация сегментов путем рекурсивного деления пополам - PullRequest
Новая
       10

Генерация сегментов путем рекурсивного деления пополам

1 голос
/ 26 июня 2019

Мне нужно рекурсивно разделить число на два и сделать сегменты.до тех пор, пока длина сегмента не станет меньше 1;ех.когда число равно 15, у нас будет: 

0,15 ==> 1 segment, length = 15 
0,7.5,15 ==> 2 segments, length = 7.5
0,3.75,7.5,11.25,15 ==> 4 segments, length = 3.75
0,1.875,3.75,5.625,7.5,9.375,11.25,13.125,15 ==> 8 segments, length = 1.875 
0,0.9375,1.875, ..... ,13.125,14.0625,15 ==> 16 segments, length = 0.9375

, пока я могу сделать это с помощью наивного кода, как показано ниже: 

double delta = N; //N being the input number
while(delta > 1.0)
    delta /= 2.0;
int count = (N / delta) + 1;
var series = Enumerable.Range(0, count).Select(x => x * delta).ToArray();

Есть ли лучший способ?

1 Ответ

0 голосов
/ 26 июня 2019

Используя следующий метод для вычисления следующей наибольшей степени 2 для 32-разрядных целых чисел: 

public int NextHighestPowerOf2(int n) {
    // if n > 2^31 then fails - answer can't fit in int
    if ((n & (n - 1)) == 0) // n is a power of 2
        return n << 1;
    else {
        --n;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        return n + 1;
    }
}

Вы можете вычислить series аналогично: 

var nhp2 = NextHighestPowerOf2(N);
var series = Enumerable.Range(0, nhp2+1).Select(n => (double)(n*N)/nhp2).ToArray();

ПРИМЕЧАНИЕ: Это немного отличается от вашего кода тем, что разделяет начальную степень 2.Ваш код имеет сегменты размером 1 для начальной степени 2. Если вы хотите, чтобы ваш код, просто измените метод, чтобы использовать только часть else.

...