पुनरावृत्ति का वर्णन करने के लिए मैं मास्टर प्रमेय का उपयोग कैसे करूं?

Question

हाल ही में मैं रिकर्सन का अध्ययन कर रहा हूं; इसे कैसे लिखना है, इसका विश्लेषण करना आदि। मैंने थोड़ी देर के लिए सोचा है कि पुनरावृत्ति और पुनरावृत्ति एक ही बात थी, लेकिन हाल ही में होमवर्क असाइनमेंट और क्विज़ पर कुछ समस्याएं मुझे सोच रही हैं कि थोड़ा अंतर है, कि 'पुनरावृत्ति' तरीका है एक पुनरावर्ती कार्यक्रम या समारोह का वर्णन करें।

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

तो, कुछ सवाल: कहते हैं कि तुम इस पुनरावृत्ति दिया जाता है की सुविधा देता है:

आर (एन) = 2 * आर (n-2) + r (n-1);
आर (1) = r (2) = 1

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

अब, मान लें कि आपको पुनरावृत्ति, टी (एन), पिछले पुनरावृत्ति से बनाए गए कार्यक्रम द्वारा किए गए जोड़ों की संख्या के लिए पुनरावृत्ति खोजने के लिए कहा गया था। मैं देख सकता हूं कि बेस केस शायद टी (1) = टी (2) = 0 होगा, लेकिन मुझे यकीन नहीं है कि वहां से कहां जाना है।

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

संपादित करें: ठीक है, मैंने अपने पिछले कुछ असाइनमेंट्स को देखा है जहां से पूछा गया है कि 'पुनरावृत्ति खोजने के लिए', जो इस प्रश्न का हिस्सा है, मुझे पोस्ट परेशानी हो रही है साथ में।

पुनरावृत्ति है कि सबसे अच्छा तरह से वर्णित कार्यक्रम टुकड़ा

int example(A, int l, int r) { 
    if (l == r) 
    return 2; 
    return (A[l] + example(A, l+1, r); 
} 

Answer 1

कुछ साल पहले, मोहम्मद अकरा और लोय बज़ी ने एक परिणाम साबित किया जो मास्टर विधि को सामान्यीकृत करता है - यह लगभग हमेशा बेहतर होता है। आप वास्तव में मास्टर प्रमेय अब और का उपयोग नहीं किया जाना चाहिए ...

उदाहरण के लिए देखें, इस writeup: http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

असल में, अखबार में, 1 समीकरण की तरह लग रहे करने के लिए अपने पुनरावृत्ति गुणांक बंद लेने मिलता है, और प्रमेय में अभिव्यक्ति एकीकृत 1.

Answer 2

(जब एल == 1 और आर == n के साथ कहा जाता है) में इसके संचालन की संख्या आपका एक रिकर्सिव फ़ंक्शन का उपयोग करके कोड में लिखा गया विधि, इस तरह दिखेगा:

function r(int n) 
{ 
    if (n == 2) return 1; 
    if (n == 1) return 1; 
    return 2 * r(n-2) + r(n-1); // I guess we're assuming n > 2 
} 

मैं su नहीं हूँ फिर से "पुनरावृत्ति" क्या है, लेकिन एक रिकर्सिव फ़ंक्शन बस एक है जो स्वयं को कॉल करता है।

रिकर्सिव कार्यों एक भागने खंड की जरूरत है - एक स्टैक ओवरफ़्लो त्रुटि को रोकने के लिए (कुछ गैर पुनरावर्ती मामले "यदि n == 1 वापसी 1", उदाहरण के लिए) (अर्थात, समारोह इतना है कि दुभाषिया स्मृति या अन्य संसाधनों)

Answer 3

एक साधारण प्रोग्राम है जो लागू होता है कि विचार करेंगे की तरह खत्म हो जाता है कहा जाता हो जाता है:

public int r(int input) { 
    if (input == 1 || input == 2) { 
     return 1; 
    } else { 
     return 2 * r(input - 2) + r(input -1) 
    } 
} 

आप यह भी सुनिश्चित है कि बनाने के लिए की आवश्यकता होगी इनपुट एक अनंत रिकर्सन का कारण नहीं बन रहा है, उदाहरण के लिए, यदि शुरुआत में इनपुट 1 से कम था। यदि यह मान्य केस नहीं है, तो एक त्रुटि लौटाएं, यदि यह मान्य है, तो उपयुक्त मान वापस करें।

Answer 4

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

और, उन्हें हल करने के पीछे उद्देश्य, मुझे लगता है कि एक रिकर्सिव परिभाषा से ऐसा नहीं है। कहें कि क्या आपके पास सभी एन> 0 के लिए टी (0) = 2 और टी (एन) = 2 + टी (एन -1) था, आपको अभिव्यक्ति से जाना होगा "टी (एन) = 2 + टी (एन -1) "एक की तरह" 2 एन + 2 "।

सूत्रों: 1) "ग्राफ़ थ्योरी के साथ असतत गणित - द्वितीय संस्करण", एडगर जी Goodair और माइकल एम Parmenter 2) "कंप्यूटर एल्गोरिदम सी ++," द्वारा एलिस होरोवित्ज, सरताज साहनी, और Sanguthevar Rajasekaran द्वारा।

