बाइनरी चयन प्रक्रिया

Question

मैं एक साधारण काम प्रतीत होता हूं जो मुझे पागल कर रहा है। तो यदि आप एक प्रोग्रामिंग चुनौती पसंद करते हैं ... पढ़ें।

मैं एक संख्या सीमा लेने में सक्षम होना चाहता हूं उदा। [1:20] और बाइनरी सीरैच एल्गोरिदम के समान तंत्र का उपयोग करके मान मुद्रित करें। तो, सबसे पहले सबसे कम मूल्य (इस मामले में 1) प्रिंट करें और फिर मध्य मान (उदाहरण के लिए इस मामले में 10) और फिर श्रेणी को क्वार्टर में विभाजित करें और मानों को 1/4 और 3/4 पर प्रिंट करें (इस मामले में, 5 और 15) और फिर आठवें में विभाजित करें और तब तक जब तक सीमा में सभी मूल्य मुद्रित नहीं किए जाते हैं।

इसका आवेदन (जो यहां समझने के लिए वास्तव में जरूरी नहीं है) एक मेमोरी पेज एक्सेस मैकेनिज्म के लिए है जो पहले मध्य श्रेणी में पृष्ठों तक पहुंचने पर अधिक कुशलतापूर्वक व्यवहार करता है।

इस समस्या के लिए, ऊपर वर्णित तरीके से किसी भी संख्या सीमा को लेने और मूल्यों को मुद्रित करने के लिए पर्याप्त होगा।

इस पर कोई विचार? एक psuedo कोड समाधान ठीक होगा। मैं इसका प्रयास दिखाऊंगा लेकिन अब तक जो कुछ भी मैंने कोशिश की है वह इसे काट नहीं देती है। धन्यवाद।

अद्यतन: अनुरोध के अनुसार, उदाहरण के लिए वांछित आउटपुट [1:20] ऐसा कुछ होगा: 1, 10, 5, 15, 3, 7, 12, 17, 2, 4, 6, 8, 11, 13, 16, 18, 9, 1 9, 20

यह आउटपुट उपयोग किए गए एल्गोरिदम के आधार पर कई समान तरीकों से प्रस्तुत किया जा सकता है। लेकिन, विचार पहले आधे मूल्यों को छोड़कर पहले आधे मूल्यों, फिर क्वार्टर, फिर आठवें, फिर 16 वीं, आदि प्रदर्शित करना है।

Answer 1

यहाँ कुछ अजगर अपने उदाहरण की तरह उत्पादन उत्पादन कोड है:

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 सीमा समाप्ति बिंदु शामिल नहीं, के रूप में अजगर में सम्मेलन है, इसलिए परिणाम होता है संख्या 0 से 19.

कोड उपरोंज को संग्रहीत करने के लिए एक फीफो का उपयोग करता है जिसे अभी भी संसाधित करने की आवश्यकता है। एफआईएफओ पूरी श्रृंखला के साथ शुरू किया गया है। प्रत्येक पुनरावृत्ति में, अगली रेंज पॉप हो जाती है और मध्य-बिंदु उत्पन्न होता है। फिर, वर्तमान सीमा के निचले और ऊपरी सब्रेंज को फीफो में जोड़ा जाता है यदि वे खाली नहीं हैं।

संपादित:

#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; 
} 

यह निर्धारित करने के लिए अगर एक पूर्णांक पहले ही किसी पूर्व चरण में हुआ है कुछ चालें का उपयोग करके एक फीफो की आवश्यकता से बचा जाता है: यहाँ C99 में एक पूरी तरह से अलग कार्यान्वयन है।

आप सी में मूल समाधान को आसानी से कार्यान्वित भी कर सकते हैं क्योंकि आप फीफो के अधिकतम आकार को जानते हैं (मुझे लगता है कि यह कुछ (एन + 1)/2 है, लेकिन आपको इसे दोबारा जांचना होगा), आप कर सकते हैं कतारबद्ध श्रेणियों को पकड़ने के लिए एक अंगूठी बफर का उपयोग करें।

संपादित करें 2: यहां सी 99 में एक और समाधान है। यह केवल आधे लूप पुनरावृत्तियों को करने के लिए अनुकूलित किया गया है और केवल बिट oprations और जोड़ों का उपयोग करने के लिए, कोई गुणा या विभाजन नहीं है। यह भी अधिक संक्षेप में है, और इसमें परिणामों में 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); 
    } 
} 

(इस कोड को मैं शुरू से ही लिखने के लिए इरादा है, लेकिन यह मुझे कुछ समय उसके चारों ओर मेरे सिर लपेटो करने लग गए।)

Answer 2

Binary Heap सरणी के रूप में पहले से ही इस संरचना है। आप इस फॉर्म में अपनी सरणी को स्टोर करना चाहते हैं और अनुक्रमिक रूप से प्रिंट कर सकते हैं। नोड i के लिए, बच्चे 2i + 1, 2i + 2 हैं।

Answer 3

हमम ... आप मूल रूप से किसी प्रकार की अंतरिक्ष-भरने की वक्र की तलाश कर रहे हैं। मैं लगभग निश्चित हूं कि आप चालाक बिट-ट्विडलिंग के साथ ऐसा कर सकते हैं। आप मॉर्टन जेड-ऑर्डर या अहेनेंटाफेल इंडेक्सिंग के लिए इंडेक्स की गणना के तरीके को देख सकते हैं, जिसका उपयोग कुछ कैश-अनजान स्टैंसिल एल्गोरिदम में किया जाता है। मैंने कुछ साल पहले इस पर एक नज़र डाली थी, और अनुक्रमण जो आप वर्णन कर रहे हैं और बिट-ट्विडलिंग के साथ किया गया था।

Answer 4

यह 1/2 के लिए आसान है, है ना?

तो इसे बार-बार क्यों न करें, ताकि 1/4 1/2 का 1/2 हो और 1/8 1/2 का 1//2 हो?