Detect я члена двоичной последовательности

Question

У меня есть двоичная последовательность, которая следует специфической логике таким образом, что она начинается с 0 и

го члена = последовательность (п-1) -й термин + 0 + обратными (задним ходом (п-1) -го члена)

например:

0 
0 + 0 + 1 
001 + 0 + 011 
0010011 + 0 + 0011011 

Здесь, мне нужно выяснить, п-й член последовательности -го.

Мое мнение:

Я написал рекурсивную функцию для вычисления числа членов в последовательности k-го

public static long noOfElements(long elements){ 
    long answer; 
    if(elements == 1) 
     return 1; 
    else 
    answer = 1 + 2*noOfElements(elements-1); 
    return answer; 
} 

После анализа я выяснил последовательность следует определенной схеме, то k'th последовательность может быть разбита наполовину и переключить значения 0 и 1, я мог бы отслеживать результат.

Итак, моя функция ниже нарушает заданную последовательность вплоть до [0,0,1] рекурсивно

public static long letsBegin(long reqd, long length){ 
    long mid = (length + 1)/2; 
    if(length <= 3){ 
     return reqd; 
    }else{ 
     if(reqd > mid){ 
      reqd = reqd - 2*(reqd-mid); 
      switcher();     //Switcher stores if the value is switched 
      return letsBegin(reqd, mid); 
     }else{ 
      return letsBegin(reqd, mid); 
     } 
    } 
} 

В конце концов у меня есть индекс 1, 2 или 3 в [0,0,1] и Я вывожу значение соответствующим образом. Проблема здесь

1. Это не удается для неизвестного случая (возможно, моя логика ошибочна).
2. Число последовательностей может быть до 50, что делает число элементов = 1125899906842623 и, следовательно, занимает слишком много времени для вывода значения (> 2сек) Что может быть не так? Неправильно ли моя логика

Answer 1

Вам не хватает случая (когда reqd == mid) и вызывает рекурсивную функцию с неправильной длиной (середина вместо середины-1). После этих исправлений функция выглядит так:

public static long letsBegin(long reqd, long length){ 
    long mid = (length + 1)/2; 
    if(length <= 3){ 
     return reqd; 
    } else{ 
     if(reqd > mid){ 
      reqd = reqd - 2*(reqd-mid); 
      switcher();  //Switcher stores if the value is switched 
      return letsBegin(reqd, mid-1); 
     } else if(reqd < mid) { 
      return letsBegin(reqd, mid-1); 
     } else { 
      return 0; 
     } 
    } 
} 

Кроме того, код более сложный, чем необходимо. Попробуйте использовать следующее рекуррентное соотношение вместо:

T(n, k) = T(n, k-1)   if n < 2^{k-1} 
     = 0     if n = 2^{k-1} 
     = 1 - T(2^k-n, k-1) otherwise 

Answer 2

легко сделать с помощью рекурсии, количество элементов в к-й последовательности 2^(k+1)-1:

static int foo(long n, int k) { //n-th element (indexed from 0) in k-th sequence 
    long length = (2L << k) - 1; // computes 2^(k+1)-1 
    if(n >= length) return -1; // prevent invalid inputs 
    if(n == length/2) return 0; // middle point 
    if(n < length/2) return foo(n, k-1); //left half 
    return 1 - foo(length - n - 1, k-1); //right half 
} 

В последнем рекурсивном вызове, вы оба перевернуть массив и возвращаемое значение.

EDIT:

Обязательно используйте (2L << k) и не (2 << k) в противном случае это приведет к переполнению и может привести к бесконечной рекурсии.