Answer 5

जाकारी:

कहते हैं कि तुम इस पुनरावृत्ति दिया जाता है की सुविधा देता है:

आर (एन) = 2 * आर (n-2) + r (n-1); आर (1) = आर (2) = 1

क्या यह वास्तव में मास्टर प्रमेय के रूप में है? यदि हां, तो शब्दों में, क्या यह कह रहा है?

मुझे लगता है कि अपने आवर्ती संबंध कह रहा है कि अपनी पैरामीटर के रूप में "n" के साथ "आर" के समारोह के लिए, आप जो भी वें पर मिल (डेटा की कुल संख्या आप डाल रहे सेट का प्रतिनिधित्व) है कि डेटा-सेट की स्थिति n-1 वें स्थिति के साथ-साथ एन-2 वें स्थान का परिणाम जो भी गैर-पुनरावर्ती कार्य किया जा रहा है, का उत्पादन होता है। जब आप पुनरावृत्ति संबंध को हल करने का प्रयास करते हैं, तो आप इसे इस तरह से व्यक्त करने की कोशिश कर रहे हैं जिसमें रिकर्सन शामिल नहीं है।

हालांकि, मुझे नहीं लगता कि यह मास्टर प्रमेय विधि के लिए सही रूप में है। आपका कथन "निरंतर गुणांक के साथ दूसरा क्रम रैखिक पुनरावृत्ति संबंध" है। जाहिर है, मेरी पुरानी असतत गणित पाठ्यपुस्तक के मुताबिक, पुनरावृत्ति संबंध को हल करने के लिए आपको वह रूप है जो आपको चाहिए।

यहाँ प्रपत्र है कि वे दे:

r(n) = a*r(n-1) + b*r(n-2) + f(n) 

'एक' और 'बी' के लिए कुछ स्थिरांक और च कर रहे हैं (एन) एन के कुछ कार्य है। आपके कथन में, एक = 1, बी = 2, और एफ (एन) = 0. जब भी, एफ (एन) शून्य के बराबर होता है तो पुनरावृत्ति संबंध को "homogenous" के रूप में जाना जाता है। तो, आपकी अभिव्यक्ति समरूप है।

मुझे नहीं लगता कि आप मास्टर विधि थियोर्म का उपयोग कर एक समरूप पुनरावृत्ति संबंध को हल कर सकते हैं क्योंकि f (n) = 0. मास्टर विधि प्रमेय के लिए कोई भी मामला इसके लिए अनुमति नहीं देता है क्योंकि एन-टू-द-पावर- कुछ भी शून्य के बराबर नहीं हो सकता है। मैं गलत हो सकता था, क्योंकि मैं वास्तव में इस पर एक विशेषज्ञ नहीं हूं लेकिन मुझे नहीं लगता कि मास्टर विधि का उपयोग कर एक समरूप पुनरावृत्ति संबंध को हल करना संभव है।

