0

私はコーディングコンテストのウェブサイトで見つけたプログラムを書いています。問題を解決する方法をある程度理解しましたが、数学の部分で立ち往生しています。問題を完全に希釈して、必要なものを示しています。

最初に、数値がシーケンスの一部であるかどうかを確認する必要があります。私のシーケンスは2*a+1、a がシーケンスの前の要素であるか、シーケンスの n 番目の項目を取得する 2^n-1 です。1,3,7,15,31,63です...

シーケンス全体を作成して数値が存在するかどうかを確認したくはありませんが、これを行うためのより迅速な方法が何であるかはわかりません。

2 番目に、たとえば 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)) はゼロに等しい。

したがって、確認するには、次のようにします。

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 になり、さらに多数の s になることに注意してください1。

たとえば、7バイナリでは0000000000000000000000000000111であり63、バイナリでは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 に答える