支票號碼目前在一個序列中

我正在編寫一個程序，我在編碼競爭網站上找到了，我有點想通了如何解決這個問題，但是，我被卡在數學部分，我完全稀釋問題和展示我需要什麼。支票號碼目前在一個序列中

首先我需要檢查一個數是否是序列的一部分，我的序列是2*a+1其中a是序列中的前一個元素或2^n-1以獲得序列中的第n個元素。所以它是1,3,7,15,31,63 ...

我真的不想創建整個序列，並檢查是否存在一個數字，但我不知道什麼更快方法來做到這一點。

第二，如果我給了一個數字可以說25，我想找出序列中的下一個最高的數字，這個數字。因此，對於25，它將是31，對於47，它將是63，對於8將是13.

我怎樣才能做到這些東西，而無需創建整個序列。

我在這裏看到了類似的問題，用不同的序列，但我仍然不知道如何解決這個

來源

2013-03-02 yahh

序列總是「係數* n +偏移」嗎？然後它非常容易，可以在不斷的時間複雜度下完成。 – Zeta 2013-03-02 05:10:25

你可以看到'n + 1'是否是2的冪。 – Blender 2013-03-02 05:11:08

@Blender你的編輯看起來不正確。序列1,3,7,15是2 * a + 1，其中'a'是序列中的前一個數字。 – 2013-03-02 05:12:30

首先找到序列中任何項的顯式公式。我懶得寫了一個證明，所以只需添加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是否是二的功率：

POSIT ive x是⇔（x &（x - 1））的冪等於零。

所以去檢查，只是做：

bool in_sequence(int n) { 
    return ((n + 1) & n) == 0; 
}

來源

2013-03-02 05:45:42 Blender

如果數字不在序列中怎麼辦那麼怎麼做我在序列中找到下一個最高數字 – yahh 2013-03-02 06:06:41

@yahh：試着找出它。 – Blender 2013-03-02 06:07:55

哦，你的答案絕對比我的好！（這甚至適用於'2147483647'） – 2013-03-02 09:23:20

正如@Blender已經指出你的序列基本上是2^n - 1，如果你使用的整數格式，您可以使用這一招其存儲：

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

請注意，在您的序列中的每個元素，它的二進制表示將有大量的0秒，然後大量的1秒。

例如，7二進制是二進制0000000000000000000000000000111和63是0000000000000000000000000111111。

該解決方案從01111111111111111111111111111111開始，並使用無符號位移，然後比較它是否等於您的值。

不錯，簡單。

來源

2013-03-02 05:25:50

你能解釋你如何得到這個解決方案 – yahh 2013-03-02 05:27:53

如何找到下一個更高的數字：

例如，我們得到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-02 06:17:36 MrROY

支票號碼目前在一個序列中

回答

相關問題