फाइबोनैचि सम संख्याएँ

एक साक्षात्कार के लिए एक फिबोनाची पोस्ट के तहत एक टिप्पणी से प्रेरित। उपयोगकर्ता pavellyzhin ने निम्नलिखित साक्षात्कार कार्य ( टिप्पणी ) का उल्लेख किया:

एक साल से अधिक समय पहले, "php-programmer" ने रिक्ति पर प्रतिक्रिया दी, उन्होंने टीके को भेजा और फिबोनाची से एक कार्य था: 1 से 10000 तक की रेंज में सभी फाइबोनैचि संख्याओं का चयन करें । (For) लूप का उपयोग करके निर्णय लिया गया। वहां, उपयोगकर्ताओं के निकटतम जन्मदिनों का चयन करने के लिए, कुछ बनाने के लिए SQL क्वेरी बनाने के लिए भी आवश्यक था, मुझे बस किसी प्रकार का फ़ंक्शन याद नहीं है और लिखना नहीं है। मैंने सब कुछ किया, भेजा। उन्होंने एक उत्तर भेजा: "परीक्षण कार्य के परिणामों के अनुसार आपको स्वीकार नहीं किया जाता है।" जो वास्तव में उन्हें पसंद नहीं था वह नहीं लिखा गया था। अब मैं बैठा हूं और सोच रहा हूं, शायद फिबोनाची के कारण ही मैंने उड़ान भरी ... :)

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

सिद्धांत बनाना

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

$$

$$1.1, {\ bf 2}, 3.5, {\ bf 8}, 13.21, {\ bf 34}, 55.89, {\ bf 144}, \ ldots$$

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

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

हम यह साबित करते हैं कि "हर तीसरी फिबोनाची संख्या सम है, और प्रत्येक पूर्ववर्ती संख्या ऐसी विषम है।"

• बेस इंडक्शन । पहले दो रिट्रेसमेंट नंबर $$$1.1$ - विषम, तीसरा नंबर $$$2$ - सम
• परिकल्पना । मान लीजिए कि 3 के कुछ फाइबोनैचि संख्याओं तक यह सच है कि हर तीसरा भी है, और दो पूर्ववर्ती यह विषम हैं।
• प्रेरण कदम । परिकल्पना से अंतिम एक तक की संख्या विषम है, क्योंकि यह सम के साथ विषम के योग से प्राप्त होता है, उस संख्या का अनुसरण पहले से ही विषम है, क्योंकि यह विषम के साथ सम के योग से प्राप्त होता है, और अगले के बाद भी होता है, क्योंकि उसके लिए प्राप्त दो पिछले वाले विषम हैं, निर्माण द्वारा उसकी संख्या 3 की एक बहु है, यह सम है, और दो पिछले वाले विषम हैं।

इस तरह हम गणितीय गणनाओं का सहारा लिए बिना भी अपना अनुमान साबित कर सकते हैं। आप इस विचार को औपचारिक रूप दे सकते हैं, साथ ही साथ हर तीसरे फाइबोनैचि संख्या की गणना के लिए एक सूत्र प्राप्त कर सकते हैं $$$F_ {n + 3}$ से $$$F_n$ और $$$F_ {n + 1}$ । पुनरावर्ती संबंध का उपयोग करना $$$F_ {n + 2} = F_ {n + 1} + F_ {n}$ हमें मिलता है:

$$

$$F_ {n + 3} = F_ {n + 2} + F_ {n + 1} = 2 F_ {n + 1} + F_n$$

तो अगर $$$F_n$ - तब भी $$$F_ {n + 3}$ इस सूत्र के आधार पर भी। दिया है कि $$$F_3 = 2$ , फिर हर तीसरा फाइबोनैचि संख्या वास्तव में भी है, जो हमारे अनुमान का हिस्सा है। यहां आपको यह सुनिश्चित करने की आवश्यकता है कि हम अन्य सम संख्याओं को याद नहीं करते हैं, अर्थात्। वे सभी के गुणक हैं 3. अपने सरल विचार के लिए जन्नत को धन्यवाद, क्योंकि इसके लिए उपरोक्त सूत्र से $$$F_ {n + 3}$ यह भी है कि अगर $$$F_n$ - अजीब तो $$$F_ {n + 3}$ विषम भी है, इसलिए हम संख्याओं के साथ उस संख्या को प्राप्त करते हैं $$$3k-2,3k-1, k \ में \ mathbb {N}$ - विषम (प्रेरण द्वारा, से शुरू करें $$$F_1 = F_2 = 1$ - विषम), और $$$3k, k \ in \ mathbb {N}$ - यहां तक ​​कि, जो सभी फाइबोनैचि संख्याओं को कवर करता है, जिसका अर्थ है कि हम वास्तव में सभी सम संख्याओं को कवर करते हैं।

एक और तरीका है, क्योंकि यह दिखाना संभव होगा कि संख्याएं भी नहीं हैं। मान लीजिए कि एक संख्या मौजूद है $$$F_m$ - और भी $$$0 \ not \ equiv m \ mod 3$ तो $$$m = 3k - 1$ या $$$m = 3k + 1$ जहाँ $$$k$ - किसी प्रकार का प्राकृतिक।

आइए हम मूल पोस्ट से फाइबोनैचि संख्याओं के मैट्रिक्स प्रतिनिधित्व की ओर मुड़ें

$$

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

दोनों भागों के निर्धारक की गणना, हम प्राप्त करते हैं

$$

$$(-1) ^ n = F_ {n + 1} F_ {n-1} -F_n ^ 2$$

यह संख्याओं के विभाजकों का अनुसरण करता है $$$F_ {n + 1}, F_n$ और $$$F_ {n-1}, F_n$ डिवाइडर का मिलान करें $$$(- 1) ^ n$ , यानी। पड़ोसी फाइबोनैचि संख्या परस्पर सरल है। इसका मतलब यह भी है कि आपसी सादगी और संख्या $$$F_ {3k}, F_ {3k-1}$ और $$$F_ {3k}, F_ {3k + 1}$ , यानी। $$$F_ {3k}$ और $$$F_m$ । लेकिन धारणा से $$$F_m$ - सम, और $$$F_ {3k}$ - पहले से सिद्ध भी। तो अन्य भी संख्या से $$$F_ {3k}$ जहाँ $$$k \ in \ mathbb {N}$ फिबोनाची अनुक्रम में मौजूद नहीं है। और हमने एक दिलचस्प तथ्य यह भी स्थापित किया कि पड़ोसी फिबोनाची संख्याएं परस्पर सरल हैं।

अंत में, हम अपने अनुमान को साबित करने के लिए कम से कम एक और तरीका दिखाते हैं: ल्यूक के प्रमेय का उपयोग करें।

ल्यूक की प्रमेय । पूर्णांक विभाजित है $$$F_m$ , और $$$F_n$ , अगर और केवल अगर यह एक भाजक है $$$F_d$ जहाँ $$$d = \ gcd (m, n)$ विशेष रूप से

$$

$$\ gcd (F_m, F_n) = F _ {\ gcd (m, n)}$$

यहां $$$\ gcd$ सबसे बड़ा सामान्य कारक है। अगर डाला जाए $$$m = 3$ तो $$$\ gcd (2, F_n) = F _ {\ gcd (3, n)}$ । अगर $$$F_n$ - यहां तक ​​कि, फिर बाईं ओर 2 है, ताकि दाहिना पक्ष भी 2 के बराबर हो, यह आवश्यक है कि $$$एन$ 3 से विभाजित और एक ही समय में विपरीत सच है। इस प्रकार, हम वही प्राप्त करते हैं जो हम सिद्ध करना चाहते थे।

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

एल्गोरिथ्म

और अब यह एक एल्गोरिथ्म के साथ आने के लिए बना हुआ है। आप निश्चित रूप से वही कर सकते हैं जो मूल रूप से पावेलिझिन ने किया था, लेकिन जाँच के बजाय $$$0 \ equiv F_n \ mod 2$ हम जाँच कर सकते हैं $$$0 \ equiv n \ mod 3$ , यह एक मोड़ है! सच है, यह एल्गोरिथ्म के पुनरावृत्तियों की संख्या को प्रभावित नहीं करता है, क्योंकि हमने सिर्फ अनुक्रम फ़िल्टर को बदल दिया है। जिस संपत्ति की हमें ज़रूरत है (समता), उसके साथ फाइबोनैचि संख्याओं का तुरंत बाद में उत्पन्न करना बेहतर है, इसलिए एक और स्पष्ट तरीका है कि बिनेट सूत्र का उपयोग करें

