🖖 🚴🏻 👨🏿‍🎤 लगभग एक चिकना डिजाइन 🙎 👩🏾‍🤝‍👩🏽 🚃

परिचय

मैं आपको यह बताकर लेख शुरू करूंगा कि मैं इस सुरुचिपूर्ण डिजाइन से कैसे परिचित हुआ। ओलंपियाड प्रोग्रामिंग के कारण, मेरे शिक्षक और मैंने कई दिलचस्प समस्याओं को हल किया। और फिर एक दिन मैं निम्नलिखित कार्य में आया:

आरोही क्रम में प्रिंट करें सभी इर्रिदेबल फ्रैक्शंस जिनके हरनाम n, n <= 100 से अधिक नहीं है।

जब मैंने समस्या की स्थिति को अंत तक पढ़ा, तो यह मुझे जटिल नहीं लगा (यह नहीं है और यह नहीं है)। मेरे लिए पहली बात यह थी कि बस हर भाजक को 2 से n तक हल करना था और, प्रत्येक भाजक के लिए, 1 से हर के संख्यात्मक पर iterate, बशर्ते कि अंश और भाजक परस्पर सरल हो। ठीक है, फिर उन्हें आरोही क्रम में क्रमबद्ध करें।

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

स्टर्न-ब्रो ट्री

स्टर्न-ब्रोको पेड़ की खोज स्वतंत्र रूप से जर्मन गणितज्ञ मेरिट्ज स्टर्न और फ्रांसीसी घड़ी निर्माता अकिलीस ब्रोको ने की थी। यह पेड़ आपको सभी अप्रासंगिक, गैर-नकारात्मक अंशों के सेट का निर्माण करने की अनुमति देता है।

शुरू करने के लिए, हम निम्नलिखित शब्द पेश करते हैं: दो अंश दिए जाएं

। फिर अंश

- उनके मीडियन को बुलाया।
हम दो काल्पनिक अंशों के साथ पेड़ का निर्माण शुरू करते हैं:

- संकेत करना 0;

- अनंत को निरूपित करते हुए "विडंबनापूर्ण रूप में।"

प्रत्येक बाद के पुनरावृत्ति में, उनके मध्य में अंशों के बीच में डाला जाता है, और एक ही ऑपरेशन को फ्रैक्चर के प्रत्येक जोड़े के लिए दोहराया जाता है:

अनंत तक इस प्रक्रिया को जारी रखते हुए, हम गैर-नकारात्मक अंशों के पूरे सेट का निर्माण कर सकते हैं।

स्टर्न-ब्रोको पेड़ इतना दिलचस्प नहीं होगा अगर यह अपनी अद्भुत विशेषताओं के लिए नहीं था, और इसमें बहुत कुछ है:

भिन्नों की जलन;
भिन्नों का क्रम;
बिल्कुल सभी अंशों की उपस्थिति।

एक पूछ सकता है: सभी फ्रैक्चर्स इरेड्यूबल क्यों हैं? क्यों दिए जाते हैं आदेश? एक ही अंश एक से अधिक बार क्यों नहीं मिल सकता है? इन सवालों के जवाब काफी सरल हैं। इस पेड़ की संरचना पर विचार करने के लिए आपको केवल थोड़ा और विस्तार चाहिए।

चलो

- स्टर्न-ब्रोको पेड़ के लगातार दो अंश। आप देख सकते हैं कि समानता yz - xt = 1 उनके लिए है (कई जोड़े अंशों के लिए इसे स्वयं जांचें)। हम पेड़ के सभी अंशों के लिए प्रेरण द्वारा इस कथन को सिद्ध करते हैं। प्रेरण के आधार के लिए हम भिन्न लेते हैं

और

जिसके लिए समानता 1 * 1 - 0 * 0 = 1 सत्य है।

अब हम यह दिखाते हैं कि फ्रैक्चर के बीच माध्यिका डालते समय

जिसके लिए समानता yz - xt = 1 सत्य है, यह भिन्न के लिए भी धारण करेगा

