वास्तव में, पहले दो फाइबोनैचि संख्याएं पूर्वनिर्धारित हैं। पहली फाइबोनैचि संख्या 0 है और दूसरी फाइबोनैचि संख्या 1 है। शून्य-आधारित अनुक्रमण के साथ और यह मानते हुए कि फाइबोनैचि संख्याएं एक सरणी में हैं, फिर:
सूचकांक पर 0 , फाइबोनैचि संख्या है 0 , ( पूर्वनिर्धारित ) ;सूचकांक पर 1 , फाइबोनैचि संख्या है 1 , ( पूर्वनिर्धारित ) ;
सूचकांक पर दो , फाइबोनैचि संख्या है 1 = 1 + 0 , ( परिभाषा से ) ;
सूचकांक पर 3 , फाइबोनैचि संख्या है दो = 1 + 1 , ( परिभाषा से ) ;
सूचकांक पर 4 , फाइबोनैचि संख्या है 3 = दो + 1 , ( परिभाषा से ) ;
सूचकांक पर 5 , फाइबोनैचि संख्या है 5 = 3 + दो , ( परिभाषा से ) ;
सूचकांक पर 6 , फाइबोनैचि संख्या है 8 = 5 + 3 , ( परिभाषा से ) ;
सूचकांक पर 7 , फाइबोनैचि संख्या है 13 = 8 + 5 , ( परिभाषा से ) ;
सूचकांक पर 8 , फाइबोनैचि संख्या है इक्कीस = 13 + 8 , ( परिभाषा से ) ;
सूचकांक पर 9 , फाइबोनैचि संख्या है 3. 4 = इक्कीस + 13 , ( परिभाषा से ) ;
और इसी तरह।
प्रोग्रामिंग में, इन फाइबोनैचि संख्याओं के लिए शून्य-आधारित अनुक्रमणिका के लिए चर n, और नहीं i का उपयोग किया जाता है। और उसके साथ, पहले बारह फाइबोनैचि संख्याएँ हैं:
| 0 | 1 | 1 | दो | 3 | 5 | 8 | 13 | इक्कीस | 3. 4 | 55 | 89 |
| 0 | 1 | दो | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ग्यारह |
तालिका में दूसरी पंक्ति शून्य-आधारित अनुक्रमणिका देती है, जिनमें से प्रत्येक में प्रोग्रामिंग में चर n होगा। पहली पंक्ति संबंधित फाइबोनैचि संख्याएँ देती है। तो, फाइबोनैचि संख्याएं केवल कोई संख्या नहीं हैं। पहली फिबोनाची संख्या के लिए मूल परिभाषा 0 से शुरू होती है और दूसरी फाइबोनैचि संख्या के लिए 1 होती है। बाकी नंबर वहीं से तैयार किए जाते हैं।
फाइबोनैचि संख्याएं O(n) समय में और O(1) समय में भी उत्पन्न की जा सकती हैं। O(n) समय के लिए, यदि n उदाहरण के लिए 12 है, तो पहले बारह फाइबोनैचि संख्याएँ उत्पन्न होंगी। O(1) समय के लिए, केवल एक फाइबोनैचि संख्या उत्पन्न होती है। उदाहरण के लिए, यदि n 6 है, तो फाइबोनैचि संख्या 8 उत्पन्न होगी।
यह आलेख जावा में फाइबोनैचि संख्याओं के उत्पादन के इन दो तरीकों की व्याख्या करता है।
फाइबोनैचि संख्या के लिए सूत्र
फाइबोनैचि संख्या के लिए एक गणितीय सूत्र है। यह सूत्र तीन पंक्तियों या एक पंक्ति में लिखा जा सकता है। तीन पंक्तियों में लिखा है-
जहां एफ एन शून्य-आधारित n . पर फाइबोनैचि संख्या है वां अनुक्रमणिका। इस प्रकार फाइबोनैचि संख्या को परिभाषित किया गया है।
O(n) समय . में फाइबोनैचि संख्याओं का निर्माण
यदि फाइबोनैचि संख्याओं को O(3) बार में बनाया जाना है, तो 0, 1, 1 की संख्याएँ उत्पन्न होंगी; वे पहले तीन फाइबोनैचि संख्याएं हैं। अंतिम शून्य-आधारित n वां यहाँ सूचकांक 2 है। यदि फाइबोनैचि संख्याओं को O(7) बार में बनाया जाना है, तो 0, 1, 1, 2, 3, 5, 8 संख्याएँ उत्पन्न होंगी; वे पहले सात फाइबोनैचि संख्याएं हैं। अंतिम शून्य-आधारित n वां यहाँ सूचकांक 6 है। यदि फाइबोनैचि संख्याओं को O(n) समय में उत्पन्न करना है, तो 0, 1, 1, 2, 3, 5, 8 - - -, संख्याएँ उत्पन्न होंगी; वे पहली n फाइबोनैचि संख्याएँ हैं। अंतिम शून्य-आधारित n वां यहाँ सूचकांक n-1 है।
पहली n फाइबोनैचि संख्याएँ उत्पन्न करने के लिए एक वर्ग में जावा विधि है:
कक्षा फिबोनैकी {शून्य फिबोनैकी ( पूर्णांक [ ] पी ) {
पूर्णांक एन = पी। लंबाई ;
यदि ( एन > 0 )
पी [ 0 ] = 0 ;
यदि ( एन > 1 )
पी [ 1 ] = 1 ;
के लिये ( पूर्णांक मैं = दो ; मैं < एन ; मैं ++ ) { //n=0 और n=2 पर विचार किया गया है
पूर्णांक कर्नो = पी [ मैं - 1 ] + पी [ मैं - दो ] ;
पी [ मैं ] = कर्नो ;
}
}
}
फिबोनाची वर्ग निजी है। फाइबोनैचि () विधि सरणी पी लेती है और शून्य लौटाती है। विधि सरणी की लंबाई निर्धारित करके शुरू होती है। n की यह लंबाई आवश्यक फाइबोनैचि संख्याओं की संख्या है। पहली और दूसरी फाइबोनैचि संख्याओं को स्पष्ट रूप से निर्धारित किया जाता है और सरणी में पहले और दूसरे स्थान पर रखा जाता है।
तीसरे (सूचकांक, n = 2) से शुरू होने वाली शेष फाइबोनैचि संख्याएं फॉर-लूप में निर्धारित की जाती हैं और सरणी में उनकी स्थिति में रखी जाती हैं। तो, फ़ंक्शन को शून्य वापस करना होगा। फॉर-लूप में मुख्य विवरण पिछले दो नंबर जोड़ता है।
स्पष्टता के उद्देश्य से सूचकांक चर, i, का उपयोग n के बजाय किया गया है।
एक उपयुक्त जावा मुख्य वर्ग (जावा मुख्य विधि के साथ) है:
जनता कक्षा मुख्य {जनता स्थिर शून्य मुख्य ( डोरी args [ ] ) {
पूर्णांक एम = 12 ;
पूर्णांक [ ] आगमन = नया पूर्णांक [ एम ] ;
फाइबोनैचि ओब्जो = नया फिबोनैकी ( ) ;
ओबीजे फिबोनैकी ( आगमन ) ;
के लिये ( पूर्णांक मैं = 0 ; मैं < एम ; मैं ++ )
व्यवस्था . बाहर . प्रिंट ( आगमन [ मैं ] + '' ) ;
व्यवस्था . बाहर . प्रिंट्लन ( ) ;
}
}
फाइबोनैकी () विधि द्वारा संख्याओं का उत्पादन करने के बाद, जावा मुख्य विधि उन्हें पढ़ती है।
लगातार समय में एक फाइबोनैचि संख्या का निर्माण
एक गणितीय सूत्र है जिसका उपयोग फाइबोनैचि संख्या उत्पन्न करने के लिए किया जा सकता है, जब संबंधित शून्य-आधारित सूचकांक दिया जाता है, n। सूत्र है:
जहाँ n शून्य-आधारित सूचकांक है और Fib एन संबंधित फाइबोनैचि संख्या है। ध्यान दें कि समीकरण के दायीं ओर, यह 5 का वर्गमूल नहीं है जिसे घात n तक बढ़ाया जाता है; यह कोष्ठकों में व्यंजक है जिसे घात n तक बढ़ा दिया गया है। ऐसे दो भाव हैं।
यदि n 0 है, तो फाइब एन 0 होगा। यदि n 1 है, तो Fib एन होगा 1. यदि n 2 है, Fib एन होगा 1. यदि n 3 है, Fib एन 2 होगा। यदि n 4 है, Fib एन 3 होगा - और इसी तरह। पाठक इस सूत्र को n के लिए विभिन्न मानों को प्रतिस्थापित करके और मूल्यांकन करके गणितीय रूप से सत्यापित कर सकता है।
जब कोडित किया जाता है, तो यह सूत्र n के लिए केवल एक फाइबोनैचि संख्या उत्पन्न करेगा। यदि एक से अधिक फाइबोनैचि संख्याओं की आवश्यकता होती है, तो सूत्र के कोड को अलग-अलग संगत अनुक्रमितों में से प्रत्येक के लिए एक बार कॉल करना होगा।
जावा में, केवल एक फाइबोनैचि संख्या उत्पन्न करने की विधि है:
आयात जावा.लैंग.* ;कक्षा मिथ्या {
दोहरा फाइबनो ( पूर्णांक एन ) {
दोहरा एफआईबीएन = ( गणित . पॉव ( ( 1 + गणित . वर्ग ( 5 ) ) / दो , एन ) - गणित . पॉव ( ( 1 - गणित . वर्ग ( 5 ) ) / दो , एन ) ) / गणित . वर्ग ( 5 ) ;
वापसी एफआईबीएन ;
}
}
java.lang.* पैकेज को प्रोग्राम की शुरुआत में इम्पोर्ट किया जाना था। ऐसा इसलिए है क्योंकि पैकेज में गणित वर्ग है, जिसमें शक्ति (पाउ) और वर्गमूल (वर्ग) विधियां हैं। यहां कस्टम जावा विधि सीधे गणित सूत्र को लागू करती है।
इस फ़ंक्शन के लिए समय जटिलता ओ (1) है, एक मुख्य ऑपरेशन की निरंतर प्रसिद्धि। उपरोक्त विधि के लिए जावा मुख्य विधि के साथ एक उपयुक्त जावा मुख्य वर्ग है:
जनता कक्षा मुख्य {जनता स्थिर शून्य मुख्य ( डोरी args [ ] ) {
पूर्णांक एन = ग्यारह ;
फाइब ओब्जो = नया मिथ्या ( ) ;
दोहरा सही = ओबीजे फाइबनो ( एन ) ;
व्यवस्था . बाहर . प्रिंट्लन ( सही ) ;
}
}
सूचकांक n = 11 भेजा जाता है और फाइबोनैचि संख्या, 89 लौटा दी जाती है। आउटपुट है:
89.00000000000003अनावश्यक दशमलव अंकों को हटाया जा सकता है, लेकिन यह कुछ और समय के लिए चर्चा है।
निष्कर्ष
फाइबोनैचि संख्याएं पूर्ण संख्याओं का एक विशेष क्रम है। वर्तमान संख्या प्राप्त करने के लिए, तत्काल पिछली दो संगत संख्याएँ जोड़ें। पहले दो फाइबोनैचि संख्याएं, 0 के बाद 1, पूरे अनुक्रम के लिए पूर्व-घोषित हैं। शेष फाइबोनैचि संख्याएँ वहाँ से उत्पन्न होती हैं।
इंडेक्स 2 से फाइबोनैचि संख्याएं उत्पन्न करने के लिए, जो इंडेक्स n-1 से मेल खाती है, प्रिंसिपल स्टेटमेंट के साथ फॉर-लूप का उपयोग करें:
पूर्णांक कर्नो = पी [ मैं - 1 ] + पी [ मैं - दो ] ;जहां currNo वर्तमान फाइबोनैचि संख्या है और P n संख्याओं को संग्रहीत करने के लिए सरणी है।
किसी भी शून्य-आधारित सूचकांक n से केवल एक फाइबोनैचि संख्या उत्पन्न करने के लिए, गणितीय सूत्र का उपयोग करें:
