[Powered by Google Translate] [धारा 3 - अधिक आरामदायक]
[रोब Bowden - हार्वर्ड विश्वविद्यालय]
>> [यह CS50 है. - CS50.TV]
>> तो पहला सवाल अजीब शब्दों है.
GDB की मदद से आप "डिबग" एक कार्यक्रम है, लेकिन, और अधिक विशेष रूप से, यह क्या आप करते हैं?
मैं एक जवाब है कि, और मैं नहीं जानता कि वास्तव में क्या उम्मीद है,
इसलिए मैं यह की तर्ज साथ यह कुछ लग रहा है की मदद से आप कदम से कदम
कार्यक्रम के माध्यम से चलते हैं, इसके साथ बातचीत करने के लिए, परिवर्तन चर, ये सब बातें करते -
मूल रूप से पूरी तरह से एक कार्यक्रम के नियंत्रण
और कार्यक्रम के क्रियान्वयन के किसी भी भाग का निरीक्षण किया.
तो उन सुविधाओं को जाने के लिए आप चीजों डिबग.
ठीक है.
द्विआधारी खोज क्यों आवश्यकता नहीं है कि एक सरणी हल किया जा?
कौन है कि जवाब देने के लिए करना चाहता है?
[छात्र] क्योंकि यह अगर यह हल नहीं है काम नहीं करता. >> हाँ. [हँसी]
अगर यह हल नहीं है, तो यह असंभव है यह आधे में विभाजित
और छोड़ दिया है कि सब कुछ पता है और कम से सही करने के लिए सब कुछ है
मध्यम मूल्य से अधिक है.
तो यह हल किया जा करने की जरूरत है.
ठीक है.
क्यों चुकता n हे में बुलबुले की तरह है?
क्या किसी को पहले एक बहुत जल्दी क्या बुलबुला तरह की उच्च स्तरीय सिंहावलोकन देने के लिए करना चाहते हैं?
[छात्र] आप मूल रूप से प्रत्येक तत्व के माध्यम से जाना है और आप पहले कुछ तत्वों की जाँच करें.
अगर वे जहाँ आप उन्हें स्वैप से बाहर रहे हैं, तो आप अगले कुछ तत्वों और इतने पर की जाँच करें.
जब आप अंत तक पहुँचते हैं, तो आप जानते हैं कि सबसे बड़ा तत्व अंत में रखा गया है,
तो आप की अनदेखी है कि एक तो आप के माध्यम से जा रहा पर रखने,
और हर बार जब आप एक कम तत्व की जांच जब तक आप में कोई परिवर्तन नहीं है. >> हाँ.
यह बुलबुला तरह कहा जाता है क्योंकि अगर आप अपने पक्ष पर सरणी फ्लिप तो यह ऊपर है और नीचे, खड़ी,
तो बड़ी मूल्यों नीचे सिंक और छोटे मूल्यों शीर्ष पर बुलबुला होगा.
यही कारण है कि यह कैसे अपने नाम मिल गया.
और हाँ, तुम बस के माध्यम से जाना.
आप सरणी के माध्यम से जा रहा रखने के लिए, बड़ा मूल्य गमागमन
नीचे करने के लिए सबसे बड़ा मूल्यों को प्राप्त है.
>> चुकता n हे ऐसा क्यों है?
सबसे पहले, किसी को भी कहते हैं कि क्यों यह n हे चुकता करना चाहती है?
[छात्र] क्योंकि प्रत्येक रन के लिए यह n बार चला जाता है.
तुम सिर्फ यकीन है कि आप सबसे बड़ा तत्व सभी तरह से नीचे ले लिया है हो सकता है,
तो आप कई तत्वों के रूप में लिए है कि दोहराना है. >> हाँ.
तो मन में रखने के लिए बड़ी हे क्या मतलब है और क्या बड़ा ओमेगा का मतलब.
बड़ा हे धीमी गति से यह वास्तव में कैसे चला सकते हैं पर बाध्य ऊपरी की तरह है.
तो यह चुकता n हे कह कर, यह पता हे या नहीं है और इसे चलाने के लिए सक्षम होगा
रैखिक समय में है, लेकिन यह पता cubed हे है
क्योंकि यह n cubed हे से घिरा है.
यदि यह चुकता n हे से घिरा है, तो यह भी पता cubed द्वारा घिरा है.
तो यह n चुकता है, और निरपेक्ष सबसे खराब स्थिति में यह चुकता n की तुलना में बेहतर नहीं कर सकते हैं,
जो है क्यों यह चुकता n हे है.
तो देखने के लिए कि यह कैसे बाहर आता n चुकता मामूली गणित,
अगर हम हमारी सूची में पाँच बातें हैं, पहली बार कितने स्वैप हम संभवतः के लिए बनाने की जरूरत सकता है
आदेश में इस पाने के लिए? चलो वास्तव में सिर्फ -
हम कितने स्वैप करने के लिए सरणी के माध्यम से बुलबुला तरह का पहला रन बनाने के लिए है करने के लिए जा रहे हैं?
[छात्र] n - 1. >> हाँ.
>> 1 - अगर वहाँ 5 तत्व हैं, हम करने के लिए n बनाने की आवश्यकता जा रहे हैं.
फिर एक दूसरे पर हम कितने स्वैप करने के लिए बनाने के लिए जा रहे हैं?
[छात्र] n - 2. >> हाँ.
और तीसरा n होना जा रहा है - 3, और फिर सुविधा के लिए मैं पिछले दो लिखेंगे
तब के रूप में हम करने के लिए 2 स्वैप और 1 स्वैप करने की आवश्यकता के लिए जा रहे हैं.
मुझे लगता है कि पिछले एक या होने की जरूरत हो सकता है नहीं वास्तव में.
यह एक स्वैप है? मुझे नहीं मालूम.
तो इन स्वैप की कुल मात्रा में या कम से कम तुलना आपको करना है.
यहां तक ​​कि अगर आप स्वैप नहीं है, तो आप अभी भी मूल्यों की तुलना की जरूरत है.
तो वहाँ n सरणी के माध्यम से 1 रन में 1 तुलना.
यदि आप इन बातों को पुनर्व्यवस्थित, वास्तव में यह छह चीजें बनाने के लिए चीजों को अच्छी तरह से धुआँरा,
और फिर मैं 3 करने के लिए, 2 हूँ, 1.
तो बस इन रकम उलटफेर, हम देखते हैं कितने तुलना हम बनाने चाहते हैं
पूरे एल्गोरिथ्म में.
तो अगर हम यहाँ नीचे इन लोगों को लाने के लिए,
तो हम अब भी कर रहे हैं लेकिन कई की तुलना वहाँ थे संक्षेप.
लेकिन अगर हम इन राशि और हम इन राशि और हम इन संक्षेप
यह अभी भी एक ही समस्या है. हम बस विशेष रूप से उन समूहों का योग.
>> तो अब हम 3 एन संक्षेप रहे हैं. यह सिर्फ 3 n नहीं है.
यह हमेशा n / 2 n होने जा रहा है.
यहाँ तो हम 6 के लिए होता है.
अगर हम 10 बातें किया था, तो हम चीजों के 5 अलग जोड़े के लिए इस समूह कर सकता है
और + n n n + + + n n के साथ खत्म होता है.
तो तुम हमेशा n / 2 n मिल जा रहे हैं, और तो यह हम इसे / 2 चुकता n लिख लेता हूँ.
और तो भले ही आधे का कारक है, जो में आने के लिए होता है
तथ्य यह है कि सरणी पर प्रत्येक चलना के माध्यम से हम कम 1 तुलना की वजह से
इतना है कि कैसे हम 2 से अधिक मिलता है, लेकिन यह अभी भी चुकता n है.
हम एक आधे के निरंतर कारक के बारे में परवाह नहीं है.
तो इस तरह बड़े हे सामान की एक बहुत सिर्फ गणित के इस प्रकार के कर के प्रकार पर निर्भर करता है,
गणित रकम और ज्यामितीय श्रृंखला सामान कर रही है,
लेकिन इस कोर्स में उनमें से ज्यादातर बहुत सीधा कर रहे हैं.
ठीक है.
N के ओमेगा में अंतरवेशन शॉटन क्यों है? ओमेगा क्या मतलब है?
[दो छात्रों को एक ही बार में बोल - unintelligible] >> हाँ.
आप ओमेगा के रूप में कम बाध्य के बारे में सोच सकते हैं.
>> तो कोई बात नहीं कैसे कुशल आपके सम्मिलन सॉर्ट एल्गोरिथ्म है,
की परवाह किए बिना कि सूची में पारित कर दिया है, यह हमेशा के लिए कम से कम n चीजों की तुलना
या यह n बातों पर पुनरावृति है.
ऐसा क्यों है?
[छात्र] क्योंकि यदि सूची पहले से ही सॉर्ट किया जाता है, तो के माध्यम से पहली यात्रा
आप केवल गारंटी नहीं है कि बहुत पहले तत्व कम से कम कर सकते हैं,
और दूसरी यात्रा आप केवल पहले दो की गारंटी कर सकते हैं
क्योंकि आप नहीं जानते कि सूची के बाकी हल है. >> हाँ.
यदि आप एक पूरी तरह से क्रमबद्ध सूची में बहुत कम से कम, पास आप सभी तत्वों पर जाना है
देखने के लिए कुछ भी नहीं करने के लिए चारों ओर ले जाया जा जरूरत है.
तो खत्म हो सूची गुजर रहा है और कह रही है ओह, यह पहले से ही सॉर्ट किया जाता है,
यह असंभव है के लिए आप जानते हैं यह हल है जब तक आप प्रत्येक तत्व की जांच
देखना है कि वे क्रमबद्ध क्रम में हैं.
तो सम्मिलन प्रकार पर ही कम n के ओमेगा है.
सबसे खराब मामला मर्ज तरह के समय क्या चल रहा है,
सबसे खराब मामला बड़ा हे फिर से किया जा रहा है?
तो सबसे बुरी स्थिति में, कैसे मर्ज तरह से चलाने में करता है?
[छात्र] एन लॉग एन. >> हाँ.
सबसे तेजी से सामान्य छँटाई एल्गोरिदम n लॉग एन. बेहतर होगा कि तुम ऐसा नहीं कर सकते.
>> विशेष मामलों में कर रहे हैं, और अगर हम आज समय है लेकिन हम शायद won't -
हम एक है कि n लॉग एन की तुलना में बेहतर करता देख सकता था.
लेकिन सामान्य मामले में, आप n लॉग एन की तुलना में बेहतर नहीं कर सकते हैं.
और मर्ज तरह n लॉग n है कि इस पाठ्यक्रम के लिए एक पता होना चाहिए होता है.
और इतना है कि आज हम वास्तव में लागू करने हो जाएगा.
और अंत में, कोई तीन से अधिक वाक्यों में चयन छंटाई कैसे काम करता है?
क्या किसी को जवाब देना चाहते हैं, और मैं अपने वाक्य गिनती जाएगा
क्योंकि अगर आप 3 से अधिक जाने -
क्या किसी को चयन छंटाई याद है?
चयन तरह आम तौर पर होता है बहुत आसान करने के लिए सिर्फ नाम से याद है.
तुम बस पर पुनरावृति सरणी, जो भी सबसे बड़ा मूल्य है या छोटी -
आदेश जो कुछ भी तुम्हें अंदर छँटाई कर रहे हैं
तो हम कहते हैं कि हम सबसे बड़ी से छोटी छँटाई कर रहे हैं.
आप सरणी पर पुनरावृति, जो न्यूनतम तत्व है के लिए देख रहे हैं,
यह चयन करने के लिए, और फिर बस यह स्वैप जो पहली जगह में है.
और फिर सरणी पर 2 पास न्यूनतम तत्व के लिए फिर देखो,
यह चयन करें, और तब यह क्या 2 की स्थिति में है साथ स्वैप.
तो हम बस उठा रहे हैं और न्यूनतम मूल्यों का चयन
और उन्हें सरणी के सामने में डालने जब तक यह हल है.
उस पर सवाल?
>> ये अनिवार्य रूप से आप बाहर भरने के लिए जब आप प्रस्तुत कर रहे हैं pset रूपों में दिखाई देते हैं.
वे मूल रूप से कर रहे हैं उन लोगों के लिए जवाब है.
ठीक है, तो अब समस्याओं कोडन.
मैं पहले से ही ईमेल पर बाहर भेज दिया - क्या किसी को भी उस ईमेल पाने के लिए नहीं? ठीक है.
मैं पहले से ही ईमेल पर बाहर भेजा जगह है कि हम का उपयोग करने के लिए जा रहे हैं,
और अगर आप मेरे नाम पर क्लिक करें तो मुझे लगता है कि मैं करने के लिए नीचे होने जा रहा हूँ
क्योंकि आर के पीछे की ओर - लेकिन अगर तुम मेरे नाम पर क्लिक करें आप 2 संशोधन देखेंगे.
1 संशोधन करने के लिए मैं पहले से ही नकल हो सकता है और रिक्त स्थान में कोड चिपकाया जा रहा है
खोज बात के लिए आप को लागू करने के लिए जा रहे हैं.
और 2 संशोधन तरह बात यह है कि हम उस के बाद लागू किया जाएगा.
तो तुम मेरे 1 अवतरण पर क्लिक करें और वहाँ से काम कर सकते हैं.
और अब हम द्विआधारी खोज को लागू करना चाहते हैं.
>> क्या किसी को सिर्फ एक pseudocode उच्च स्तर के विवरण देना चाहता हूँ
की हम क्या करने के लिए खोज के लिए क्या करना है करने के लिए जा रहे हैं? हाँ.
[छात्र] तुम बस सरणी के बीच लेने और देखने के लिए कि क्या आप के लिए देख रहे हैं
कि कम से कम या अधिक से अधिक है कि है.
और अगर यह कम है, आप आधा है कि कम है के लिए जाना है,
और अगर यह अधिक है, आप आधा है कि अधिक है और आप दोहराना है कि जब तक आप सिर्फ एक ही बात हो.
[Bowden] हाँ.
सूचना है कि पहले से ही हमारे संख्या सरणी सॉर्ट किया जाता है,
और तो इसका मतलब है कि हम इस बात का फायदा लेने के लिए और हम पहले की जाँच कर सकता कर सकते हैं,
ठीक है, मैं 50 नंबर के लिए देख रहा हूँ.
तो मैं बीच में जा सकते हैं.
मध्य परिभाषित करना मुश्किल है जब यह चीजों की एक भी नंबर है,
लेकिन चलो बस का कहना है कि हम हमेशा बीच में काटना होगा.
तो यहाँ हम 8 बातें है, तो बीच 16 होगा.
मैं 50 के लिए देख रहा हूँ, तो 50 16 से अधिक है.
तो अब मैं मूल रूप से इन तत्वों के रूप में अपने सरणी का इलाज कर सकते हैं.
मैं 16 से अधिक सब कुछ दूर फेंक कर सकते हैं.
अब मेरी सरणी इन 4 तत्वों, और मैं फिर से.
तो फिर मैं बीच खोजने के लिए फिर से करना चाहते हैं, जो 42 होने जा रहा है.
50 से 42 कम है, इसलिए मैं इन दोनों तत्वों को दूर फेंक कर सकते हैं.
यह मेरे शेष सरणी है.
मैं बीच फिर से खोजने के लिए जा रहा हूँ.
मुझे लगता है कि 50 एक बुरा उदाहरण था क्योंकि मैं हमेशा दूर फेंक रहा था छोड़ दिया करने के लिए चीजें,
लेकिन एक ही उपाय है, अगर मैं कुछ के लिए देख रहा हूँ
और यह तत्व कम से कम मैं वर्तमान में देख रहा हूँ,
तो मैं सही करने के लिए सब कुछ दूर फेंक करने के लिए जा रहा हूँ.
तो अब हम को लागू करने की जरूरत है कि.
सूचना है कि हम आकार में पारित करने की जरूरत है.
हम भी कड़ी मेहनत से कोड आकार की जरूरत नहीं कर सकते हैं.
तो अगर हम उससे छुटकारा पाना परिभाषित #
ठीक है.
कैसे मैं अच्छी तरह से समझ सकते हैं कि संख्या सरणी के आकार वर्तमान में क्या है?
>> कितने तत्वों संख्या सरणी में कर रहे हैं?
[छात्र] नंबर, कोष्ठक, लंबाई.
[Bowden] सी. में नहीं मौजूद नहीं है
की जरूरत है. लंबाई.
Arrays गुण नहीं है, तो वहाँ arrays का कोई लंबाई संपत्ति है
कि सिर्फ तुम लेकिन यह लंबे समय के लिए होता है दे देंगे.
देखें [छात्र] कितना स्मृति यह है और कितना विभाजित >> हाँ.
तो हम कैसे देख सकते हैं कितना स्मृति यह कर सकते हैं? >> [छात्र] sizeof. >> हाँ, sizeof.
Sizeof ऑपरेटर है कि संख्या सरणी के आकार वापस जा रहा है है.
और कहा कि लेकिन कई integers होने जा रहा है वहाँ कई बार एक पूर्णांक के आकार के होते हैं
बाद से है कि कितना स्मृति यह वास्तव में ले जा रहा है.
, तो अगर मैं सरणी में बातें की संख्या चाहते हैं
तो मैं एक पूर्णांक के आकार के आधार पर विभाजित करने के लिए जा रहा हूँ.
ठीक है. तो देता है कि मुझे यहाँ आकार में गुजरती है.
मैं आकार में पारित करने की आवश्यकता क्यों है?
मैं सिर्फ क्यों नहीं ऊपर यहाँ कर सकते हैं int आकार = sizeof (टेबल) / sizeof (int)?
यह काम क्यों नहीं करता है?
[छात्र] यह एक वैश्विक चर नहीं है.
[Bowden] टेबल मौजूद है और हम संख्या में सूखी घास का ढेर के रूप में पारित कर रहे हैं,
और यह क्या करने के लिए आ रहा है की एक पूर्वाभास की तरह है. हाँ.
[छात्र] टेबल सिर्फ यह करने के लिए संदर्भ है, तो यह लौटेंगे कितना बड़ा है कि संदर्भ है.
हाँ.
मैं व्याख्यान में संदेह नहीं है कि आप ढेर देखा है अभी तक वास्तव में सही है?
हम अभी इसके बारे में बात की है.
तो हो चुकी है, जहां अपने सभी चर के लिए भंडारित किया जा जा रहे हैं.
>> कोई स्मृति है कि स्थानीय चर के लिए आवंटित किया गया है ढेर में जा रहा है,
और प्रत्येक कार्य के ढेर पर अपनी जगह हो जाता है, अपने स्वयं के ढेर फ्रेम है क्या यह कहा जाता है.
तो मुख्य ढेर फ्रेम है, और इसे के अंदर करने के लिए इस संख्या सरणी मौजूद जा रहा है,
और यह आकार sizeof (संख्या) का होने जा रहा है.
यह तत्वों के आकार के आधार पर विभाजित संख्या के आकार किया जा रहा है,
लेकिन मुख्य ढेर फ्रेम के भीतर सभी जीवन है कि.
जब हम खोज फोन, खोज अपने स्वयं के ढेर फ्रेम हो जाता है,
अपनी जगह अपने स्थानीय चर के सभी स्टोर करने के लिए.
लेकिन इन तर्कों - तो टेबल में इस पूरे सरणी की एक प्रतिलिपि नहीं है.
हम खोज में एक प्रति के रूप में पूरे सरणी में पास नहीं है.
यह सिर्फ कि सरणी के लिए एक संदर्भ गुजरता है.
तो खोज इस संदर्भ के माध्यम से इन नंबरों का उपयोग कर सकते हैं.
यह अभी भी चीजें हैं जो मुख्य ढेर फ्रेम के अंदर रहने तक पहुँचने है,
लेकिन मूल रूप से, जब हम संकेत करने के लिए मिलता है, जो जल्द ही होना चाहिए,
यह है कि संकेत क्या कर रहे हैं.
सूचक सिर्फ बातें करने के लिए संदर्भ, और आप संकेत का उपयोग करने के लिए चीजों का उपयोग कर सकते हैं
है कि अन्य बातें ढेर फ्रेम में हैं.
तो भले ही संख्या मुख्य करने के लिए स्थानीय है, हम अभी भी इस सूचक के माध्यम से उपयोग कर सकते हैं.
लेकिन जब से यह सिर्फ एक सूचक है और यह सिर्फ एक संदर्भ है,
sizeof (टेबल) सिर्फ संदर्भ ही के आकार देता है.
यह बात की ओर इशारा करते है के आकार वापस नहीं करता है.
यह संख्या का वास्तविक आकार वापस नहीं करता है.
और इसलिए यह काम करने के लिए नहीं जा रहा है के रूप में हम यह चाहते है.
>> उस पर सवाल?
सूचक में काफी अधिक रक्तमय विस्तार में चला गया हो सप्ताह में लिए आते हैं.
और इस वजह से चीजें हैं जो आप देखते हैं, सबसे खोज बातें या इस तरह बातें की एक बहुत कुछ है,
वे लगभग सभी सरणी के वास्तविक आकार लेने की आवश्यकता के लिए जा रहे हैं,
सी में है, क्योंकि हम कोई विचार नहीं है सरणी के आकार क्या है.
आप मैन्युअल रूप से इसे पारित अंदर की जरूरत है
और आप स्वयं पूरे सरणी में पारित नहीं क्योंकि आप सिर्फ संदर्भ में गुजर रहे हैं कर सकते हैं
और इसे संदर्भ से आकार नहीं मिल सकता.
ठीक है.
तो अब हम को लागू करने से पहले क्या समझाया गया था चाहते हैं.
तुम उस पर एक मिनट के लिए काम कर सकते हैं,
और आप पूरी तरह से 100% सब कुछ काम कर रही के बारे में चिंता करने की ज़रूरत नहीं है.
बस कैसे आपको लगता है कि यह काम करना चाहिए के लिए 1/2 pseudocode लिखने.
ठीक है.
नहीं करने के लिए पूरी तरह से इस के साथ अभी तक किया जा जरूरत है.
लेकिन किसी को भी वे अब तक क्या किया है के साथ सहज महसूस करता है,
कुछ की तरह हम एक साथ के साथ काम कर सकते हैं?
क्या किसी को करने के लिए स्वयंसेवक चाहते हैं? या मैं बेतरतीब ढंग से ले जाएगा.
यह करने के लिए कोई उपाय है, लेकिन हम एक काम कर रहे राज्य में संशोधित कर सकते हैं कुछ सही होना जरूरी नहीं है.
[छात्र] ज़रूर. ठीक है. >>
तो आप छोटे से बचाने के आइकन पर क्लिक करके संशोधन बचा सकता है.
Ramya आप सही कर रहे हैं? >> [छात्र] हाँ. >> [Bowden] ठीक है.
तो अब मैं अपने संशोधन देखने और हर कोई संशोधन खींच सकते हैं कर सकते हैं.
और यहाँ हम है - ठीक है.
Ramya पुनरावर्ती समाधान है, जो निश्चित रूप से एक मान्य हल के साथ चला गया.
वहाँ के दो तरीके आप इस समस्या को कर सकते हैं कर रहे हैं.
आप या तो यह iteratively या बारी बारी से कर सकते हैं.
ज्यादातर समस्याओं का सामना है कि बारी बारी से किया जा सकता है भी iteratively किया जा सकता है.
तो यहाँ हम यह recursively किया है.
>> क्या किसी को परिभाषित करने के लिए यह क्या एक समारोह पुनरावर्ती बनाने का मतलब है करना चाहते हैं?
[छात्र] जब आप एक समारोह है ही कॉल
और फिर खुद को फोन जब तक यह सच है और सच के साथ बाहर आता है. >> हाँ.
एक पुनरावर्ती समारोह सिर्फ एक समारोह है जो खुद को कॉल है.
वहाँ तीन बड़ी चीजें हैं जो एक पुनरावर्ती समारोह होना चाहिए.
1 जाहिर है, यह ही कहता है.
दूसरा आधार मामला है.
तो कुछ बिंदु पर कार्य करने के लिए ही फोन बंद करने की जरूरत है,
और है कि आधार के मामले के लिए क्या है.
यहाँ तो हम जानते हैं कि हम बंद कर देना चाहिए, हम हमारे खोज में देना चाहिए
जब शुरू अंत के बराबर होती है और हम खत्म हो जाना है कि क्या मतलब है.
लेकिन अंत में, आखिरी बात यह है कि पुनरावर्ती कार्यों के लिए महत्वपूर्ण है:
कार्य किसी आधार के मामले दृष्टिकोण होना चाहिए.
जैसे कि यदि आप वास्तव में कुछ भी नहीं अपडेट कर रहे हैं जब आप 2 पुनरावर्ती कॉल,
यदि आप सचमुच सिर्फ रहे हैं समारोह फिर बुला ही तर्क के साथ
और कोई वैश्विक चर बदल गया है या कुछ भी,
जो बुरा है कि मामले में आप आधार मामला कभी नहीं पहुँच जाएगा,
यह एक अनंत recursion और एक ढेर अतिप्रवाह हो जाएगा.
लेकिन यहां हम देखते हैं कि अद्यतन हम शुरू से अद्यतन कर रहे हैं + 2 / अंत हो रहा है,
हम अंत तर्क यहाँ अपडेट कर रहे हैं, हम शुरू तर्क अपडेट कर रहे हैं यहाँ.
तो सभी पुनरावर्ती कॉल में हम कुछ अद्यतन कर रहे हैं. ठीक है.
क्या आप हमें अपने समाधान के माध्यम से चलना चाहते हैं? ज़रूर. >>
मैं SearchHelp का उपयोग कर रहा हूँ इतना है कि हर बार जब मैं इस समारोह फोन
मैं जहां मैं सरणी में देख रहा हूँ के शुरू और अंत
जहां की मैं सरणी देख रहा हूँ.
>> हर कदम में जहां यह कह रहा है कि यह मध्य तत्व + 2 / अंत है जो शुरुआत है,
वह यह है कि हम क्या देख रहे हो के लिए बराबर है?
और अगर ऐसा है, तो हम यह पाया गया है, और मुझे लगता है कि recursion के स्तर पारित हो जाता है.
और अगर यह सच नहीं है, तो हम जांच कि सरणी के बीच बहुत बड़ा मूल्य है,
जो मामले में हम शुरू से ही मध्य सूचकांक करने के लिए जा रहा द्वारा सरणी के बाईं आधा पर दिखेगा.
अन्यथा हम अंत आधा कर.
[Bowden] ठीक है.
यह अच्छा रहेगा.
ठीक है, तो एक दो बातें, और वास्तव में, यह एक बहुत ही उच्च स्तर बात है
है कि आप इस पाठ्यक्रम के लिए पता करने के लिए कभी नहीं की जरूरत है, लेकिन यह सच है.
पुनरावर्ती काम करता है, तो आप हमेशा सुना है कि वे एक बुरा सौदा कर रहे हैं
क्योंकि अगर आप recursively अपने आप को भी कई बार कहते हैं, आप ढेर अतिप्रवाह
के बाद से, जैसा कि मैंने पहले कहा, हर समारोह में अपने स्वयं के ढेर फ्रेम हो जाता है.
तो पुनरावर्ती समारोह के प्रत्येक कॉल अपने स्वयं के ढेर फ्रेम हो जाता है.
तो अगर आप 1,000 पुनरावर्ती कॉल बनाने के लिए, आप 1,000 ढेर फ्रेम मिल,
और जल्दी से आप भी कई ढेर फ्रेम और बातें सिर्फ तोड़ नेतृत्व.
तो यही कारण है कि पुनरावर्ती कार्य आम तौर पर खराब कर रहे हैं.
लेकिन वहाँ पुनरावर्ती कार्यों का एक अच्छा सबसेट पूंछ पुनरावर्ती कार्य कहा जाता है,
और इस के लिए एक जहां अगर संकलक इस नोटिस का एक उदाहरण होना होता है
और यह होना चाहिए, मुझे लगता है कि बजना में अगर आप यह झंडा O2 पास
तो यह नोटिस इस पूंछ पुनरावर्ती है और बातें अच्छा कर देगा.
>> यह प्रत्येक पुनरावर्ती कॉल के लिए पर और फिर से एक ही ढेर फ्रेम पुनः प्रयोग करेंगे.
और इसलिए क्योंकि आप उसी ढेर फ्रेम का उपयोग कर रहे हैं, आप के बारे में चिंता करने की जरूरत नहीं करते
कभी बह निकला हो चुकी है, और एक ही समय में, जैसे पहले कहा,
जहां एक बार आप वापसी सच है, तो यह ऊपर इन ढेर फ्रेम के सभी लाभ है
और SearchHelp 9 पर लौटने के लिए 10 कॉल, 8 पर लौटने के लिए है.
तो यह है कि हो सकता है जब कार्य पूंछ पुनरावर्ती जरूरत नहीं है.
और इसलिए इस समारोह में पूंछ पुनरावर्ती बनाता क्या सूचना है कि किसी भी searchHelp करने के लिए कॉल के लिए
पुनरावर्ती फोन है कि इसे बना रहा है कि यह क्या लौट रहा है.
SearchHelp के लिए पहले फोन में, हम या तो तुरंत वापसी झूठी,
तुरंत वापसी सच है, या हम एक पुनरावर्ती फोन SearchHelp
जहां हम लौट रहे हैं क्या है कि वह क्या कॉल लौट रहा है.
और हम ऐसा नहीं कर सकता है अगर हम int x वापसी SearchHelp = x * 2 की तरह कुछ किया,
बस कुछ यादृच्छिक परिवर्तन.
>> तो अब यह पुनरावर्ती कॉल, इस int x = SearchHelp पुनरावर्ती कॉल,
कोई लंबी पूंछ पुनरावर्ती है क्योंकि यह वास्तव में वापसी है
वापस पिछले एक ढेर फ्रेम करने के लिए इतना है कि कार्य करने के लिए है कि पिछले कॉल
फिर वापसी मान के साथ कुछ कर सकते हैं.
तो यह पुनरावर्ती पूंछ नहीं है, लेकिन हम क्या था से पहले अच्छी तरह से पुनरावर्ती पूंछ है. हाँ.
[छात्र] 2 आधार मामला पहले नहीं किया जा जाँच की जानी चाहिए
क्योंकि वहाँ एक स्थिति है जहां जब आप यह तर्क से गुजारें सकता है
= अंत शुरू कर दिया है, लेकिन वे सुई मान रहे हैं.
सवाल इस मामले में चला सकते हैं नहीं किया गया था जहाँ हम अंत सुई मूल्य है
या = अंत शुरू करने के लिए उचित है, = अंत शुरू
और आप वास्तव में उस विशेष मान अभी तक की जाँच नहीं की है,
तो + 2 / अंत शुरू करने के लिए बस एक ही मूल्य होने जा रहा है.
लेकिन हम पहले से ही झूठे लौटा दिया है और हम मूल्य वास्तव में कभी नहीं की जाँच की.
तो बहुत कम से कम, पहली कॉल में, अगर आकार 0 है, तो हम झूठी वापसी करना चाहते हैं.
लेकिन यदि आकार 1 है, तो शुरू बराबर अंत करने के लिए नहीं जा रहा है,
और हम कम से कम एक तत्व की जांच करेंगे.
लेकिन मुझे लगता है कि आप सही कर रहे हैं कि हम एक मामले में अंत में, जहां + 2 / अंत शुरू कर सकते हैं,
शुरू शुरू + 2 / अंत के रूप में ही किया जा रहा समाप्त होता है,
लेकिन हम उस तत्व वास्तव में कभी नहीं की जाँच की.
>> तो हम पहले की जाँच करें अगर मध्य तत्व के मूल्य के लिए हम देख रहे हैं,
तो हम तुरंत वापसी सच कर सकते हैं.
वरना अगर वे बराबर हो, तो जारी रखने में कोई मतलब नहीं है
क्योंकि हम सिर्फ एक मामले में जहां हम एक एकल - तत्व सरणी पर हैं अद्यतन करने के लिए जा रहे हैं.
यदि एक के लिए हम देख रहे हैं कि एकल तत्व नहीं है,
तो सब कुछ गलत है. हाँ.
[छात्र] बात यह है कि वास्तव में आकार के बाद से सरणी में तत्वों की संख्या की तुलना में बड़ा है,
वहां पहले से ही एक ऑफसेट - >> तो आकार -
[छात्र] कहते हैं कि अगर सरणी 0 आकार का था, तो SearchHelp वास्तव में 0 की टेबल की जाँच करेगा
पहले फोन पर.
सरणी 0 आकार है तो, 0 - >> हाँ.
वहाँ एक और बात यह है कि यह अच्छा हो सकता है. चलो लगता है.
तो अगर सरणी 10 तत्व था और हम जाँच करने के लिए जा रहे हैं बीच एक 5 सूचकांक है,
तो हम 5 की जाँच कर रहे हैं, और हम कहते हैं कि मूल्य कम है.
तो हम सब कुछ दूर फेंक रहे हैं 5 से आगे.
तो शुरू + 2 / अंत करने के लिए हमारी नई अंत होने जा रहा है,
हाँ तो, यह हमेशा के लिए सरणी के अंत से परे रहने के लिए जा रहा है.
यदि यह मामला है अगर यह भी या विषम था, तो हम जांच, कहते हैं होगा, 4,
लेकिन हम अभी भी दूर फेंक रहे हैं -
तो हाँ, अंत हमेशा सरणी के वास्तविक अंत से परे होने जा रहा है.
तत्व हम पर ध्यान केंद्रित कर रहे हैं तो, अंत हमेशा के लिए है कि एक के बाद एक होने जा रहा है.
और यदि ऐसा है तो शुरू कभी बराबर अंत नहीं है, हम 0 आकार की एक सरणी में हैं.
>> दूसरी बात मैं सोच रहा था कि हम शुरू अपडेट कर रहे हैं शुरू हो + / अंत 2,
इसलिए इस मामले कि मैं मुसीबत के साथ आ रहा है, जहां + अंत / 2 शुरू
तत्व हम जाँच कर रहे हैं.
हम कहते हैं कि हम इस 10-तत्व सरणी था. जो भी हो.
तो शुरू + / 2 को समाप्त करने के लिए यह एक तरह कुछ होने जा रहा है,
और अगर है कि मूल्य नहीं है, कहते हैं, हम अद्यतन करने के लिए करना चाहते हैं.
मूल्य अधिक होता है, तो हम सरणी के इस आधे पर देखना चाहता हूँ.
तो कैसे हम शुरू अद्यतन कर रहे हैं, हम शुरू अपडेट कर रहे हैं अब इस तत्व हो.
लेकिन यह अभी भी काम करते हैं, हो सकता है या बहुत कम से कम, आप शुरू करना + / अंत 2 + एक कर सकते हैं.
आप + अंत शुरू होने की जरूरत नहीं है [छात्र] [अश्राव्य] >> हाँ.
हम पहले से ही इस तत्व की जाँच की है और पता है कि यह एक के लिए हम देख रहे हैं नहीं है.
तो हम शुरू अद्यतन करने के लिए इस तत्व की जरूरत नहीं है.
हम सिर्फ यह छोड़ सकते हैं और इस तत्व होना शुरू करने के लिए अद्यतन.
और वहाँ कभी एक मामला है, हम कहते हैं, कि यह अंत थे,
तो फिर शुरू होगा, + शुरू अंत / 2 यह होगा,
+ शुरू अंत - हाँ, मुझे लगता है कि यह अनंत recursion में समाप्त कर सकते हैं.
चलो का कहना है कि यह सिर्फ आकार 2 या 1 आकार की एक सरणी के एक सरणी है. मुझे लगता है कि यह काम करेगा.
तो वर्तमान में, शुरुआत है कि तत्व और अंत 1 से परे है.
तो तत्व है कि हम की जाँच करने के लिए जा रहे हैं यह एक है,
और फिर जब हम शुरू अद्यतन, हम शुरू अपडेट कर रहे हैं 0 + 1/2 हो सकता है,
जो हमें वापस शुरू किया जा रहा है इस तत्व के साथ खत्म हो रहा है.
>> इसलिए हम पर और फिर से एक ही तत्व की जाँच कर रहे हैं.
तो इस मामले में जहां हर पुनरावर्ती फोन वास्तव में कुछ अद्यतन करना चाहिए.
तो हम शुरू + / अंत 2 + 1 और, या करने की जरूरत है, वहाँ एक मामला है
हम वास्तव में, जहां शुरू नहीं अपडेट कर रहे हैं.
हर कोई है कि देख रहे हो?
ठीक है.
क्या किसी को इस समाधान या किसी भी अधिक टिप्पणी पर सवाल है?
ठीक है. किसी को भी एक समाधान है कि हम सब पर देख सकते हैं चलने का है?
क्या हम सब यह recursively कर?
या फिर भी मुझे लगता है कि अगर आप उसकी खोला, तो आप अधिरोहित अपने पिछले एक हो सकता है.
क्या यह स्वचालित रूप से बचाने के लिए? मैं सकारात्मक नहीं हूँ.
क्या किसी को चलने का है?
हम इसे माध्यम से एक साथ चलना अगर नहीं कर सकते हैं.
विचार करने के लिए एक ही होने जा रहा है.
समाधान चलने का.
हम करने के लिए मूल रूप से एक ही विचार करना चाहते हैं के लिए जा रहे हैं
जहां हम सरणी की नई अंत का ट्रैक रखने और सरणी की नई शुरुआत करना चाहते हैं
और क्या है कि और अधिक से अधिक.
और क्या हम कभी एक दूसरे को काटना शुरू और अंत के रूप में ट्रैक के रख रहे हैं अगर,
तो हम यह नहीं मिल रहा था और हम झूठी वापसी कर सकते हैं.
तो मुझे लगता है कि कैसे करते हो? कोई भी सुझाव या मेरे लिए कोड को रोकना है?
[छात्र] एक समय पाश करो. >> हाँ.
आप करने के लिए एक पाश करना चाहते हैं के लिए जा रहे हैं.
>> तुमने कोड है मैं खींच सकता है, या आप क्या करने के लिए सुझाव लिए जा रहे थे?
[छात्र] मुझे ऐसा लगता है. >> सभी सही. यह चीजों को आसान बनाता है. तुम्हारा नाम क्या था?
[छात्र] लुकास.
1 संशोधन. ठीक है.
कम है कि हम क्या से पहले शुरू करने के लिए बुलाया.
नहीं है काफी क्या हम अंत से पहले कहा जाता है.
दरअसल, अंत सरणी के भीतर अब है. यह एक तत्व हम पर विचार करना चाहिए.
तो कम 0 है, सरणी के आकार - 1,
और अब हम पाशन कर रहे हैं, और हम जाँच कर रहे हैं -
मुझे लगता है कि आप इसे माध्यम से चल सकता है.
अपनी सोच को क्या इस के माध्यम से किया गया था? हमें अपने कोड के माध्यम से चलो.
[छात्र] ज़रूर. बीच में टेबल मूल्य को देखो और यह सुई तुलना करने के लिए.
ओह, वास्तव में, कि पीछे की ओर होना चाहिए - तो अगर यह अपने सुई से अधिक है, तो आप के लिए चाहते हैं.
आप दूर करने के लिए सही आधा फेंक देना चाहते हैं के लिए जा रहे हैं, और तो हाँ, कि जिस तरह से होना चाहिए.
[Bowden] तो यह कम होना चाहिए? यह है कि आप ने क्या कहा? >> [छात्र] हाँ.
[Bowden] ठीक है. कम.
यदि ऐसा है तो क्या हम देख रहे हैं कि हम क्या चाहते हैं की तुलना में छोटी है,
तो हाँ, हम दूर बाईं आधा फेंक करना चाहते हैं,
जिसका मतलब है कि हम सब कुछ हम पर विचार कर रहे हैं अद्यतन कर रहे हैं
सरणी के सही करने के लिए कम हिल द्वारा.
यह अच्छा लग रहा है.
मुझे लगता है कि यह एक ही मुद्दा है कि हम पिछले एक पर कहा है,
जहां अगर 0 कम है और ऊपर 1 है, तो कम + ऊपर 2 / स्थापित करने के लिए फिर से वही बात हो जा रहा है.
>> और यहां तक ​​कि अगर यह मामला नहीं है, यह अभी भी बहुत कम से कम और अधिक कुशल है
बस चले तत्व फेंक हम सिर्फ देखा, जिस पर हम जानते हैं कि वह गलत है.
इतनी कम + 1/2 + - >> [छात्र] कि अन्य तरीका होना चाहिए.
[Bowden] या यह होना चाहिए - 1 और अन्य एक 1 + होना चाहिए.
[छात्र] और वहाँ एक डबल होना चाहिए संकेत के बराबर होती है. >> [Bowden] हाँ.
[छात्र] हाँ.
ठीक है.
और अंत में, अब है कि हम इस + 1 - 1 बात,
यह है - यह नहीं हो सकता है - यह कभी संभव है कम करने के लिए एक की तुलना में अधिक मूल्य के साथ समाप्त करने के लिए?
मुझे लगता है कि एक ही तरीका है कि हो सकता है - क्या यह संभव है? >> [छात्र] मुझे नहीं मालूम.
लेकिन अगर इसे छोटा कर दिया जाता है और फिर शून्य से हो जाता है कि 1 और फिर - >> हाँ.
[छात्र] संभवतः यह गड़बड़ हो जाएगी.
मुझे लगता है कि यह अच्छा ही है क्योंकि होना चाहिए
के लिए इसे खत्म करने के लिए कम वे के बराबर होगा, मुझे लगता है.
लेकिन अगर वे समान हैं, तो हम समय के साथ शुरू करने के पाश नहीं किया जाएगा
और हम सिर्फ मान होता है. तो मुझे लगता है कि हम अच्छा कर रहे हैं अब.
सूचना है कि भले ही यह कोई समस्या नहीं रह गया है पुनरावर्ती,
विचारों का एक ही तरह लागू होते हैं जहां हम देख सकते हैं कि कैसे यह इतनी आसानी से ही बख्शी
तथ्य यह है कि हम सिर्फ और अधिक से अधिक हो इंडेक्स फिर से अद्यतन करने के द्वारा एक पुनरावर्ती समाधान करने के लिए,
हम समस्या छोटे और छोटे कर रहे हैं, हम सरणी के एक सबसेट पर ध्यान केंद्रित कर रहे हैं.
[छात्र] यदि कम 0 है और 1 है, वे दोनों 0 + 1/2, जो 0 से जाना होगा होगा,
और फिर एक 1 + होगा, एक होगा - 1.
[छात्र] हम समानता कहाँ की जाँच कर रहे हैं?
जैसे अगर बीच एक सुई वास्तव में है?
वर्तमान में हम यह नहीं कर रहे हैं? ओह!
It's अगर -
हां. हम सिर्फ यहाँ नीचे परीक्षण करना क्योंकि पहले बीच का कहना है -
[छात्र] यह बाध्य दूर फेंक नहीं वास्तव में पसंद है.
तो अगर आप दूर फेंक के लिए बाध्य करने के लिए, आप के लिए यह पहली या जो भी जाँच करने के लिए किया है.
आह. हाँ. >> [छात्र] हाँ.
तो अब हम एक हम वर्तमान में देखा फेंक दिया है,
जिसका मतलब है कि हम अब भी है की जरूरत है
अगर (सूखी घास का ढेर [(कम ऊपर +) / 2] == सुई), तो हम सच लौट सकते हैं.
और क्या मैं और या बस अगर रखा, यह सचमुच एक ही बात का मतलब
क्योंकि यह सच लौटा होता है.
तो मैं किसी और डाल अगर हूँ, लेकिन यह बात नहीं है.
>> तो और, यह नहीं है, और यह एक आम बात है, मुझे क्या करना है अगर
जहां भी अगर यह मामला है, जहां सब कुछ यहाँ अच्छा है,
की तरह कम ऊपर से अधिक कभी नहीं हो सकता है, यह है कि क्या सच है मूल्य के बारे में तर्क नहीं है.
तो आप के रूप में अच्छी तरह से है, जबकि कम से कम या बराबर है कह सकते हैं
या, जबकि कम से कम है
यदि ऐसा है तो वे कभी बराबर या कम कर रहे हैं पारित करने के लिए होता है,
तो हम इस लूप के बाहर तोड़ सकते हैं.
प्रश्न, चिंताओं, टिप्पणी?
ठीक है. यह अच्छा लग रहा है.
अब हम तरह करना चाहते हैं.
अगर हम अपने 2 संशोधन करने के लिए जाना है, हम इन एक ही नंबर देखते हैं,
लेकिन अब वे क्रमबद्ध क्रम में नहीं रह रहे हैं.
और हम तरह लागू n लॉग एन हे में किसी भी एल्गोरिथ्म का उपयोग करना चाहते हैं.
जो एल्गोरिथ्म तो आपको लगता है कि हम यहाँ लागू करना चाहिए? >> [छात्र] मर्ज तरह.
[Bowden] हाँ. मर्ज प्रकार हे (n लॉग एन) है, इसलिए है कि हम क्या करने जा रहे हैं.
और समस्या के लिए बहुत ही होने जा रहा है,
जहां यह आसानी से अपने आप में एक पुनरावर्ती समाधान करने के लिए उधार देता है.
हम एक समाधान के साथ चलने का भी ऊपर आ सकते हैं अगर हम चाहते हैं,
लेकिन recursion यहाँ आसान हो सकता है और हम recursion करना चाहिए.
मुझे लगता है कि हम मर्ज प्रकार के माध्यम से 1 चलना होगा,
हालांकि वहाँ मर्ज प्रकार पर एक सुंदर वीडियो पहले से ही है. [हँसी]
तो मर्ज तरह वहाँ रहे हैं - मैं इस कागज का इतना बर्बाद कर रहा हूँ.
ओह, वहाँ केवल एक ही छोड़ दिया है.
तो विलय.
ओह, 1, 3, 5.
ठीक है.
मर्ज दो अलग arrays लेता है.
व्यक्तिगत रूप से उन दो सरणियों दोनों क्रमबद्ध हैं.
तो इस सरणी, 1, 3, 5, हल. इस सरणी, 0, 2, 4, हल.
अब मर्ज करना चाहिए कि क्या उन्हें एक सरणी है कि खुद को क्रमबद्ध में गठबंधन है.
तो हम 6 आकार की एक सरणी है कि यह के अंदर किया जा रहा है इन तत्वों चाहते हैं
क्रमबद्ध क्रम में.
>> और इसलिए हम तथ्य यह है कि इन दो सरणियों हल कर रहे हैं का लाभ ले सकते
रैखिक समय में ऐसा करते हैं,
रैखिक समय अर्थ है अगर इस सरणी आकार x है और इस आकार y है,
तो कुल एल्गोरिथ्म हे (एक्स, वाई +) होना चाहिए. ठीक है.
सुझाव तो.
[छात्र] हम बाएँ से शुरू कर सकते हैं?
तो आप नीचे पहली और फिर 1 0 डाल दिया और फिर यहाँ आप 2 पर हैं.
तो यह है जैसे आप एक टैब है कि सही करने के लिए बढ़ रहा है की तरह है. >> [Bowden] हाँ.
इन दोनों arrays के लिए अगर हम सिर्फ leftmost तत्व पर ध्यान केंद्रित है.
क्योंकि दोनों arrays को हल कर रहे हैं, हम जानते हैं कि इन 2 तत्वों
या तो सरणी में छोटी तत्व हैं.
तो इसका मतलब है कि 1 उन 2 तत्वों के हमारे विलय सरणी में छोटी तत्व होना चाहिए.
यह सिर्फ इतना होता है कि छोटी से छोटी सही इस समय पर एक है.
तो हम 0 ले, यह बाईं तरफ डालने क्योंकि 0 1 कम से कम है,
इतना 0 ले, यह हमारी पहली स्थिति में डालने के लिए, और फिर हम इस अद्यतन
अब पहली तत्व पर ध्यान केंद्रित है.
और अब हम दोहराएँ.
तो अब हम 2 की तुलना करने के लिए और 1. 1 छोटा है, तो हम 1 डालने देंगे.
हम यह सूचक को अद्यतन करने के लिए इस आदमी को इंगित.
अब हम इसे फिर से ऐसा करते हैं, 2. यह अद्यतन करने के लिए, 2 इन 3, तुलना करेंगे.
इस अद्यतन, तो 4 और 5.
तो यह है कि मर्ज है.
>> यह बहुत स्पष्ट होना चाहिए कि यह रैखिक समय है क्योंकि हम सिर्फ एक बार प्रत्येक तत्व भर जाना.
और लागू करने मर्ज तरह इस कर रही है कि सबसे बड़ा कदम है.
और यह है कि मुश्किल नहीं है.
एक जोड़ी चीजों के बारे में चिंता करने की ज़रूरत है, हम कहते हैं कि हम 1, 2, 3, 4, 5, 6 विलय कर रहे थे.
इस मामले में हम परिदृश्य में जहां यह एक छोटे होने जा रहा है में खत्म होता है,
तो हम इस सूचक को अद्यतन करने के लिए, यह एक के लिए छोटे होने जा रहा है, इस अद्यतन,
यह एक छोटी है, और अब आप को पहचानने
जब आप वास्तव में तत्वों की है बाहर चलाने के लिए के साथ तुलना.
चूंकि हम पहले से ही इस पूरे सरणी इस्तेमाल किया है,
अब इस सरणी में सब कुछ है बस यहाँ में डाला है.
तो अगर हम कभी भी इस मुद्दे पर जहां हमारे arrays में से एक पूरी तरह से पहले से ही मिला दिया गया है में चलाते हैं,
तो हम सिर्फ अन्य सरणी के सभी तत्वों को लेने और उन्हें सरणी के अंत में डालें.
तो हम सिर्फ 4 सम्मिलित करते हैं, कर सकते हैं 5, 6. ठीक है.
वह एक बात को देखने के लिए बाहर है.
लागू कि 1 कदम होना चाहिए.
तब सॉर्ट मर्ज उस पर आधारित है, यह 2 कदम, 2 मूर्खतापूर्ण कदम है.
चलो बस इस सरणी दे.
तो प्रकार का मर्ज करने के लिए, चरण 1 recursively हिस्सों में सरणी को तोड़ने के लिए है.
तो हिस्सों में विभाजित इस सरणी.
अब हम 4, 15, 16, 50, और 8, 23, 42, 108 है.
और अब हम इसे फिर से करते हैं और हम halves में इन विभाजित.
मैं इसे इस तरफ बिल्कुल वैसा ही करूँगा.
15 4, और 16 तो, 50.
हम यहाँ पर एक ही बात करेंगे.
और अब हम हिस्सों में इसे फिर से विभाजित.
और हम 4, 15, 16, 50 है.
तो यह है कि हमारे आधार मामला है.
एक बार arrays 1 आकार के हैं, तो हम हिस्सों में बंटवारे के साथ बंद.
>> अब हम क्या इस के साथ क्या करते हो?
हम अंत में यह भी 8, 23, 42, और 108 में टूट जाएगा.
तो अब है कि हम इस बिंदु पर कर रहे हैं, अब कदम मर्ज तरह की दो सूचियों में जोड़े विलय.
इसलिए हम इन मर्ज करना चाहते हैं. हम सिर्फ मर्ज कहते हैं.
हम जानते हैं कि मर्ज क्रमबद्ध क्रम में इन वापस आ जाएगी.
4, 15.
अब हम इन मर्ज करना चाहते हैं, और उस क्रमबद्ध क्रम में उन लोगों के साथ एक सूची प्रदान करेगा,
16, 50.
हम उन विलय - 8, 23 और 42, 108 - मैं नहीं लिख सकते हैं.
तो हम मर्ज किए गए जोड़े एक बार किया है.
अब हम सिर्फ फिर से विलय.
अपने आप में सूचना है कि इन सूचियों में से प्रत्येक सॉर्ट किया जाता है,
और फिर हम सिर्फ इन सूचियों विलय 4 आकार की एक सूची है जो क्रमबद्ध प्राप्त कर सकते हैं
और इन दो सूचियों का विलय करने के लिए 4 आकार की एक सूची है कि हल है.
और अंत में, हम 4 आकार के उन दो सूचियों में विलय करने के लिए 8 आकार की एक सूची है कि हल है प्राप्त कर सकते हैं.
तो देखने के लिए कि इस समग्र n लॉग एन है, हम पहले से ही देखा है कि मर्ज रैखिक है,
इसलिए हम इन विलय के साथ जब काम कर रहे हैं, तो मर्ज की कुल लागत की तरह,
क्योंकि इन दो सूचियों के लिए सिर्फ 2 -
या अच्छी तरह से, यह पता हे, लेकिन यहाँ n सिर्फ इन 2 तत्वों, तो यह 2 है.
और इन 2 2 हो सकता है और इन 2 2 हो जाएगा और इन 2 2 हो जाएगा,
तो विलीन हो जाती है कि हम ऐसा करने की जरूरत के सभी भर में, हम अंत में पता कर रही है.
2 + 2 + 2 + 2 8 की तरह है, जो n है,
तो इस सेट में विलय की लागत n है.
और फिर यहाँ भी वही बात है.
हम इन 2 मर्ज करने के लिए, तो इन 2, और व्यक्तिगत रूप से इस मर्ज चार आपरेशन ले जाएगा,
इस मर्ज चार आपरेशनों ले, लेकिन एक बार फिर इन सब के बीच,
हम अंत में विलय n कुल बातें, और इसलिए इस कदम लेता है.
और इसलिए प्रत्येक स्तर n तत्वों विलय कर दिया जा रहा है लेता है.
>> और कितने स्तरों वहाँ रहे हैं?
हर स्तर पर, हमारे सरणी आकार 2 से बढ़ता है.
यहाँ हमारे arrays 1 आकार के होते हैं, वे यहाँ 2 आकार की हैं, वे यहाँ 4 आकार के कर रहे हैं,
और अंत में, वे 8 आकार के हैं.
इतने के बाद से दोगुनी है, वहाँ के लिए लॉग n इन स्तरों के एक कुल को होने जा रहे हैं.
तो लॉग n स्तर, प्रत्येक व्यक्ति के स्तर ले n कुल आपरेशनों के साथ,
हम एक n लॉग एन एल्गोरिथ्म मिलता है.
प्रश्न?
लोगों को पहले से ही यह कैसे लागू करने पर प्रगति की है?
एक राज्य में पहले से ही किसी को भी, जहां मैं सिर्फ अपने कोड खींच सकते हैं?
मैं एक मिनट दे सकते हैं.
यह एक करने के लिए लंबे समय तक होने जा रहा है.
मैं अत्यधिक पुनरावृत्ति की सिफारिश -
आप मर्ज के लिए recursion नहीं करना है
क्योंकि मर्ज के लिए recursion करने के लिए, आप करने के लिए विभिन्न आकारों की एक गुच्छा के पास जा रहे हैं.
तुम्हें पता है, लेकिन यह कष्टप्रद है.
लेकिन recursion ही प्रकार के लिए बहुत आसान है.
तुम बस सचमुच तरह बाईं आधे पर कॉल, सही पर आधा तरह. ठीक है.
किसी को भी कुछ भी मैं अभी तक खींच सकता है?
वरना मैं एक मिनट दे दूँगा.
ठीक है.
किसी को कुछ हम साथ काम कर सकते है?
वरना हम सिर्फ इस के साथ काम करेंगे और फिर वहाँ से विस्तार.
>> किसी को भी इस से अधिक है कि मैं ऊपर खींचने के लिए कर सकते हैं?
[छात्र] हाँ. आप मेरा खींच सकते हैं. >> सभी सही.
हाँ!
[छात्र] स्थितियों की एक बहुत थे. >> ओह, गोली मार. आप कर सकते हैं -
[छात्र] मैं इसे बचाने के लिए है. >> हाँ.
तो हम मर्ज अलग नहीं किया.
ओह, लेकिन यह इतना बुरा नहीं है.
ठीक है.
तो तरह ही सिर्फ mergeSortHelp बुला.
हमें समझाने mergeSortHelp क्या करता है.
[छात्र] MergeSortHelp बहुत ज्यादा दो मुख्य चरण करता है,
जो सरणी के प्रत्येक आधा तरह और फिर उन दोनों के मर्ज है.
[Bowden] ठीक है, तो मुझे एक दूसरी दे.
मुझे लगता है कि इस - >> [छात्र] मैं करने की जरूरत -
हाँ. मैं कुछ याद आ रही है.
मर्ज में, मुझे पता है कि मैं एक नई सरणी बनाने की जरूरत है
क्योंकि मैं यह जगह में नहीं कर सका. हाँ. >> तुम नहीं कर सकते हैं. सुधारें.
[छात्र] तो मैं एक नई सरणी बनाने.
मैं फिर से बदलने के लिए मर्ज अंत में भूल गया था.
ठीक है. हम एक नई सरणी की जरूरत है.
मर्ज सॉर्ट में, यह लगभग हमेशा सच.
एक बेहतर समय के लिहाज से एल्गोरिथ्म की लागत का एक हिस्सा
लगभग हमेशा के लिए थोड़ा और अधिक स्मृति का उपयोग करने की आवश्यकता होगी.
यहाँ तो, कोई फर्क नहीं पड़ता कि तुम कैसे करते छंटाई संविलय
आप अनिवार्य रूप से कुछ अतिरिक्त स्मृति का उपयोग करने की आवश्यकता होगी.
वह या वह एक नई सरणी बनाया.
और फिर आप कहते हैं कि अंत में हम सिर्फ मूल सरणी में नई सरणी को कॉपी करने की जरूरत है.
[छात्र] मुझे ऐसा लगता है, हाँ.
मैं अगर कि संदर्भ या जो कुछ भी द्वारा गिनती करने के मामले में यह काम करता है पता नहीं है -
हाँ, यह काम करेगा. >> [छात्र] ठीक है.
क्या आप इस चलाने की कोशिश? >> [छात्र] नहीं, अभी नहीं. ठीक है. >>
इसे चलाने का प्रयास करें, और उसके बाद मैं इसके बारे में एक पल के लिए बात करेंगे.
[छात्र] मैं सभी समारोह प्रोटोटाइप और सब कुछ करने की जरूरत है, हालांकि सही?
समारोह प्रोटोटाइप. हाँ - ओह, आप की तरह मतलब है.
क्रमबद्ध करें mergeSortHelp बुला रही है.
>> इतने में आदेश के लिए तरह mergeSortHelp कॉल करने के लिए, mergeSortHelp या तो है चाहिए परिभाषित किया गया है
तरह से पहले या हम सिर्फ प्रोटोटाइप की जरूरत है. बस कॉपी और पेस्ट करें कि.
और इसी प्रकार, mergeSortHelp मर्ज के लिए बुला रहा है,
लेकिन मर्ज अभी तक परिभाषित नहीं किया गया है, तो हम सिर्फ दो mergeSortHelp पता है
कि है कि क्या मर्ज करते की तरह लग रहा है, और वह है कि.
MergeSortHelp तो.
हम यहाँ एक मुद्दा है, जहां हम कोई आधार मामला है.
MergeSortHelp पुनरावर्ती है, इसलिए किसी भी पुनरावर्ती समारोह
आधार मामले के कुछ प्रकार की जरूरत को पता है जब recursively ही बुला रोकने के लिए जा रहा है.
हमारे आधार मामला क्या हो रहा है यहाँ हो? हाँ.
[छात्र] यदि आकार 1 है? >> [Bowden] हाँ.
तो जैसे हम सही वहाँ देखा, हम बंटवारे arrays बंद कर दिया
एक बार हम 1 आकार, जो अनिवार्य रूप से खुद को हल कर रहे हैं के arrays में मिला.
तो अगर आकार 1 के बराबर होती है, हम जानते हैं कि सरणी क्रमबद्ध पहले से ही है,
तो हम सिर्फ लौट सकते हैं.
>> सूचना है कि शून्य है, तो हम विशेष रूप से कुछ भी वापस नहीं करते हैं, हम सिर्फ वापस.
ठीक है. इसलिए कि हमारे आधार मामला है.
मुझे लगता है कि हमारे आधार के मामले में भी अगर हम 0 आकार की एक सरणी विलय होता है हो सकता है,
हम शायद कुछ बिंदु पर रोक चाहते हैं,
इसलिए हम अभी कम से कम 2 या कम से कम या 1 के बराबर आकार कह सकते हैं
इतना है कि यह किसी भी श्रृंखला के लिए काम करेंगे.
ठीक है.
इसलिए कि हमारे आधार मामला है.
अब आप हमें मर्ज के माध्यम से चलना चाहते हो?
इन सभी मामलों का क्या मतलब है?
यहाँ तक, हम सिर्फ एक ही विचार कर रहे हैं,
[छात्र] मैं सभी mergeSortHelp कॉल के साथ आकार पारित हो की जरूरत है.
मैं एक अतिरिक्त प्राथमिक आकार के रूप में जोड़ा गया है और यह वहाँ / 2 आकार की तरह नहीं है.
[Bowden] ओह, 2 / आकार, आकार / 2. >> [छात्र] हाँ, और भी ऊपर समारोह में के रूप में अच्छी तरह से.
[Bowden] यहाँ? >> [छात्र] आकार बस. >> [Bowden] ओह. आकार, आकार? >> [छात्र] हाँ.
[Bowden] ठीक है.
मुझे एक पल के लिए लगता है.
क्या हम एक मुद्दे में चलाने?
हम हमेशा 0 के रूप में कर रहे हैं बाईं इलाज. >> [छात्र] नहीं
यह भी गलत है. माफ़ कीजिए. यह शुरू होना चाहिए. हाँ.
[Bowden] ठीक है. मुझे लगता है कि बेहतर पसंद है.
और अंत. ठीक है.
तो अब तुम हमें मर्ज के माध्यम से चलना चाहते हो? >> [छात्र] ठीक है.
मैं सिर्फ इस नई सरणी के माध्यम से चल रहा हूँ कि मैंने बनाया है.
इसका आकार सरणी के हिस्से के आकार है कि हम हल किया जा रहा है
और तत्व है कि मैं नई सरणी कदम में रखा जाना चाहिए खोजने की कोशिश कर रहा है.
तो क्या है कि, पहले मैं अगर सरणी के बाईं आधा किसी भी अधिक तत्वों की जाँच कर रहा हूँ,
और अगर ऐसा नहीं है, तो आप है कि किसी और शर्त है, जो सिर्फ कहते हैं, नीचे जाने के
ठीक है, यह सही सरणी में हो सकता है, और चाहिए हम newArray की वर्तमान सूचकांक में डाल देता हूँ कि.
>> और तो अन्यथा, मैं अगर सरणी के दाईं ओर भी समाप्त हो गया है की जाँच कर रहा हूँ,
जो मामले में मैं सिर्फ बाईं में डाल दिया.
यह वास्तव में आवश्यक नहीं हो सकता. मैं ठीक से नहीं कह सकता.
लेकिन वैसे भी, अन्य दो चेक जिनमें से दो को छोड़ दिया है या सही में छोटे होते हैं.
और प्रत्येक मामले में भी, मैं incrementing रहा हूँ जो भी प्लेसहोल्डर मैं वेतन वृद्धि.
[Bowden] ठीक है.
यह अच्छा लग रहा है.
क्या किसी को टिप्पणी या चिंताओं या प्रश्नों है?
या यह पाँच की तरह लग रहा है - चार मामलों में है कि हम बस में चीजों को लाने के लिए है तो
लेकिन हम विचार करना है कि क्या छोड़ दिया सरणी बातें हम विलय की आवश्यकता के बाहर चला गया है,
क्या सही सरणी बातें हम विलय की आवश्यकता के बाहर चला गया है -
मैं कुछ भी नहीं है पर इशारा कर रहा हूँ.
तो बम्माँ सरणी बातें बाहर चला गया है या सही सरणी बातें बाहर चला गया है.
उन दो मामलों हैं.
हम भी क्या छोड़ दिया बात की कम से कम सही बात है तुच्छ मामले की जरूरत है.
तो हम करने के लिए छोड़ दिया बात का चयन करना चाहते हैं.
उन मामलों रहे हैं.
तो यह सही था तो, वह है कि.
ऐरे छोड़ दिया है. यह 1, 2, 3. ठीक है. तो हाँ, उन चार बातें हम करना चाहते हो सकता हैं.
और हम एक चलने का समाधान से अधिक नहीं जाना होगा.
मैं सुझा नहीं होगा -
मर्ज तरह के एक समारोह में कहा कि दोनों पूंछ पुनरावर्ती नहीं है का एक उदाहरण है,
यह आसान नहीं है यह पूंछ पुनरावर्ती बनाना नहीं है,
लेकिन यह भी बहुत आसान बनाने के लिए यह चलने का नहीं है.
यह बहुत आसान है.
मर्ज की तरह के इस कार्यान्वयन,
मर्ज करने के लिए, कोई फर्क नहीं पड़ता कि तुम क्या करते हो, आप मर्ज का निर्माण करने के लिए जा रहे हैं.
>> तो मर्ज मर्ज के शीर्ष पर बनाया तरह बारी बारी से सिर्फ इन तीन लाइनों.
Iteratively, यह अधिक कष्टप्रद और अधिक कठिन करने के बारे में सोचना है.
नोटिस लेकिन कि यह mergeSortHelp के बाद से पुनरावर्ती पूंछ नहीं है - जब वह खुद कहता है -
यह अभी भी इस पुनरावर्ती कॉल रिटर्न के बाद काम करने की जरूरत है.
तो इस ढेर फ्रेम करने के लिए इस फोन करने के बाद भी मौजूद जारी रहना चाहिए.
और फिर जब आप यह कहते हैं, ढेर फ्रेम करने के लिए मौजूद जारी रहना चाहिए
क्योंकि कि फोन करने के बाद भी, हम अभी भी विलय की आवश्यकता है.
और यह nontrivial इस पूंछ पुनरावर्ती.
प्रश्न?
सही सभी.
तो वापस जाने के लिए तरह - ओह, वहाँ दो चीजें मैं दिखाना चाहते है. ठीक है.
तरह करने के लिए वापस जा रहे हैं, हम इस जल्दी करना होगा.
या खोज. तरह? क्रमबद्ध करें. हाँ.
सॉर्ट के शुरुआत करने के लिए वापस जा रहे हैं.
हम है कि एक प्रकार सरणी एल्गोरिथ्म किसी भी एल्गोरिथ्म का उपयोग करना चाहते हैं
n हे.
तो यह कैसे संभव है? क्या किसी को किसी भी प्रकार है -
मैं पर पहले संकेत दिया था -
अगर हम के बारे में n लॉग एन से पता हे सुधार करने के लिए कर रहे हैं,
हम हमारे एल्गोरिथ्म समय के लिहाज से सुधार हुआ है,
जिसका मतलब है कि हम क्या करने के लिए उस के लिए बनाने की जरूरत करने जा रहे हैं?
[स्पेस] छात्र. >> हाँ. हम और अधिक स्थान का उपयोग करने के लिए होने जा रहे हैं.
और भी अधिक स्थान नहीं बस, यह तेजी से और अधिक स्थान है.
तो मुझे लगता है कि इस प्रकार से एल्गोरिथ्म के छद्म कुछ छद्म polynom
छद्म - मैं याद नहीं कर सकते. छद्म कुछ.
लेकिन यह इसलिए है क्योंकि हम इतना अंतरिक्ष का उपयोग करने की जरूरत है
कि यह प्राप्त लेकिन यथार्थवादी नहीं है.
>> और कैसे हम इस लक्ष्य को हासिल करते हैं?
हम इस लक्ष्य को हासिल कर सकते हैं अगर हम गारंटी कर सकते हैं कि सरणी में किसी विशेष तत्व
एक निश्चित आकार से नीचे है.
इसलिए चलो बस का कहना है कि आकार 200 है,
एक सरणी में किसी भी तत्व 200 आकार से नीचे है.
और यह वास्तव में बहुत यथार्थवादी है.
तुम बहुत आसानी से एक सरणी है कि आप यह सब कुछ पता कर सकते हैं
कुछ संख्या की तुलना में कम हो रहा है.
जैसे कि अगर आप कुछ बिल्कुल भारी वेक्टर या कुछ है
लेकिन आप जानते हैं कि सब कुछ करने के लिए 0 और 5 के बीच होने जा रहा है,
तो यह काफी तेजी से यह करने के लिए होने जा रहा है.
और तत्वों में से किसी पर बाध्य 5 है,
तो इस बाध्य है, वह यह है कि आप कितना स्मृति का उपयोग करने के लिए होने जा रहे हैं.
तो बाध्य 200 है.
सिद्धांत रूप में वहाँ हमेशा एक ही है के बाद से केवल एक पूर्णांक 4 अरब तक हो सकता है,
लेकिन यह है कि फिर हम अंतरिक्ष का उपयोग किया था के बाद से अवास्तविक है
4 अरब के आदेश पर. तो यह है कि अवास्तविक है.
लेकिन यहाँ हम हमारे बाध्य कहूँगा 200 है.
n हे में कर चाल है कि हम एक और आकार की गिनती ही बुलाया सरणी बनाने.
तो वास्तव में, इस के लिए एक सरल तरीका है - मैं वास्तव में अगर बजना यह नहीं पता नहीं है.
लेकिन बहुत कम से कम जीसीसी में - मैं संभालने बजना यह भी है -
यह सिर्फ पूरे सरणी को प्रारंभ करने के लिए 0s हो जाएगा.
तो अगर मैं ऐसा नहीं करना चाहती, तो मैं अलग के लिए कर सकता है (int i = 0;
मैं <बाध्य, मैं + +) मायने रखता है और मैं [] = 0;
तो अब सब कुछ 0 से प्रारंभ है.
मैं अपने सरणी पर पुनरावृति,
और मैं क्या कर रहा हूँ मैं प्रत्येक की संख्या की गिनती कर रहा हूँ - चलो यहाँ नीचे जाना.
हम में से 4, 15, 16, 50, 8, 23, 42, 108 है.
मैं भरोसा कर रहा हूँ क्या उन तत्वों में से प्रत्येक की घटनाओं की संख्या है.
चलो वास्तव में यहाँ कुछ और अधिक कुछ दोहराता है साथ जोड़.
मूल्य तो हम यहाँ है, कि के मूल्य सरणी [i] जा रहा है.
तो वैल 4 या 8 या जो कुछ भी हो सकता है.
और अब मैं भरोसा कर रहा हूँ कि मूल्य के कितने मैंने देखा है,
इतना मायने रखता है [वैल] + +;
इस के बाद किया जाता है, की गिनती के लिए 0001 की तरह कुछ लग रहा है.
चलो मायने रखता करना [वैल] - 1 + बाध्य.
>> अब जब कि सिर्फ तथ्य यह है कि हम 0 से शुरू कर रहे हैं के लिए खाते.
तो 200 अगर हमारी सबसे बड़ी संख्या होने जा रहा है,
तो 0 200 201 बातें है.
इतना मायने रखता है, यह 00001 की तरह लग रही है क्योंकि हम एक 4 करने के लिए होगा.
फिर हम 0001 जहां हम गिनती के 8 सूचकांक में 1 एक होगा होगा.
हम गिनती के 23 सूचकांक में 2 होगा.
हम गिनती के 42 सूचकांक में 2 होगा.
तो हम गिनती का उपयोग कर सकते हैं.
तो num_of_item = मायने रखता है [i].
और इसलिए यदि num_of_item 2 है, इसका मतलब है कि हम संख्या मैं 2 सम्मिलित करना चाहते हैं
हमारे क्रमबद्ध सरणी में.
तो हम कितनी दूर हम सरणी में कर रहे हैं का ट्रैक रखने की जरूरत है.
तो सूचकांक = 0.
ऐरे - मैं सिर्फ यह लिख देंगे.
गणना -
सरणी [सूचकांक + +] = मैं;
यह है कि मैं क्या चाहता हूँ? मुझे लगता है कि मैं क्या चाहता हूँ.
हाँ, यह अच्छा लग रहा है. ठीक है.
तो हर कोई समझ करता है मेरे मायने रखता सरणी के उद्देश्य क्या है?
यह इन नंबरों में से प्रत्येक की घटनाओं की संख्या की गिनती है.
तो मैं जो मायने रखता है सरणी iterating कर रहा हूँ,
और मायने रखता सरणी में ith स्थिति
मैं की संख्या कि मेरी क्रमबद्ध सरणी में दिखाई चाहिए है.
यही कारण है कि 4 की गिनती के लिए एक होने जा रहा है
और 8 की गिनती के लिए एक होने जा रहा है, 23 की गिनती के लिए 2 होने जा रहा है.
तो है कि मैं उनमें से कितने मेरी क्रमबद्ध सरणी में सम्मिलित करना चाहते हैं.
तो मैं सिर्फ इतना है कि.
मैं num_of_item डालने हूँ मैं मेरे क्रमबद्ध सरणी में है.
>> प्रश्न?
तो फिर, यह रैखिक समय है, जब से हम सिर्फ इस पर एक बार पुनरावृति
लेकिन यह भी क्या इस संख्या के लिए होता है में रैखिक है,
और इसलिए यह भारी अपने ही क्या है पर निर्भर करता है.
200 का एक ही साथ, जो कि बुरा नहीं है.
यदि अपने ही 10,000 होने जा रहा है, तो यह है कि एक छोटे से बदतर है,
लेकिन अगर अपने ही करने के लिए 4 अरब हो सकता है, जा रहा है कि पूरी तरह से अवास्तविक है
और इस सरणी के लिए चार अरब आकार, जो अवास्तविक है किया जा रहा है.
तो वह है कि. प्रश्न?
[अश्राव्य छात्र प्रतिक्रिया] ठीक है. >>
मैं एक अन्य बात का एहसास हुआ है जब हम के माध्यम से जा रहे थे.
मुझे लगता है कि समस्या लुकास और शायद हर एक एक हमने देखा था.
मैं पूरी तरह से भूल गया.
केवल एक चीज मैं पर टिप्पणी करना चाहता था यह है कि जब आप इंडेक्स की तरह चीजों के साथ काम कर रहे हैं,
आप यह वास्तव में कभी नहीं देखने के लिए जब आप एक पाश के लिए लिख रहे हैं,
लेकिन तकनीकी रूप से, आप इन सूचकांकों के साथ जब भी काम कर रहे हैं,
आप बहुत ज्यादा हमेशा अहस्ताक्षरित integers के साथ सौदा करना चाहिए.
इसका कारण यह है कि जब आप हस्ताक्षरित integers के साथ काम कर रहे हैं,
इसलिए यदि आप 2 integers पर हस्ताक्षर किए है और आप उन्हें एक साथ जोड़ें
और वे बहुत बड़ा खत्म होता है, तो आप एक नकारात्मक संख्या के साथ खत्म होता है.
तो है कि पूर्णांक अतिप्रवाह क्या है.
>> अगर मैं 2 अरब और 1 अरब जोड़ने के लिए, मैं नकारात्मक 1 अरब के साथ खत्म होता है.
यही कारण है कि कैसे integers कंप्यूटर पर काम करते हैं.
प्रयोग के साथ समस्या तो -
यह ठीक है छोड़कर यदि कम करने के लिए 2 अरब होना होता है और अप करने के लिए 1 अरब होता है,
तो इस के लिए एक अरब नकारात्मक होने जा रहा है और फिर हम को विभाजित करने के लिए जा रहे हैं कि 2 से
और नकारात्मक 500 मिलियन के साथ खत्म होता है.
तो यह केवल एक मुद्दा अगर आप एक सरणी के माध्यम से खोज हो होता है
चीजों के अरबों के.
लेकिन अगर कम + अतिप्रवाह के लिए होता है, तो यह एक समस्या है.
के रूप में जल्द ही के रूप में हम उन्हें अहस्ताक्षरित, तो 2 अरब से अधिक 1 3 अरब डॉलर का है.
3 अरब 2 से विभाजित 1.5 अरब है.
तो जैसे ही वे अहस्ताक्षरित हो, सब कुछ सही है.
और इतना है कि यह भी एक मुद्दा है जब आप loops के लिए लिख रहे हैं,
और वास्तव में, यह शायद यह स्वचालित रूप से करता है.
यह वास्तव में सिर्फ तुम पर चिल्लाना होगा.
तो अगर इस संख्या भी सिर्फ एक पूर्णांक में बड़ा है, लेकिन यह एक अहस्ताक्षरित पूर्णांक में फिट होगा,
यह आप पर चिल्लाना होगा तो, यही कारण है कि आप इस मुद्दे में वास्तव में कभी नहीं चला.
आप देख सकते हैं कि एक सूचकांक नकारात्मक हो सकता है कभी नहीं जा रहा है,
और इसलिए जब आप एक सरणी पर iterating कर रहे हैं,
आप लगभग हमेशा int अहस्ताक्षरित मैं कह सकते हैं, लेकिन आप वास्तव में नहीं है.
बातें करने के लिए बहुत ज्यादा बस के रूप में अच्छी तरह से काम करने के लिए जा रहे हैं.
ठीक है. [फुसफुसाती] समय क्या हुआ है?
आखिरी बात मैं दिखाना चाहता था और मैं सिर्फ यह वास्तव में जल्दी करूँगा.
तुम्हें पता है कि हम तो हम # 5 या कुछ और के रूप में अधिकतम परिभाषित कर सकते हैं परिभाषित किया है?
चलो MAX नहीं है. # 200 के रूप में ही परिभाषित करते हैं. यही कारण है कि हम क्या से पहले किया था.
यह एक निरंतर को परिभाषित करता है, जो सिर्फ नकल की और चिपकाया जा रहा है
जहाँ हम करने के लिए बाध्य लिखने होगा.
>> तो हम वास्तव में # को परिभाषित करता है के साथ और अधिक कर सकते हैं.
हम # कार्यों को परिभाषित कर सकते हैं.
वे वास्तव में कार्य नहीं कर रहे हैं, लेकिन हम उन्हें कार्य कॉल होगा.
एक उदाहरण MAX (एक्स, वाई) की तरह कुछ होगा (: x x <y y) के रूप में परिभाषित किया गया है. ठीक है.
तो तुम त्रिगुट ऑपरेटर सिंटैक्स के लिए इस्तेमाल किया जाना चाहिए,
लेकिन एक्स y से कम है? Y लौटें, और लौटने के एक्स.
तो आप देख सकते हैं यह एक अलग समारोह कर सकते हैं,
और समारोह की तरह bool अधिकतम 2 तर्क लेता है हो सकता है, यह वापस.
यह एक सबसे आम लोगों को मैं इस तरह से किया है. हम उन्हें मैक्रोज़ कहते हैं.
यह एक मैक्रो है.
यह सिर्फ इसके लिए वाक्यविन्यास है.
आप एक मैक्रो लिखने के लिए आप जो चाहते हैं कर सकते हैं.
आप अक्सर debugging printfs और सामान के लिए मैक्रोज़ देखते हैं.
तो printf का एक प्रकार है, वहाँ सी में विशेष स्थिरांक तरह लाइन अधोडैस अधोडैस हैं,
2 रेखांकित करता है लाइन अधोडैस,
और वहाँ भी मुझे लगता है कि 2 समारोह को रेखांकित करता है. कि यह हो सकता है. कुछ ऐसा ही.
उन चीजों को समारोह के नाम के साथ प्रतिस्थापित किया जाएगा
या लाइन है कि आप पर कर रहे हैं की संख्या.
अक्सर, आप debugging printfs कि यहाँ नीचे मैं तो बस लिख सकता है लिखने
डिबग और यह लाइन नंबर और समारोह में कहा कि मैं में होने मुद्रित करेगा
कि यह है कि डीबग कथन का सामना करना पड़ा.
और तुम भी अन्य बातों के मुद्रित कर सकते हैं.
तो एक बात आप के लिए बाहर देखना चाहिए है अगर मैं # DOUBLE_MAX को परिभाषित होता है
* 2 * y और 2 की तरह कुछ के रूप में है.
तो जो भी कारण के लिए, आप एक बहुत है कि क्या होता है.
तो यह एक मैक्रो बनाते हैं.
यह वास्तव में टूट गया है.
मैं यह DOUBLE_MAX (3, 6) की तरह कुछ कर रही द्वारा फोन होगा.
तो क्या वापस आ जाना चाहिए?
12 [] छात्र.
हाँ, 12, लौटा किया जाना चाहिए और 12 वापस आ रहा है.
एक्स 3 के लिए बदल दिया जाता है, 6 y के लिए बदल दिया जाता है, और हम 2 * 6, जो 12 है लौटने के.
अब इस बारे में क्या? क्या वापस आ जाना चाहिए?
14 [] छात्र. >> आदर्श रूप में, 14.
मुद्दा यह है कि कैसे हैश काम को परिभाषित करता है, याद है, यह एक शाब्दिक कॉपी और पेस्ट
बहुत ज्यादा सब कुछ है, तो इस के रूप में व्याख्या की जा जा रहा है
3 1 से अधिक 6, 2 1 बार से अधिक 6, 2 3 बार की तुलना में कम है.
>> इस कारण के लिए तो आप लगभग हमेशा कोष्ठक में सब कुछ लपेटो.
किसी भी चर आप लगभग हमेशा कोष्ठक में लपेट.
ऐसे मामलों में जहाँ आप के लिए नहीं है, जैसे मैं जानता हूँ कि मैं यहाँ करने की ज़रूरत नहीं
क्योंकि की तुलना में कम है बहुत ज्यादा हमेशा सिर्फ काम करने के लिए जा रहा है,
हालांकि यह भी सच नहीं हो सकता है.
अगर वहाँ कुछ DOUBLE_MAX (1 == 2) की तरह हास्यास्पद है,
तो यह है कि कम से कम 3 1 के साथ जगह मिल जा रहा है 2 के बराबर होती है के बराबर होती है,
और यदि ऐसा है तो फिर यह 3 1 कम से कम करने के लिए जा रहा है, यह नहीं है कि बराबर 2,
जो नहीं है कि हम क्या चाहते हैं.
इसलिए किसी भी ऑपरेटर पूर्वता समस्याओं को रोकने के क्रम में,
हमेशा कोष्ठक में लपेट.
ठीक है. और वह यह है, 5:30.
यदि आप pset पर किसी भी सवाल है, हमें पता है.
यह मजेदार होना चाहिए, और हैकर संस्करण भी अधिक यथार्थवादी है
पिछले साल के हैकर संस्करण की तुलना में, इसलिए हमें उम्मीद है कि आप में से बहुत इसे करने की कोशिश है.
पिछले साल बहुत भारी था.
>> [CS50.TV]