संख्याओं की गणना करें जैसे कि किसी संख्या को फिबोनैकी संख्या के रूप में सेट बिट्स की गिनती होनी चाहिए?

Question

एक सीमा [x, y] को देखते हुए संख्याओं की संख्या मिलती है जैसे कि किसी संख्या में फिबोनैकी संख्या के रूप में सेट बिट्स की गिनती होनी चाहिए?

उदाहरण के लिए: [15,17]

15 - 1111 - Count of bits is 4 - (4 is not a fibonacci number) 

16 - 10000 - Count of bits is 1 - (1 is a fibonacci number) 

17 - 10001 - Count of bits is 2 - (2 is a fibonacci number) 

तो जवाब 2 (16,17)

जाहिर है हम सेट बिट्स गिनती और जाँच करें कि क्या इसके कि क्या (5x^2 +/- 4) हालत का उपयोग कर एक fibonacci संख्या एक पूर्ण वर्ग है है ..

नोट: यह एक साक्षात्कार प्रश्न है। साक्षात्कारकर्ता उपर्युक्त दृष्टिकोण से संतुष्ट नहीं था।

क्या हम कोई बेहतर कर सकते हैं?

Answer 1

आप प्रत्येक फाइबोनैकी संख्या (एक सीमा तक, मैं उस पर पहुंच जाऊंगा) के लिए इसे उलटा और गिन सकता हूं, यह कितनी संख्याएं "उत्पादन" सीमा में हैं।

कहें कि एक फाइबोनैकी संख्या है (जाहिर है आप केवल उन प्रयासों को ही देखेंगे जो फाइबोनैकी संख्याएं हैं, जो उत्पन्न करने के लिए तुच्छ हैं)। वहाँ कितने संख्याएं हैं जिनके पास बिट्स सेट हैं और एक्स और वाई के बीच हैं? इस countBetween(x, y, k) पर कॉल करें। केवल ऊपरी बाउंड तक गिनना आसान है, इसलिए countBetween(x, y, k) = countUpTo(y, k) - countUpTo(x, k) परिभाषित करें (विशेष ऊपरी सीमा को मानते हुए जिसे आप आसानी से बदल सकते हैं)।

countUpTo(x, k) सरल है जब x दो की शक्ति है, अर्थात् log(x) nCr k। यदि x दो की एक शक्ति नहीं है, तो एक्स से कम दो कम, q और

बाकी ऊपर एक्स के दो श्रेणियों में इसे विभाजित,

1. सर्वोच्च शक्ति।

q अप करने के लिए पहले भाग आप पहले से ही गणना कर सकते हैं, दूसरे भाग है एक अग्रणी 1 और फिर कुछ नई रेंज है कि 0 पर (1 हटाने के बाद) शुरू होता है, तो आप countUpTo(x - q, k - 1) गणना कर सकते हैं।

यह आपको countUpTo की एक पुनरावर्ती परिभाषा देता है, और यह सोचते हैं आप कम से कम समय में O(a nCr b)a nCr b लागू कर सकते हैं, इस एल्गोरिथ्म हर नंबर पर जाकर और यह परीक्षण के बराबर नहीं है।

सीमा के लिए, जाहिर है कि आप ऊपरी बाउंड की लंबाई से अधिक बिट्स सेट नहीं कर सकते हैं, इसलिए आप वहां रुक सकते हैं।

---

उदाहरण: countBetween(1024, 1000000, 5) = 15251

हम countUpTo(1024, 5) और countUpTo(1000000, 5) की जरूरत है। 0xF4240, वहाँ में दो की सबसे बड़ी शक्ति: countUpTo(1024, 5) एक आधार मामला है, परिणाम लॉग है (1024) nCr 5 = 252.

countUpTo(1000000, 5) के लिए, यह देखना आसान क्या हो रहा है बनाने के लिए हेक्साडेसिमल में 1000000 बारे में निश्चित रूप से 0x80000 है, लॉग (0x80000) एनसीआर 5 = 11628 का योगदान और 0x80000 से 0xF4240 तक हिस्सा छोड़ रहा है। उस भाग को countUpTo(0x74240‬, 4) के साथ गिना जा सकता है - ऊपरी बिट हमेशा उस सीमा में सेट होता है, इसलिए इसे बाध्य और सेट बिट्स की संख्या समायोजित करके समस्या से हटा दिया जाता है।

0x74240 में दो की सबसे बड़ी शक्ति 0x40000 है, जो countUpTo(0x34240‬, 3) छोड़कर लॉग (0x40000) एनसीआर 4 = 3060 का योगदान देती है।

0x34240 में दो की सबसे बड़ी शक्ति 0x20000 है, लॉग (0x20000) का योगदान दे रही है nCr 3 = 680, countUpTo(0x14240‬, 2) छोड़कर।

0x14240 में दो की सबसे बड़ी शक्ति 0x10000 है, जो countUpTo(0x4240‬, 1) छोड़कर लॉग (0x10000) एनसीआर 2 = 120 का योगदान देती है।

0x4240 में दो की सबसे बड़ी शक्ति 0x4000 है, जो लॉग (0x4000) एनसीआर 1 = 14. का योगदान देती है। यह countUpTo(0x240‬, 0) छोड़ देता है जो 1 है क्योंकि सेट करने के लिए कोई बिट नहीं है और सेट करने का केवल एक ही तरीका है बिट्स।

उन सब को जोड़े अप, 11628 + 3060 + 680 + 120 + 14 + 1 = 15503. लोअर बाउंड से घटाना 252 और हम 15251.

मिल उदाहरण यथोचित कम संख्या का उपयोग करता है ताकि आप आसानी से उन्हें सत्यापित कर सकते हैं

int count = 0; 
for (int i = 1024; i < 1000000; i++) 
    if (__popcnt(i) == 5) count++; 
std::cout << count << std::endl;