।
हमारे पास है:

जैसा कि आप देख सकते हैं, ये दोनों समीकरण मूल एक के बराबर हैं, इसलिए हालत yz - xt = 1 - पेड़ में लगातार सभी अंशों के लिए एक अपरिवर्तनीय है। ठीक है, क्या हालत yz - xt = 1 का मतलब है? इसका अर्थ है कि GCD (x, y) = GCD (z, t) = 1. वास्तव में, संख्याएँ x, y और z, t काप्रेम हैं (यदि GCD (x, y), 1, तो बाईं ओर को GCD से विभाजित किया जाएगा। , लेकिन दाएं हाथ को केवल 1 से विभाजित किया जाता है, इसी तरह जीसीडी (जेड, टी) के लिए।

यही कारण है कि अंश चिड़चिड़े हैं, अंश और हर हमेशा परस्पर सरल होते हैं। उन्होंने पहले सवाल का जवाब दिया! हम दूसरे पास करते हैं!

भिन्नों का आदेश क्यों दिया जाएगा? इस प्रश्न का उत्तर देने के लिए, यह दर्शाने के लिए पर्याप्त है कि दो भिन्नों का माध्य हमेशा उनके बीच रहता है।

चलो

- एक पेड़ में दो लगातार अंश और

। हम दिखाते हैं

। एक आम भाजक के लिए भिन्नता लाना और स्थिति पर विचार करना

हमें मिलता है:

यह देखते हुए कि पिछले अंशों के भाजक धनात्मक होते हैं, संख्यावाचक ऋणात्मक होना चाहिए, और यह मूल असमानता xt - yz । 0 है । इससे हम यह निष्कर्ष निकालते हैं कि दो अंशों का मध्य हमेशा उनके बीच स्थित होता है (लेकिन आवश्यक नहीं कि बीच में)। इस प्रकार, हमने स्टर्न-ब्रो के पेड़ में अंशों का क्रम दिखाया।

खैर, आखिरी वाला! हम कम से कम एक अंश को याद नहीं कर सकते हैं, अर्थात, पेड़ में सभी अंश क्यों मौजूद हैं?

यदि हमें एक पेड़ में एक निश्चित अंश खोजने की आवश्यकता है, तो हम इसे कैसे करेंगे? खोज प्रक्रिया वास्तव में एक द्विआधारी खोज है। हम मध्यिका के साथ वांछित अंश की तुलना करते हैं और 3 मामले संभव हैं:

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

जाहिर है, इस प्रक्रिया को अनिश्चित काल तक नहीं किया जा सकता है। इस प्रकार, किसी दिन हम अपना अंश पाएंगे (अपने लिए सोचें कि ऐसा क्यों है) ।

भयंकर क्रम

खैर, मूल कार्य के बारे में क्या? ऐसा लगता है कि स्टर्न-ब्रो का पेड़ हमारे लिए उपयुक्त है, लेकिन इसमें बड़ी इकाइयों के अंश होते हैं जो कि बहुत अधिक होते हैं। हालाँकि, जो हमें काल्पनिक भिन्नों के बजाय लेने से रोकता है

और

अंशों

? कुछ नहीं!

स्टर्न-ब्रो ट्री का ऐसा विशेष मामला फारे सीक्वेंस का आधार है।

ऑर्डर n का एक फ़ेयर सीक्वेंस 0 और 1 के बीच सभी इर्रिदेबल फ्रैक्शंस का सेट है, जिसका हर n से अधिक नहीं होता है, जो बढ़ते क्रम में व्यवस्थित होते हैं। अनुक्रम को F _n अक्षर से निरूपित किया जाता है।

सख्ती से गणितीय रूप से, इस क्रम को इस प्रकार लिखा जा सकता है:

यह कैसे n = 1, ..., 5 के लिए फारेसी अनुक्रम है

इस अनुक्रम का नाम जॉन फेरी एक प्रसिद्ध भूविज्ञानी के नाम पर रखा गया है।

वास्तव में, मूल समस्या को निम्नानुसार सुधार किया जा सकता है: एन-ऑर्डर फ़ेरी अनुक्रम का निर्माण करने के लिए। इसके निर्माण के लिए C # कोड बहुत सरल लगता है, केवल 2 पुनरावर्ती कॉल:

public static void FareiSequence(int n) { Console.WriteLine("{0} / {1}", 0, 1); FareiSequence(n, 0, 1, 1, 1); Console.WriteLine("{0} / {1}", 1, 1); } private static void FareiSequence(int n, int x, int y, int z, int t) { int a = x + z, b = y + t; if (b <= n) { FareiSequence(n, x, y, a, b); Console.WriteLine("{0} / {1}", a, b); FareiSequence(n, a, b, z, t); } }

गणितीय अभिव्यक्तियों को सरल बनाने के लिए भिन्नात्मक भिन्नों का उपयोग किया जा सकता है।

उदाहरण के लिए, आपको अभिव्यक्ति की गणना करने की आवश्यकता है:

एक सामान्य हर में लाने का मानक तरीका हमारे लिए दिलचस्प नहीं है। हम फ्रैरी श्रृंखला के पड़ोसी अंशों के अंतर के रूप में भिन्न का प्रतिनिधित्व करते हैं:

यह अभिव्यक्ति इतनी आसानी से गणना की जा सकती है! इसके अंत में फारे का क्रम और एक बार फिर स्टर्न-ब्रो के पेड़ पर लौट आया।

एक संख्या प्रणाली के रूप में पेड़

यह पता चला है कि स्टर्न-ब्रो ट्री का उपयोग तर्कसंगत संख्याओं का प्रतिनिधित्व करने के लिए एक संख्या प्रणाली (एक प्रतीकात्मक तरीका) के रूप में किया जा सकता है।

लेकिन प्रत्येक अंश के साथ वर्णों के अनुक्रम का मिलान कैसे करें? ऐसा करने के लिए, हम पेड़ में एक निश्चित अंश खोजने के लिए एक बार फिर से एल्गोरिथ्म को याद करते हैं।

हमें अंश खोजने की आवश्यकता है

पेड़ में। हम मध्यिका के साथ खोज शुरू करते हैं

। बाएं सबट्री के साथ संक्रमण, अक्षर L द्वारा निरूपित किया जाता है, साथ ही अक्षर R से सही उप-प्रकार होता है। इस प्रकार, संख्या

एलएलआरएल चरित्र अनुक्रम (आंकड़ा देखें) से मेल खाता है।

इस प्रकार, हम प्रत्येक तर्कसंगत अंश को L AND R (या हम पूरी तरह से 0 और 1 के साथ पूरी तरह से बाइनरी नंबर सिस्टम से मेल कर सकते हैं) के अनुक्रम के साथ मेल कर सकते हैं।

तर्कसंगत द्वारा वास्तविक संख्याओं का अनुमान

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

आइए संख्या को अनुमानित करने का प्रयास करें

। हमें यह परिणाम RRRLLLLLLLRRRRRRRRRRRRRRRRRRRRRRRRRRRrr.आर.

इस दृश्य के आधार पर, हम यह मान सकते हैं कि भिन्न

संख्या के लिए सरल तर्कसंगत सन्निकटन के रूप में सेवा करें

ऊपर और नीचे। इस प्रकार, हम यह निष्कर्ष निकाल सकते हैं

।

यह, शायद, स्टर्न-ब्रोको पेड़ के साथ हमारे परिचित को समाप्त करेगा। मुझे उम्मीद है कि लेख पढ़ने के लिए दिलचस्प था।

लगभग एक चिकना डिजाइन

परिचय

स्टर्न-ब्रो ट्री

भयंकर क्रम

एक संख्या प्रणाली के रूप में पेड़

तर्कसंगत द्वारा वास्तविक संख्याओं का अनुमान

More articles: