एक बार एक तख़्त, दो तख़्त - एक सीढ़ी होगी ...

मैं लण्ड के बारे में थोड़ी बात करना चाहूँगा। प्रोग्रामर साक्षात्कार के साथ इस तरह के एक आम काम है:

आप सीढ़ियाँ चढ़ते हैं। प्रत्येक चरण पर, आप या तो 1 चरण पर चढ़ सकते हैं या 2. कुल में, सीढ़ी के पास n चरण हैं। आप सीढ़ियों के अंत तक कितने अलग-अलग तरीकों से पहुंच सकते हैं?

कार्य बहुत कठिन नहीं है, लेकिन समाधान की न्यूनतम संभावित जटिलता के बारे में कुछ दिलचस्प बिंदु हैं और "उन चीजों को प्रदर्शित करना जो जानना दिलचस्प है।"

जाहिर है, एक तरह से या किसी अन्य, निर्णय इस अवलोकन से शुरू होता है कि प्रत्येक चरण में हमारे पास दो कार्यों का एक विकल्प है: एक कदम उठाएं या दो कदम उठाएं। पहले मामले में, सीढ़ी एक कदम से घट जाती है, दूसरे में - दो से। सीढ़ी के चारों ओर जाने के लिए संभावित तरीकों की कुल संख्या, ऐसा करने के तरीकों की संख्या का योग है यदि हम एक कदम से शुरू करते हैं, और दो से शुरू होने पर रास्ते की संख्या। नतीजतन, समाधान एक पुनरावृत्ति सूत्र को कम कर देता है:

एफ (एन) = एफ (एन -1) + एफ (एन -2)

इस एल्गोरिथ्म का एक पुनरावर्ती या पुनरावृत्ति कार्यान्वयन "हेड-ऑन" अनुपात से थोड़ा अधिक लंबा लगता है (हम कोष्ठक के बाहर अतिप्रवाह समस्या को छोड़ देते हैं):

int f(int n) { if (n == 0 || n == 1) return 1; return f(n-1) + f(n-2); } 

अपने आप में, यह समाधान सही है, लेकिन इसकी प्रभावशीलता कम है: एल्गोरिथ्म घातीय है । डायनेमिक प्रोग्रामिंग की मानक तकनीक का उपयोग करके जटिलता को कम किया जा सकता है - संस्मरण । सहज व्याख्या: सीढ़ियों पर प्रत्येक ठोस कदम से, अंत तक पहुंचने के तरीकों की संख्या इस बात पर निर्भर नहीं करती है कि हमें यह कदम कैसे मिला, इसलिए यह अगले गणना चरणों में उत्तर को याद रखने और उपयोग करने के लिए समझ में आता है। मैं कोड नहीं दूंगा - मुख्य बात यह है कि, पुनरावृत्ति के साथ, एक रैखिक समाधान प्राप्त किया जाता है। हालाँकि, यह सब नहीं है।

एक चौकस पाठक ध्यान देगा कि उपरोक्त अनुपात बस एक के द्वारा n के सुधार के साथ फाइबोनैचि संख्याओं का सूत्र है (सुधार दिखाई देता है क्योंकि प्रारंभिक शर्तें अलग हैं - Fib (0) = 0, Fib (1) = 1, Fib (2) = 1) , और हमारे मामले में सीढ़ियों एफ (0) = 1, एफ (1) = 1, एफ (2) = 2)। यह ज्ञात है कि फाइबोनैचि संख्याओं के लिए निम्नलिखित संबंध हैं:



इस प्रकार, इस घातांक के बाद, परिणामी मैट्रिक्स में पहली पंक्ति के पहले कॉलम में हमारे लिए "n + 1" फाइबोनैचि संख्या शामिल होगी (मैट्रिक्स तत्व पारंपरिक रूप से एक से अनुक्रमित होते हैं)।

अपने आप से, यह तथ्य पहले से ही दिलचस्प है, लेकिन यह तेजी से घातांक के एल्गोरिथ्म के साथ संयोजन में विशेष रूप से दिलचस्प है। जैसा कि हमारी समस्या पर लागू होता है, इसका मतलब है कि हम O (ln N) गुणन के लिए उत्तर प्राप्त कर सकते हैं। पायथन में इस समाधान के लिए कोड (फिर से, अब के लिए अतिप्रवाह समस्या के बारे में भूल जाने के लिए - अजगर स्वचालित रूप से बड़े पूर्णांक का उपयोग करने के लिए स्विच करता है जब आवश्यक हो) इस तरह दिखता है:

 #!/usr/bin/env python # You are climbing a stair case. Each time you can either make 1 step or 2 # steps. The staircase has n steps. In how many distinct ways can you climb the # staircase? def mul(a, b): return ((a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]), (a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1])) def pow(a, N): """Fast matrix exponentiation""" assert N >= 1 if N == 1: return a x = pow(a, N / 2) ret = mul(x, x) if N % 2: ret = mul(ret, a) return ret def num_stair_ways(N): x = pow(((1, 1), (1, 0)), N) return x[0][0] for i in range(1, 1001): print i, num_stair_ways(i) 

दरअसल, बस इतना ही। मुझे आशा है, मेरी तरह, पाठक को यह महसूस करने में प्रसन्नता है कि 200-सीढी की सीढि़याँ विभिन्न परिस्थितियों में 45397369416530795319729696969741061923382626 समस्या की स्थितियों के अनुसार चल सकती हैं। और यह कि यह लघुगणक जटिलता के साथ गणना की जा सकती है।

अद्यतन: टिप्पणियों को पढ़ने के परिणामस्वरूप, मैं कुछ टिप्पणियां करने की जल्दबाजी करता हूं:

• हाल ही में, एक बहुत ही समान विषय पर एक लेख पहले से ही था। लेख में कई समझदार टिप्पणियां हैं। प्रकाशित होने पर इसी तरह के लेखों के लिए स्वचालित खोज करना अच्छा होगा।
• O (ln N) संचालन के तेजी से बढ़ते अनुक्रम के Nth शब्द की गणना के लिए एल्गोरिदम के बारे में सभी चर्चाओं को संख्याओं की रैखिक रूप से बढ़ती बिट गहराई को ध्यान में रखना चाहिए। यही है, गुणन की संख्या O (ln N) के रूप में बढ़ सकती है, लेकिन प्रत्येक व्यक्ति गुणन की जटिलता अभी भी N से रैखिक रूप से बढ़ेगी। इसलिए, कुल जटिलता केवल लघुगणक रह सकती है, यदि किसी भी मॉड्यूल के लिए अंतिम मूल्य खोजना पर्याप्त है।