फाइबोनैचि साक्षात्कार

फाइबोनैचि श्रृंखला की गणना एक क्लासिक एल्गोरिदमिक कार्य है, क्योंकि यह अक्सर साक्षात्कार में दिया जाता है जब वे यह सत्यापित करना चाहते हैं कि उम्मीदवार, सिद्धांत रूप में, कम से कम एल्गोरिदम में सक्षम है। मान लीजिए आप एक ही उम्मीदवार हैं। आपको यह कार्य दिया गया था: जावास्क्रिप्ट में, एक फ़ंक्शन fib(n) लिखें जो nth फाइबोनैचि संख्या देता है। हम मानते हैं कि शून्य फाइबोनैचि संख्या शून्य है। तर्क की वैधता की आवश्यकता नहीं है। आपके पास क्या विकल्प हैं?

1. आसान होने के लिए, और लोग आपके लिए पहुंचेंगे।

सबसे सरल उपाय एक भोज चक्र है।

 const fib = n => { let prev = 0, next = 1; while(n-- && (next = prev + (prev = next))); return prev; } 

एक चुटकुला। बेशक, आपको ऐसा लिखने की आवश्यकता नहीं है - जब तक कि निश्चित रूप से, आपको पूर्णकालिक पर्यवेक्षक की स्थिति के लिए साक्षात्कार नहीं दिया जाता है।

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ next = prev + next; prev = next - prev; } return prev; } 

क्या आप परिवर्तनशील कूपन से बाहर चल रहे हैं? cypok

ठीक है, ठीक है, और भी अधिक पठनीयता के लिए, आइए इसे लिखें:

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ let temp = next; next = prev + next; prev = temp; } return prev; } 

यह एक क्लासिक, सरल और सुरुचिपूर्ण विकल्प है। लेकिन शायद आप कुछ अन्य अवधारणाओं के अपने ज्ञान का प्रदर्शन करना चाहते हैं? उदाहरण के लिए ...

2. पुनरावृत्ति को समझने के लिए, आपको पुनरावृत्ति को समझना चाहिए

उदाहरण के लिए, हाँ, आप प्रदर्शित कर सकते हैं कि आप पुनरावृत्ति कर सकते हैं। उदाहरण के लिए, इस तरह:

 const fib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } 

इस विकल्प को याद रखें। यह करने योग्य नहीं है। यह नहीं होना चाहिए। यह असंभव है। कभी नहीं। यह पिल्लों को मारने से भी बदतर है, और एक छोटे से प्रलय के बराबर है।

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

O- संकेतन की खुरदरी भाषा में व्यक्त, इस तरह के समाधान में O (e ⁿ ) की समय जटिलता है। यही है, इस फ़ंक्शन का निष्पादन समय बढ़ता एन के साथ तेजी से बढ़ता है। यही है, जब n से बढ़ता है , तो निष्पादन समय बढ़ता है। मोटे तौर पर, अगर fib(45) आपको एक घंटा इंतजार करना था, तो fib(46) आप दो घंटे, fib(47) - 4 घंटे और इसी तरह इंतजार करेंगे। मैंने इतने विस्तार से चबाया कि हर पाठक, यहां तक ​​कि एक टाइपसेटर जिसने पहली बार स्क्रिप्ट लिखने में अपना हाथ आजमाया, वह स्थिति की भयावहता का एहसास कर सका।

यह सही है, लेकिन बहुत अशिष्ट है। आप फ़ंक्शन कॉल की संख्या का अधिक सटीक अनुमान प्राप्त कर सकते हैं ~ (1 + sqrt (5)) फ़ाइबर (n) और सुंदर टिप्पणी "भोली पुनरावर्ती पद्धति का उपयोग करके फाइबोनैचि संख्या की गणना करने के लिए, आपको फ़िबोनैचि संख्या की तुलना में 3.2 गुना अधिक फ़ंक्शन कॉल की आवश्यकता होती है।" Taus

और इसकी गणना के लिए हमें एक और विधि मिलती है। आपको बस भोली पुनरावर्ती विधि को चलाने की ज़रूरत है, फ़ंक्शन कॉल की संख्या की गणना करें और 3.2 से विभाजित करें! Cerberuser

यदि आपको एक साक्षात्कार के दौरान इस समस्या का पुन: समाधान करने की आवश्यकता है, तो यह सबसे अधिक संभावना है। रैखिक समय में काम करने वाली "सही" पुनरावृत्ति लग सकती है, उदाहरण के लिए, इस तरह:

 const fib2 = n => { if(n == 0){ return [0, 1]; }else{ const [prev, next] = fib2(n - 1); return [next, prev + next]; } } const fib = n => fib2(n)[0]; 

संक्षेप में: इस तथ्य के बावजूद कि फाइबोनैचि संख्याएं पुनरावृत्ति का एक उत्कृष्ट, पाठ्यपुस्तक उदाहरण हैं, वास्तव में यह पुनरावृत्ति को लागू करने के लिए सबसे सुविधाजनक मामला नहीं है। लेकिन आप कुछ और ज्ञान दिखाने की कोशिश कर सकते हैं।

3. स्मारक समारोह

एक जादुई तरीका है जो अंतिम पैराग्राफ से एक राक्षसी अप्रभावी समाधान को संभावित रूप से बहुत जल्दी (हालांकि समस्याओं के बिना नहीं) में बदल देता है। उसका नाम संस्मरण है। और अगर आप रूसी बोलते हैं - हम उन्हें फिर से गणना करने के बजाय पिछले कॉल के परिणामों को याद करते हैं।

मूल रूप से, हम उस समाधान के अंदर कुछ भी नहीं बदल सकते हैं - बस एक memoize आवरण फ़ंक्शन जोड़ें। यहाँ, स्पष्टता के लिए, मैं एक एकल तर्क के साथ फ़ंक्शन के लिए इसके सरलीकृत संस्करण का उपयोग करता हूं।

 //   ,       ,     const oldFib = n => { if(n <= 1){ return n; }else{ return oldFib(n - 1) + oldFib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

देखा! अब fib फ़ंक्शन को बंद करने के माध्यम से cache ऑब्जेक्ट तक पहुंच है। यदि यह एक ऐसे तर्क के साथ कहा जाता है जो पहले सामना नहीं किया गया है, तो परिकलित मान cache में संग्रहीत होता है। एक ही तर्क के साथ नए फ़ंक्शन कॉल के साथ, मूल्य को पुनर्गणना करने की आवश्यकता नहीं है, यह बस कैश से लिया जाएगा। "खराब" पुराने fib फ़ंक्शन की मुख्य समस्या यह थी कि इसमें समान मूल्य कई बार पुनर्गणित किए गए थे। उदाहरण के लिए, fib(45) गणना करने के लिए एक बार f(44) , दो बार f(43) , तीन बार f(42) , पांच बार f(41) , और इसी तरह की गणना करना आवश्यक था।


तो, अब पिछले मानों की गणना एक बार की जाएगी, और जब वे फिर से अनुरोध किए जाएंगे - बस कैश से लिया गया है। क्या आप कल्पना कर सकते हैं कि चालीस-पांचवें फाइबोनैचि संख्या की गणना हम कितनी तेजी से कर सकते हैं? गंभीरता से, आपको क्या समय लगता है?

वास्तव में - थोड़ा धीमा। मैंने जानबूझकर एक क्लासिक गलती की, अक्सर पुनरावर्ती कार्यों को याद करते समय बनाया गया था। जब fib(45) "हुड के नीचे" कहा जाता है, तो oldFib(45) कहा जाता है, जो अपनी जरूरतों के लिए oldFib(44) और oldFib(43) को oldFib(43) ... क्या आपको कैच का अहसास है? इसके बाद, पहले से ही एक नियमित, गैर-ज्ञापन फ़ंक्शन के लिए कॉल हैं। बेशक, जब fib(45) फिर से कॉल किया जाता है, तो हम तुरंत कैश से परिणाम प्राप्त करते हैं - हालांकि, पहली कॉल में तेजी नहीं हुई। इसे ठीक करने के लिए, आपको अभी भी रिंच के नीचे oldFib प्राप्त oldFib :

 const oldFib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

अद्भुत! अब पहली कॉल fib(45) एक लूप के साथ संस्करण की तुलना में गति पर काम fib(45) । और आगे की चुनौतियां आम तौर पर निरंतर समय में काम करेंगी ... उफ़! फिर से धोखा हुआ। कुंजी द्वारा किसी वस्तु की संपत्ति का मूल्य प्राप्त करना एक त्वरित ऑपरेशन है, लेकिन अभी भी O (1) केवल औसत पर है, सबसे खराब स्थिति में यह O (n) से नीचा दिखा सकता है। इसे बहुत अच्छा बनाने के लिए, हमारे मामले में हम ऑब्जेक्ट से सरणी में cache के प्रकार को बदल सकते हैं।