मुझे लगता है कि है कि एक सजातीय आवर्तन संबंध हल करने के लिए जिस तरह से 5 चरणों से जाने के लिए है:

1) फार्म विशेषता समीकरण है, जो के रूप के बारे में कुछ है:

x^k - c[1]*x^k-1 - c[2]*x^k-2 - ... - c[k-1]*x - c[k] = 0 

आप तो 'तो ही आप केवल द्विघात समीकरण में अपना समीकरण बदलने के लिए जहां

x^2 - a*x - b = 0 

यह बीईसी है की जरूरत है अपने सजातीय आवर्तन संबंध में 2 पुनरावर्ती उदाहरणों मिला लिया है ause

r(n) = a*r(n-1) + b*r(n-2) 

के रूप की एक आवर्ती संबंध

r(n) - a*r(n-1) - b*r(n-2) = 0 

2) के रूप में लिखा जा सकता है आपके आवर्ती संबंध एक विशेषता समीकरण के रूप में लिखा जाता है के बाद, अगला जड़ों को खोजने (एक्स [1] और एक्स [2]) विशेषता समीकरण के।

3) अपनी जड़ों के साथ, अपने समाधान अब दो रूपों में से एक हो जाएगा:

if x[1]!=x[2] 
    c[1]*x[1]^n + c[2]*x[2]^n 
else 
    c[1]*x[1]^n + n*c[2]*x[2]^n 

जब n> 2 के लिए

। 4) अपने पुनरावर्ती समाधान के नए रूप के साथ, आप प्रारंभिक स्थितियों (r (1) और आर (2)) ग खोजने के लिए [1] और ग [2]

यहाँ उदाहरण के साथ हो रहा है का उपयोग हम क्या मिलेगा:

1) आर (एन) = 1 * आर (एन -1) + 2 * आर (n-2) => x^2 - x - 2 = 0

2) X

x = (-1 +- sqrt(-1^2 - 4(1)(-2)))/2(1) 

    x[1] = ((-1 + 3)/2) = 1 
    x[2] = ((-1 - 3)/2) = -2 

3) चूंकि x [1]! = X [2], आपकी soluti पर रूप है:

c[1](x[1])^n + c[2](x[2])^n 

4) अब, अपने प्रारंभिक स्थितियों का उपयोग दो स्थिरांक ग खोजने के लिए [1] और ग [2]:

c[1](1)^1 + c[2](-2)^1 = 1 
c[1](1)^2 + c[2](-2)^2 = 1 

सच में, मुझे यकीन है कि नहीं कर रहा हूँ क्या आपके स्थिरांक इस स्थिति में हैं, मैं इस बिंदु पर रुक गया। मुझे लगता है कि आपको संख्याओं में प्लग करना होगा जबतक कि आप दोनों को [1] और सी [2] दोनों के लिए कोई मूल्य नहीं मिलेगा, जो दोनों उन दो अभिव्यक्तियों को पूरा करेंगे।या तो उस या एक मैट्रिक्स सी पर पंक्ति कमी प्रदर्शन जहां सी बराबर है:

[ 1 1 | 1 ] 
[ 1 2 | 1 ] 

जाकारी:

पुनरावृत्ति है कि सबसे अच्छा तरह से वर्णन करता है इसके अलावा आपरेशन की संख्या निम्नलिखित कार्यक्रम टुकड़ा में (जब एल == 1 और आर == n)

int example(A, int l, int r) { 
    if (l == r) 
    return 2; 
    return (A[l] + example(A, l+1, r); 
} 

यहाँ के साथ कहा जाता है के समय जटिलता के लिए अपने दिए गए कोड के लिए मूल्यों जब आर> एल:

int example(A, int l, int r) {  => T(r) = 0 
    if (l == r)    => T(r) = 1 
    return 2;    => T(r) = 1 
    return (A[l] + example(A, l+1, r); => T(r) = 1 + T(r-(l+1)) 
} 

Total:      T(r) = 3 + T(r-(l+1)) 

वरना, जब आर == एल तो टी (आर) = 2, क्योंकि अगर बयान और बदले दोनों 1 कदम की आवश्यकता होती है प्रति निष्पादन।