$$

$$F_n = \ left \ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \ right \ rceil, \ qquad n \ in \ {3,6, \ ldots, 3k \ ldots \}$$

गणना की दक्षता के साथ कठिनाइयां हैं, मूल पोस्ट में इसके बारे में अधिक। इसलिए, मैं अपनी राय, विधि - पुनरावृत्ति गणना में सबसे अच्छा प्रस्तावित करता हूं $$$F_ {n + 3}$ , यह किया जा सकता है, जैसा कि हमने पहले दिखाया था, सूत्र द्वारा $$$F_ {n + 3} = 2F_ {n + 1} + F_n$ । एल्गोरिथ्म में पुनरावृत्त संक्रमण का निर्माण करने के लिए, हमें गणना करने की आवश्यकता है $$$F_ {n + 4}$ , सब कुछ उतना ही सरल है

$$

$$F_ {n + 4} = F_ {n + 3} + F_ {n + 2} = 2F_ {n + 1} + F_n + F_ {n + 1} + F_n = 3F_ {n +} + 2F_n$$

वैसे, आम तौर पर बोलना, यह साबित करना आसान है

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n$$

फिर औपचारिक रूप से एल्गोरिथ्म निम्नानुसार लिखा जाता है (वर्तमान में भी फाइबोनैचि संख्या $$$F_n$ इसके बाद फिबोनाची संख्या है $$$F_ {n + 1}$ । $$$एम$ क्या समस्या की स्थिति में दी गई संख्याओं के लिए ऊपरी सीमा है):

1. $$$F_n \ leftarrow F_3 = 2, \ quad F_ {n + 1} \ leftarrow F_4 =$
2. अगर $$$F_n> M$ , फिर समाप्त करें, अन्यथा परिणाम में जोड़ें $$$F_n$
3. $$$(F_n, F_ {n + 1}) \ leftarrow (2F_ {n + 1} + F_n, 3F_ {n + 1} + 2F_n)$ चरण 2 पर जाएं।

एल्गोरिथ्म काफी तुच्छ है - हम बस हर तीसरे फिबोनाची नंबर पर कूदते हैं और इसे प्रिंट करते हैं (यदि यह अधिक नहीं है $$$एम$ )। एल्गोरिथ्म की जटिलता अभी भी रैखिक है, लेकिन चरण 2 के दोहराव की संख्या सीमा में भी फाइबोनैचि संख्याओं के बराबर है $$$1 \ ldots M$ तुलना के लिए, फ़िल्टरिंग के साथ एक सरल एल्गोरिथ्म के लिए 3 गुना अधिक पुनरावृत्तियों की आवश्यकता होती है (प्रत्येक पाया के लिए, 2 छूट जाएंगे)।

एल्गोरिथ्म कागज पर मौजूद है, साक्षात्कार, PHP क्या था? खैर, आखिरकार PHP का मतलब उजागर करें

function evenfibs($ubound) { $result = []; [$evenf, $nextf] = [2, 3]; while($evenf <= $ubound) { array_push($result, $evenf); [$nextf, $evenf] = [ 3 * $nextf + 2 * $evenf, 2 * $nextf + $evenf]; } return $result; } 

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

$$

$$F_ {n + 3} = 2F_ {n + 1} + F_ {n} = 3F_n + 2F_ {n-1} = 3F_n + F_ {n-1} + F_ {n-1} = \\ 3F_n + () F_ {n-1} + F_ {n-2}) + F_ {n-3} = 4F_n + F_ {n-3}$$

 function evenfibs($ubound) { if($ubound < 2) return []; $evens = [2]; $next = 8; for($i = 1; $next <= $ubound; $i++) { $evens[$i] = $next; $next = $evens[$i]*4 + $evens[$i-1]; } return $evens; } 

सामान्यकरण

हमने यहां ल्यूक के प्रमेय का उल्लेख किया है, जो बताता है कि $$$\ gcd (F_m, F_n) = F _ {\ gcd (m, n)}$ । इसके परिणामस्वरूप, हम उस फाइबोनैचि संख्या को प्राप्त कर सकते हैं $$$F_n$ के कई $$$F_m$ , यदि और केवल यदि इसकी संख्या $$$एन$ संख्या के लिए कई $$$एम$ । यानी हर 4 वें फाइबोनैचि संख्या को 3 से विभाजित किया जाता है, हर 5 वें द्वारा 5, हर 6 वें द्वारा 8 आदि।

फिर, एक सरल तरीके से, हम फाइबोनैचि की गणना के लिए एक एल्गोरिथ्म प्राप्त करते हैं, जिसमें कुछ दिए गए तत्वों के गुणक होते हैं। $$$F_m$ । इस तथ्य का उपयोग करना

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n \\ F_ {n + m + 1} = F_ {m + 1} F_ {n + 1} # F_mF_n$$

पिछला एल्गोरिथ्म में बदल जाता है

1. $$$F_n \ leftarrow F_m, \ quad F_ {n + 1} \ leftarrow F_ {m_ 1 # $$
2. अगर $$$F_n> M$ , फिर समाप्त करें, अन्यथा परिणाम में जोड़ें $$$F_n$
3. $$$(F_n, F_ {n + 1}) \ leftarrow (F_mF_ {n + 1} + F_ {m-1} F_n, F_ {m + 1} F_ {n + 1} +__mF_n)$ चरण 2 पर जाएं।

जहाँ $$$F_ {m-1}, F_m, F_ {m + 1}$ स्थिरांक के रूप में सेट किया जा सकता है।

नोटों का सारांश । जैसा कि उपयोगकर्ता अज्ञानता ने सामान्य रूप से उल्लेख किया है, सामान्यीकृत मामले में, एक एल्गोरिथ्म का निर्माण भी संभव है जो आंशिक परिणाम से केवल संख्याओं का उपयोग करता है।

$$

$$F_ {n + 1} = F_n + F_ {n-1} \\ F_ {n + 2} = 3F_ {n} - F_ {n-2} \\ F_ {n + 3} = 4F_ {n} + F_ {n-3} \\ F_ {n + 4} = 7F_ {n} - F_ {n-4} \\ F_ {n + 5} = 11F_ {n} + F_ {n-5} \\ \ cdots \\ F_ {n + t} = (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt}$$

हमें गणितीय इंडक्शन की विधि द्वारा यह साबित करने के लिए, t = 1 और t = 2 के लिए, पूर्णता स्पष्ट है। मान लीजिए कि यह कुछ टी तक रखती है, तो

$$

$$F_ {n + t + 1} = F_ {n + t} + F_ {n + t-1} = \\ (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt} + \\ (F_ {t-1} + 2F_ {t-2}) F_n + (-1) ^ {t-2} F_ {n-t + 1} = \\ (F_t_ F_ {) t-1} + 2 (F_ {t-1} + F_ {t-2})) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {n-t + 1}) = \\ (F_ {t + 1} + 2F_t) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {nt} -F_ {nt-1}) = \\ (F_ {t +) 1} + 2F_t) F_n + (-1) ^ tF_ {nt-1}$$

कुल जैसा कुछ

बेशक कार्य पूरी तरह से सिंथेटिक है, पुनरावृत्तियों की संख्या बहुत कम है (के लिए) $$$M = $ 10,00$ उत्तर में केवल 6 संख्याएँ हैं, अर्थात् 6 पुनरावृत्तियों को पूरा किया गया होगा, और मूल "हेड-ऑन" एल्गोरिथ्म को 18 की आवश्यकता होगी), लेकिन इस तरह एक उपयोगकर्ता जिसने यहां कुछ नया खोजा है, अब साक्षात्कार में फाइबोनैचि संख्याओं में थोड़ा गहरा गणितीय ज्ञान दिखा सकता है।

संपादित करें: सरल प्रमाणों के लिए जनेटम और अललेक्सइन उपयोगकर्ताओं के लिए धन्यवाद, मैंने उन्हें "प्रमेयकरण" में शामिल किया, साथ ही एल्गोरिथ्म के लिए हंटररोल का उपयोग केवल गणनाओं में पहले से ही प्राप्त संख्याओं का उपयोग करके और इसे सामान्य करने के लिए उपयोगकर्ता की अज्ञानता के लिए किया।