बेशक, किसी को यह नहीं भूलना चाहिए कि संस्मरण के लिए स्मृति की आवश्यकता होती है। और जब हम समय की जटिलता को कम करते हैं, तो स्मृति जटिलता O (1) से O (n) तक बढ़ती है।

हम और कैसे दिखा सकते हैं? उदाहरण के लिए, गणित के अपने गहन ज्ञान का प्रदर्शन

4. मिस्टर बिनेट

पुनरावृत्ति संबंधों को स्पष्ट सूत्रों में बदलने के लिए एक विशेष, अद्भुत विज्ञान है। यहां हम इसके विवरण में नहीं जाएंगे। हम केवल यह कहेंगे कि फाइबोनैचि संख्याओं के लिए, काफी सरल तर्कों का उपयोग करके, हम निम्नलिखित सूत्र को प्राप्त कर सकते हैं, जिसे Binet सूत्र के रूप में जाना जाता है:

$$

$$F_n = \ frac {\ left (\ frac {1 + sqrt5} {2} \ right) ^ n - \ बाएँ (\ frac {1 - \ sqrt5} {2} \ right) ^ n} {sqrt5}$$

हालाँकि, यह काफी गणितीय भाषा है, हम इसे जावास्क्रिप्ट में लिखते हैं:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; const b = (1 - 5 ** 0.5) / 2; return (a ** n - b ** n) / 5 ** 0.5; } 

पहले कुछ नंबरों पर ड्राइव करते हैं। महान, सब कुछ काम करने लगता है। यहां 13 है, यहां 21 है, यहां 34 है, यहां है ... 54.9999999999999999 है?

हां, निश्चित रूप से, ऐसा परिणाम तर्कसंगत है। बिनेट का सूत्र गणितीय रूप से सटीक है, लेकिन कंप्यूटर परिमित सटीकता के अंशों के साथ संचालित होता है, और उनके साथ संचालन के दौरान एक त्रुटि जमा हो सकती है, जो इस मामले में हुआ था। हालाँकि, हम इसे ठीक कर सकते हैं। यह जानकर कि अंश में घटाया गया परिमाण हमेशा छोटा होगा, हम निम्न अवस्था के लिए सूत्र को सरल बना सकते हैं:

$$

$$F_n = \ left \ lfloor \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n} {\ sqrt5} \ right \ rceil$$

यहां अजीब अधूरा वर्ग कोष्ठक का अर्थ है निकटतम पूर्णांक, अर्थात गोलाई। हमारे कोड को फिर से लिखें:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; return Math.round(a ** n / 5 ** 0.5); } 

हाँ, यह बहुत बेहतर है हम 55 और 89 दोनों देख सकते हैं, और यहां तक ​​कि मेरी पसंदीदा फिबोनाची संख्या 144 है (जो मुझे पसंद है क्योंकि यह बारह वर्गों के बराबर है)। संख्या 76 तक सब कुछ ठीक रहेगा। जो 3416454622906707 के बराबर होना चाहिए, और हमारा कार्य 3416454622906706 की गणना करेगा। क्योंकि भिन्नात्मक संख्याओं की सीमित सटीकता की समस्या दूर नहीं हुई है, हमने इसे और गहरा कर दिया और उम्मीद की कि यह नहीं आएगी। जैसा कि इस उदाहरण से पता चलता है, वे व्यर्थ में आशा करते थे।

वास्तव में, हम इस पद्धति को बचाने के लिए कुछ और कर सकते हैं। लेकिन इसके बारे में और नीचे। इस बीच - एक तरफ मजाक करता है। चलो कठोर, कट्टर और क्रूर विधि के बारे में बात करते हैं।

5. सफेद खरगोश का पालन करें।

वे कहते हैं कि यदि आपको कोई समस्या है और आपके पास यह विचार आया है कि आप इसे नियमित अभिव्यक्तियों के साथ हल कर सकते हैं, तो अब आपको दो समस्याएं हैं। इसके विपरीत मैट्रिसेस नियमित अभिव्यक्ति हैं। कई समस्याएं, यदि मैट्रिसेस की भाषा में सुधार की जाती हैं, तो बस अपने आप ही हल हो जाती हैं।

फिबोनाची संख्याओं के लिए, मैट्रिक्स भाषा में उनके लिए आप यह स्पष्ट पहचान लिख सकते हैं:

$$

$$\ start {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} \ start {pmatrix} F_ {n - 1} \\ F_n \ end {pmatrix} = \ start {pmatrix}: F_n \\ F_ {n +1} \ n अंत {pmatrix}$$

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

