java - 检测二进制序列的第 n 项

Question

我有一个遵循特定逻辑的二进制序列它以 0 和

开头

第 n 项 = (n-1)th term + 0 + inverse(reverse(n-1)th term)

例如:

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

在这里，我需要找出第 k 个序列的第 n 项。

我的看法:

我写了一个递归函数来计算第 k 个序列中的项数

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

经过分析，我发现序列遵循一定的模式，第k个序列可以被分解成一半，并切换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);
        }
    }
}

最后，我在 [0,0,1] 中有索引 1、2 或 3，并相应地输出值。这里的问题是

1. 它因某些未知情况而失败(可能是我的逻辑错误)。
2. 序列的数量最多可达 50，使得元素数量 = 1125899906842623，因此输出值的时间太长(>2 秒)可能出了什么问题？我的逻辑不对吗

Answer 1

用递归很容易搞定，第k个序列的元素个数是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
}

在最后一次递归调用中，您同时翻转了数组和返回值。

编辑:

务必使用(2L << k)而不是 (2 << k)否则会导致溢出并可能导致无限递归。