二進制選擇過程

我一直在做什麼似乎是一個簡單的任務，是讓我瘋了。所以如果你喜歡編程挑戰......請繼續閱讀。二進制選擇過程

我希望能夠採取一些例如範圍[1:20]並使用類似於二元語法算法的機制打印值。因此，首先打印最低值（在此情況下爲1），然後打印中間值（例如在此情況下爲10），然後將範圍分爲四等分並在1/4和3/4處打印值（在此情況下爲5和15），然後分成八個等等，直到範圍內的所有值都被打印完畢。

這樣做的應用（這是不是真的有必要了解這裏）是該行爲更有效的網頁時，在中間被訪問的第一範圍內存頁面訪問機制。

對於這個問題，這將是足夠採取任何數量的範圍和在上面描述的方式打印該值。

對這個有什麼想法？僞代碼解決方案將會很好。我會試圖證明這一點，但迄今爲止我嘗試過的一切都不會削減它。謝謝。

更新：根據要求，示例[1:20]的期望輸出將如下所示：1，10，5，15，3，7，12，17，2，4，6，8， 11，13，16，18，9，19，20

該輸出可以在取決於所使用的算法許多類似的方式呈現。但是，這個想法是首先顯示一半的價值，然後是四分之一，然後是八分之一，然後是十六分之一，而不是先前提供的價值。

來源

2012-08-08 Steve Walsh

能否請您提供一個樣本情況下所需的完整輸出？ – 2012-08-08 18:26:32

但你只能使用你分配的頁面，我是對的嗎？ – 2012-08-08 18:29:44

這回答類似的問題可能會有所幫助：http://stackoverflow.com/a/11761192/1009831 – 2012-08-08 18:32:53

這裏是產生類似輸出到你的例子一些Python代碼：

def f(low, high): 
    ranges = collections.deque([(low, high)]) 
    while ranges: 
     low, high = ranges.popleft() 
     mid = (low + high) // 2 
     yield mid 
     if low < mid: 
      ranges.append((low, mid)) 
     if mid + 1 < high: 
      ranges.append((mid + 1, high))

實施例：

>>> list(f(0, 20)) 
[10, 5, 15, 2, 8, 13, 18, 1, 4, 7, 9, 12, 14, 17, 19, 0, 3, 6, 11, 16]

的low, high範圍排除端點，如同慣例在Python，所以結果包含爲0〜19

的代碼數值，採用一個FIFO存儲仍需要處理的子範圍。 FIFO在整個範圍內初始化。在每次迭代中，下一個範圍都會彈出，並且中點會放棄。然後，如果當前範圍的下部和上部子範圍非空，則將其附加到FIFO。

編輯：這裏是C99完全不同的實現：

#include <stdio.h> 

int main() 
{ 
    const unsigned n = 20; 
    for (unsigned i = 1; n >> (i - 1); ++i) { 
     unsigned last = n; // guaranteed to be different from all x values 
     unsigned count = 1; 
     for (unsigned j = 1; j < (1 << i); ++j) { 
      const unsigned x = (n * j) >> i; 
      if (last == x) { 
       ++count; 
      } else { 
       if (count == 1 && !(j & 1)) { 
        printf("%u\n", last); 
       } 
       count = 1; 
       last = x; 
      } 
     } 
     if (count == 1) 
      printf("%u\n", last); 
    } 
    return 0; 
}

這通過使用一些技巧，以確定是否爲整數已在前面的迭代已經發生避免了FIFO的必要性。因爲你知道FIFO的最大尺寸（我想它是類似於（n + 1）/ 2，但你需要仔細檢查這個），你可以使用環形緩衝區來保存排隊的範圍。

編輯2：這裏是在C99又一解決方案。它被優化爲僅執行一半循環迭代，並且僅使用位操作和添加，而不用乘法或除法。它也更加簡潔，它不包含0的結果，所以你可以在開始時按照最初的設計進行。

for (int i = 1; n >> (i - 1); ++i) { 
    const int m = 1 << i; 
    for (int x = n; x < (n << i); x += n << 1) { 
     const int k = x & (m - 1); 
     if (m - n <= k && k < n) 
      printf("%u\n", x >> i); 
    } 
}

（這是我打算從一開始就寫代碼，但我花了一些時間來環繞它我的頭。）

來源

2012-08-08 18:41:19

看起來很甜美。我明天會試試這個方法，然後回報。謝謝。 – 2012-08-08 18:51:38

哇 - 這個答案很完美。我必須瞭解deque物體和屈服特徵 - 這兩者都值得學習。不幸的是，我不得不在C代碼中實現這一點。我將需要創建一個子域結構的FIFO列表，這將在c中更加難以實現。這強調了python對這類問題的強大作用。任何人有我的任何提示在c實現？ – 2012-08-09 08:55:55

@ZincX：我用一些提示更新了我的答案。對不明顯的C代碼抱歉。 – 2012-08-09 13:57:02

Binary Heap因爲陣列已具有這種結構。您可能希望將數組存儲在此表單中並按順序打印。對於節點i，子女是2i + 1,2i + 2。

來源

2012-08-08 18:51:41 Ankush

期望的結果是一個非常不尋常的二進制堆形式（如果您完全可以這樣調用它）：它將是一個二進制搜索樹，以通常存儲二進制堆的方式存儲在數組中。但是，tt並不滿足堆屬性，這個觀察也不意味着構建這個數組的簡單方法。 – 2012-08-08 21:36:01

嗯......你基本上是在尋找某種各種各樣的空間填充曲線。我幾乎可以肯定，你可以用聰明的手段做到這一點。您可能想看看計算Morton Z-order或Ahnentafel索引的指數的方式，這些指標用於某些不依賴緩存的模板算法。幾年前，我看了一下這個，索引與你所描述和完成的有點相似。

來源

2012-08-08 18:57:47 Emmet

空間填充曲線是一個從區間到單位正方形一對一映射的連續函數。這與提出的問題有什麼關係？ – 2012-08-08 21:29:55

很容易爲1/2，對不對？

那麼爲什麼不這樣做遞歸，這樣1/4就是1/2 1/2和1/8是1/4 1/2？

來源

2012-08-08 20:27:00 user1277476

*½很容易？你如何終止這個算法？你如何跟蹤已經消費的數字？ – 2012-08-08 21:37:49

@SvenMarnach在遞歸解決方案中，您會將序列分成多個部分，然後再細分，依此類推。因此，如果您正確劃分，則無需跟蹤任何內容。當下一個分區產生空序列時，終止發生。 – HonkyTonk 2012-08-09 10:26:29

@HonkyTonk：簡單的遞歸方法會以錯誤的順序產生值。我不確定你在說什麼算法，但我想不出一個簡單的遞歸解決方案。 – 2012-08-09 12:01:10

二進制選擇過程

回答

相關問題