$$

$$\ start {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n \ start {pmatrix} 0 \\ 1 \ end {pmatrix} = \ start {pmatrix} F_n \\ \ _ {n + 1} \ अंत {pmatrix}$$

आप वैक्टर को त्यागकर इसे थोड़ा और सरल बना सकते हैं। वास्तव में, सभी आवश्यक मूल्य मैट्रिक्स में ही निहित हैं:

$$

$$\ start {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ start {pmatrix} F_ {n-1} और F_ {n} \\ F_ {n} & F_ / n + 1 } \ end {pmatrix}$$

महान, है ना? यह समझने के लिए बना हुआ है कि क्या है, सद्भाव के लिए, अगर वह एक धर्मज्ञ नहीं है। मेरा मतलब है - नीले रंग से ऐसी कठिनाइयाँ क्यों हैं। और जवाब सरल है - तेजी से घातांक।

गणना करने के लिए कितने प्राथमिक गुणन हैं, कहते हैं, 2 ¹⁰ ? एक सामान्य व्यक्ति नौ कहेगा। दो बार - चार। दो बार चार - आठ। दो बार आठ सोलह है। और इसी तरह। एक चालाक व्यक्ति कहेगा कि चार।

$$

$$2 \ cdot 2 = 4 \\ 4 \ cdot 4 = 16 \\ 2 \ cdot 16 = 32 \\ 32 \ cdot 32 = 1024$$

प्रोग्रामर कहेगा। वह इस संख्या को दिल से याद करता है, और कुछ भी गुणा करने की आवश्यकता नहीं है। हालाँकि, हमने ऊपर संस्मरण के मुद्दों पर चर्चा की।

तो, एक त्वरित घातांक भी मैट्रिसेस पर लागू होता है, और इस तरह से हमें हमारे फ़ंक्शन के असममित समय की जटिलता को ओ (एन) से ओ (लॉग एन) तक कम करने की अनुमति मिलती है। और यह बहुत अच्छा है - जब तक, निश्चित रूप से, यह जटिलता वास्तव में हमारे लिए बहुत महत्वपूर्ण है। कोड लिखते हैं:

 //    ,          const mul = ( [ [a1, a2], [a3, a4] ], [ [b1, b2], [b3, b4] ]) => [ [a1 * b1 + a2 * b3, a1 * b2 + a2 * b4], [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4] ]; const matrix = [ [0, 1], [1, 1] ]; // ,   const id = [ [1, 0], [0, 1] ] const fib = n => { let result = id; const bits = n.toString(2); //        for(const bit of bits){ result = mul(result, result); if(bit == "1"){ result = mul(result, matrix); } } return result[1][0]; } 

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

पुनश्च

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

और क्या सबसे दिलचस्प है: यदि आप ध्यान से देखते हैं कि प्रक्रिया में कौन से नंबर प्राप्त किए जाएंगे, कौन से संचालन किए जाएंगे, तो यह स्पष्ट हो जाएगा कि यह विधि एक ही मैट्रिक्स गुणन है, केवल एक अलग पहलू के तहत। एकमात्र अंतर यह है कि क्या हम संख्या को दो-आयामी सरणियों में या एक विशेष वर्ग के ऑब्जेक्ट के क्षेत्रों में संग्रहीत करते हैं।

वह सब है। अगर आपको लगता है कि मैंने नंबर खोजने के लिए कुछ अन्य दिलचस्प तरीके याद किए हैं, जिनकी किसी को ज़रूरत नहीं है, तो टिप्पणियों में इसके बारे में लिखना सुनिश्चित करें।

तेजी से दोहरीकरण जैसी एक विधि भी है। यह O (लॉग) में मैट्रिक्स गुणन की तरह काम करता है, लेकिन एसिम्पोटिक्स (और व्यवहार में) में एक छोटे से स्थिरांक के साथ। संक्षेप में, तब दो फार्मूले का उपयोग किया जाता है, जिस पर भरोसा करते हुए व्यक्ति जल्दी से दो बार कम सूचकांकों पर पुन: आवर्ती हो सकता है:

एफ _{2 एन} = एफ _एन * (2 * एफ _{एन + 1} - एफ _एन )
एफ _{2 एन + 1} = एफ _एन ² + एफ _{एन + 1} ²

वैसे, कार्यान्वयन काफी कॉम्पैक्ट है।

विभिन्न तरीकों की गति की तुलना

just_maksim