इष्टतम एक सतत भिन्न

Question

एक का परिणाम गणना करने के लिए एल्गोरिथ्म क्रमागत भिन्न इस तरह के डिवीजनों की एक श्रृंखला है:

depth 1 1+1/s 

depth 2 1+1/(1+1/s) 

depth 3 1+1/(1+1/(1+1/s)) 
    .  .  .   
    .  .  .  
    .  .  . 

गहराई एक पूर्णांक है, लेकिन s एक चल बिन्दु संख्या है।

बड़ी गहराई वाले ऐसे अंश के परिणाम की गणना करने के लिए इष्टतम एल्गोरिदम (प्रदर्शन-वार) क्या होगा?

Answer 1

सुझाव: इन बुनियादी बीजगणित का उपयोग कर सूत्रों के प्रत्येक उतारना। आप एक पैटर्न उभरेंगे देखेंगे।

मैं तुम्हें पहला कदम दिखाता हूँ तो यह स्पष्ट हो जाता है:

f(2,s) = 1+1/s = (s+1)/s 
f(3,s) = 1+1/f(2,s) = 1+(s/(s+1)) = (1*(s+1) + s)/(s+1) = (2*s + 1)/(s + 1) 
     /* You multiply the first "1" by denominator */ 
f(4,s) = 1+1/f(3,s) = 1+(s+1)/(2s+1) = (1*(2*s+1) + (s+1))/(2*s+1) = (3*s + 2)/(2*s + 1) 
f(5,s) = 1+1/f(4,s) = 1+(2s+1)/(3s+2) = (1*(3*s+2) + (2s+1))/(3*s+2) = (5*s + 3)/(3*s + 2) 

...

Hint2: आप स्पष्ट पैटर्न रूप में उभर रहा है, ऊपर सबसे इष्टतम नहीं दिख रहा है, तो एल्गोरिदम में फिबोनाची संख्याओं की गणना शामिल होगी (इसलिए आपको इष्टतम फिबोनाकी # जनरेटर के लिए Google की आवश्यकता होगी)।

Answer 2

पूंछ रिकर्सन (रिकर्सन (रिकर्सन (...)) की तरह बदबू आ रही है)।

(दूसरे शब्दों में - यह पाश)

Answer 3

मैं 1/s की गणना है, जो हम a कॉल करेंगे के साथ शुरू होगा।

फिर फॉर-लूप का उपयोग करें, जैसे कि यदि आप रिकर्सन का उपयोग करते हैं, तो सी में, आप एक स्टैक ओवरफ़्लो अनुभव कर सकते हैं।

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

चूंकि आप हमेशा 1/s को विभाजित करने जा रहे हैं और विभाजन महंगा है, बस इसे एक बार करने से प्रदर्शन में मदद मिलेगी।

मुझे उम्मीद है कि यदि आप इसे काम करते हैं तो आप वास्तव में एक पैटर्न ढूंढ सकते हैं जो आपको और अनुकूलित करने में मदद करेगा।

आपको इस तरह का एक लेख मिल सकता है: http://www.b-list.org/weblog/2006/nov/05/programming-tips-learn-optimization-strategies/, सहायक होने के लिए।

मैं प्रदर्शन के अनुसार मान रहा हूं कि आप इसका मतलब है कि आप इसे तेज करना चाहते हैं, स्मृति की परवाह किए बिना, बीटीडब्ल्यू।

आप पाते हैं कि यदि आप प्रत्येक चरण में गणना की गई मानों को कैश करते हैं, तो आप एक महंगी गणना को फिर से करने के बजाय उनका पुन: उपयोग कर सकते हैं।

मैं व्यक्तिगत रूप से हाथ से 4-5 कदम उठाता हूं, प्रत्येक चरण के समीकरणों और परिणामों को लिखता हूं, और देखता हूं कि कोई पैटर्न उभरता है या नहीं।

अद्यतन:

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

http://answers.yahoo.com/question/index?qid=20100511111152AAVHx6s

Answer 4

मैं DVK's excellent answer पर थोड़ा विस्तार करना चाहता हूं। d गहराई के लिए मांग मूल्य को इंगित करने के लिए मैं उनके नोटेशन f(d,s) के साथ रहूंगा।

यदि आप बड़े d के लिए f(d,s) मान की गणना करते हैं, तो आप देखेंगे कि मान d बढ़ते हैं।

φ = एफ (∞, एस) दें। यही है, φ d की सीमा अनंत है, और निरंतर विस्तार पूर्ण रूप से विस्तारित है। ध्यान दें कि φ में स्वयं की एक प्रति है, ताकि हम φ = 1 + 1/φ लिख सकें। φ द्वारा दोनों पक्षों को गुणा करने और उलटफेर, हम द्विघात समीकरण प्राप्त

φ - φ - 1 = 0

जो प्राप्त करने के लिए हल किया जा सकता

φ = (1 + √ 5)/2।

यह famous golden ratio है।

आप पाएंगे कि f(d,s) φ के बहुत करीब है क्योंकि डी बड़ा हो जाता है।

लेकिन प्रतीक्षा करें। अभी और है!

जैसा कि डीवीके ने बताया, f(d,s) के सूत्र में फिबोनाची अनुक्रम से शर्तें शामिल हैं। विशेष रूप से, इसमें फाइबोनैकी अनुक्रम की लगातार शर्तों के अनुपात शामिल होते हैं। वहाँ एक closed form expression for the nth term of the sequence अर्थात्

(φ ⁿ - (1 φ) ⁿ) है,/√ 5.

1- φ के बाद से एक से भी कम है, (1 φ) ⁿn के रूप में छोटा हो जाता है, इसलिए nth Fibonacci शब्द के लिए एक अच्छा अनुमान φ ⁿ/√ 5. और डीवीके के सूत्र पर वापस लौटने के बाद, फाइबोनैकी अनुक्रम में लगातार शर्तों का अनुपातहो जाएगा^{एन + 1}/φ ^एन = φ।

तो यह इस तथ्य को प्राप्त करने का दूसरा तरीका है कि इस प्रश्न में निरंतर अंश φ पर मूल्यांकन करता है।