0

我正在编写一个在编码竞赛网站上找到的程序，我已经想出了如何解决这个问题，但是，我被困在其中的数学部分，我完全淡化了这个问题并展示了我需要什么。

首先我需要检查一个数字是否是序列的一部分，我的序列是2*a+1其中 a 是序列中的前一个元素或 2^n-1 以获得序列中的第 n 个项目。所以它是1,3,7,15,31,63 ...

我真的不想创建整个序列并检查是否存在数字，但我不确定执行此操作的更快方法是什么。

其次，如果给我一个数字，比如说 25，我想找出我的序列中的下一个最高数字到这个数字。因此，对于 25，它将是 31，对于 47，它将是 63，对于 8，它将是 13。

我怎么能在不创建整个序列的情况下做这些事情。

我在这里看到了不同序列的类似问题，但我仍然不确定如何解决这个问题

4

3 回答 3

2

首先找到序列中任何术语的显式公式。我懒得写证明，所以只需添加1到序列中的每个术语：

 1 + 1 =  2
 3 + 1 =  4
 7 + 1 =  8
15 + 1 = 16
31 + 1 = 32
63 + 1 = 64
...

你可以清楚地看到a_n = 2^n - 1。

要检查特定数字是否在您的序列中，假设它是：

x = 2^n - 1
x + 1 = 2^n

来自维基百科：

整数的二进制表示可以应用非常快速的测试来确定给定的正整数 x 是否是 2 的幂：

正 x 是 2 的幂 ⇔ (x & (x − 1)) 等于 0。

所以要检查，只需执行以下操作：

bool in_sequence(int n) {
    return ((n + 1) & n) == 0;
}
于 2013-03-02T05:45:42.227 回答
1

正如@Blender 已经指出你的序列本质上是2^n - 1，如果你使用整数格式来存储它，你可以使用这个技巧：

boolean inSequence(int value) {
    for (int i = 0x7FFF; i != 0; i >>>= 1) {
        if (value == i) {
            return true;
        }
    }
    return false;
}

请注意，对于序列中的每个元素，其二进制表示将是很多0s，然后是很多1s。

例如，7in binary is0000000000000000000000000000111和63in binary is 0000000000000000000000000111111。

该解决方案从01111111111111111111111111111111使用无符号移位开始，然后比较它是否等于您的值。

很好很简单。

于 2013-03-02T05:25:50.750 回答
0

如何找到下一个更高的数字：

例如，我们得到 19 ( 10011 ) ，应该返回 31 (11111)

int findNext(int n){
    if(n == 0) return 1;

    int ret = 2;         // start from 10
    while( (n>>1) > 0){  // end with 100000
        ret<<1;
    }
    return ret-1;
}
于 2013-03-02T06:17:36.467 回答