C में प्रोग्रामिंग, तथा पुनरावर्तन

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

1. भोला पुनरावर्ती फिबोनाची fib(n) = n यदि n < 2, अन्यथा fib(n−1) + fib(n−2) से परिभाषित है। fib(5) निकालते समय fib को कुल कितनी कॉल होती हैं, प्रारंभिक कॉल सहित?

   संख्यात्मक उत्तर — मान टाइप करें।

   उत्तर देखें

   उत्तर: 15

   पुनरावर्तन-वृक्ष बनाकर शीर्ष गिनने पर 15 मिलता है। संवृत रूप 2·F(n+1) − 1 है जहाँ F स्वयं फिबोनाची अनुक्रम है: F(6) = 8, अतः 2×8 − 1 = 15, और वही सूत्र fib(6) हेतु 25 व fib(4) हेतु 9 देता है। दो जाँचें अधिकांश त्रुटियाँ पकड़ती हैं: गणना सदा विषम होती है, क्योंकि प्रत्येक आंतरिक शीर्ष की ठीक दो संतानें हैं; और वह n से बहुत बड़ी है, और अभिप्राय यही है — भिन्न उप-समस्याएँ केवल 6 हैं, और उससे ऊपर सब पुनर्गणना है।

2. 4-बाइट int व 8-बाइट संकेतक वाली मशीन पर int a[10]; हेतु sizeof(a) तथा sizeof(&a[0]) क्रमशः हैं:

   1. 40 व 8
   2. 8 व 8
   3. 40 व 40
   4. 10 व 8
   उत्तर देखें

   उत्तर: A — 40 व 8

   sizeof(a) सम्पूर्ण सरणी-वस्तु का आकार पूछता है: 10 × 4 = 40 बाइट। &a[0], int का संकेतक है, अतः उसका आकार संकेतक-चौड़ाई, 8 है। यही सर्वाधिक तीव्र स्थान है जहाँ सरणी व संकेतक भिन्न होते हैं, और इसीलिए सरणी पाता फलन उसकी लंबाई नहीं निकाल सकता — फलन के भीतर प्राचल वस्तुतः संकेतक है और sizeof, 8 लौटाता है। विकल्प B वह है जो अभ्यर्थी "सरणी संकेतक है" मानकर देता है; विकल्प D बाइटों के बजाय अवयव गिनता है, जो sizeof कभी नहीं करता।

3. void swap(int a, int b) { int t = a; a = b; b = t; } अपने बुलाने वाले के चर क्यों नहीं बदल पाता?

   1. क्योंकि अस्थायी चर t क्षेत्र से बाहर हो जाता है
   2. क्योंकि C तर्कों की प्रतिलिपि बनाता है, अतः फलन प्रतिलिपियाँ बदलता है
   3. क्योंकि फलन void लौटाता है
   4. क्योंकि संकेतक प्रकार बिना int नहीं बदले जा सकते
   उत्तर देखें

   उत्तर: B — क्योंकि C तर्कों की प्रतिलिपि बनाता है, अतः फलन प्रतिलिपियाँ बदलता है

   C में ठीक एक प्राचल-पासन तंत्र है: तर्क प्राचल में प्रतिलिपित होता है। अतः फलन के भीतर a व b नई वस्तुएँ हैं, स्वैप उन पर सही होता है, और बुलाने वाले के चर कभी स्पर्श ही नहीं हुए। उपचार पते देना है — swap(int *a, int *b) भीतर *a/*b सहित — जो भिन्न तंत्र नहीं अपितु संकेतक-मानों पर लगा वही प्रतिलिपिकरण है। विकल्प A, t के विषय में वास्तविक तथ्य है और विफलता से अप्रासंगिक; t के static होने पर भी स्वैप समान रूप से विफल होता। विकल्प C लौटाए मान को प्राचलों से भ्रमित करता है, और void में कुछ भी फलन को संकेतक से लिखने से नहीं रोकता।

4. हनोई की मीनार को 10 चक्रिकाओं हेतु कितनी चालें चाहिए?

   संख्यात्मक उत्तर — मान टाइप करें।

   उत्तर देखें

   उत्तर: 1023

   पुनरावृत्ति T(n) = 2T(n−1) + 1 है, T(1) = 1 सहित — n−1 चक्रिकाएँ पार ले जाएँ, सबसे बड़ी हिलाएँ, n−1 वापस लाएँ — जो 2ⁿ − 1 पर हल होती है, अतः 2¹⁰ − 1 = 1023। सर्वाधिक सामान्य गलत उत्तर 1024 है, घात याद रखकर −1 छोड़ने से; −1 वास्तविक है और n = 1 पर सहज दिखता है, जहाँ सूत्र को 2 के बजाय 1 देना चाहिए। यह भी ध्यान दें कि चालों की संख्या चरघातांकी है जबकि पुनरावर्तन गहराई केवल 10, और अगला प्रश्न उसी भेद पर घूमता है।

5. भोला fib(20) निकालने में दस हज़ारों कॉल होते हैं। उस गणना के दौरान कॉल स्टैक की अधिकतम गहराई है:

   1. लगभग 2²⁰
   2. 20
   3. कॉलों की संख्या के बराबर
   4. लगभग 13529
   उत्तर देखें

   उत्तर: B — 20

   स्टैक गहराई पुनरावर्तन-वृक्ष की ऊँचाई है, उसका आकार नहीं। सबसे गहरी श्रृंखला fib(20) → fib(19) → … → fib(1) है, अतः गहराई लगभग 20 है, चाहे कॉलों की संख्या 2·F(21) − 1 = 21,891 हो। कारण यह है कि दोनों पुनरावर्ती शाखाएँ एक के बाद एक खोजी जाती हैं, साथ नहीं: बाएँ उपवृक्ष के लौटने पर उसके फ़्रेम दाएँ उपवृक्ष के आरंभ से पूर्व चले जाते हैं। इसीलिए भोला फिबोनाची समय की आपदा है, स्थान की नहीं, और प्रश्न दोनों लागतों को पृथक् करने हेतु मानक रूप से यही करता है। विकल्प A व D आकार को ऊँचाई से भ्रमित करते हैं।

6. C में सरणियों व संकेतकों के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक सही हो सकते हैं।)

   1. a[i] व *(a + i) परिभाषा से तुल्य हैं
   2. सरणी-नाम को अन्यत्र संकेत करने हेतु पुनर्निर्दिष्ट किया जा सकता है
   3. सरणी प्राचल पाता फलन उसकी लंबाई निर्धारित नहीं कर सकता
   4. i[a] वाक्य-रचना त्रुटि है
   उत्तर देखें

   उत्तर: A — a[i] व *(a + i) परिभाषा से तुल्य हैं; C — सरणी प्राचल पाता फलन उसकी लंबाई निर्धारित नहीं कर सकता

   A व C। अनुलेखन की परिभाषा संकेतक-अंकगणित है, अतः a[i] का अर्थ *(a + i) है (A) — और चूँकि योग क्रमविनिमेय है, i[a] का अर्थ *(i + a) है, जो वही बात है और पूर्णतः वैध, अतः D असत्य है और वह प्रिय चालबाज़ प्रश्न है। C सत्य है और क्षय-नियम से निकलता है: प्राचल संकेतक है, sizeof संकेतक-चौड़ाई देता है, और लंबाई पृथक् रूप से देनी पड़ती है — इसीलिए सरणी लेता प्रत्येक C पुस्तकालय फलन एक गणना भी लेता है। B असत्य है: सरणी-नाम परिवर्तनीय lvalue नहीं है, और यही "सरणी संकेतक नहीं है" का दूसरा आधा है।

7. भोले पुनरावर्ती फिबोनाची में स्मृतिकरण जोड़ने से उसकी समय-जटिलता बदलती है:

   1. चरघातांकी से रैखिक
   2. चरघातांकी से लघुगणकीय
   3. रैखिक से अचर
   4. वह जटिलता नहीं बदलता, केवल अचर
   उत्तर देखें

   उत्तर: A — चरघातांकी से रैखिक

   भोला संस्करण चरघातांकी है क्योंकि उप-समस्याएँ पुनः निकाली जाती हैं — fib(6) के भीतर fib(3) तीन बार, और ऊपर कहीं अधिक बुरा। स्मृतिकरण प्रत्येक परिणाम पहली बार उत्पन्न होने पर संचित करता है, अतः n भिन्न उप-समस्याओं में प्रत्येक ठीक एक बार हल होती है और प्रत्येक बाद की माँग एक खोज है: काम n में रैखिक हो जाता है। विकल्प B वह है जिस तक अभ्यर्थी विभाजन-और-जीत के साहचर्य से पहुँचता है, पर यहाँ कुछ भी समस्या आधी नहीं करता — n उप-समस्याएँ हैं और प्रत्येक अपने पूर्ववर्तियों के साथ O(1) है। साथ आने वाली स्थान-लागत ध्यान दें: सारणी हेतु O(n), जबकि भोला संस्करण केवल O(n) स्टैक प्रयोग करता था, अतः स्मृतिकरण यहाँ कुछ नहीं छोड़ता, जो असामान्य है और ध्यान देने योग्य।

8. fib(6) की भोली गणना के भीतर fib(3) कितनी बार मूल्यांकित होता है?

   1. एक बार
   2. दो बार
   3. तीन बार
   4. पाँच बार
   उत्तर देखें

   उत्तर: C — तीन बार

   तीन बार। fib(6), fib(5) व fib(4) बुलाता है; fib(5), fib(4) व fib(3) बुलाता है; प्रत्येक fib(4), fib(3) व fib(2) बुलाता है। अतः fib(3) तक एक बार सीधे fib(5) से और एक-एक बार दोनों fib(4) कॉलों से पहुँचा जाता है — कुल तीन। इसे हाथ से अनुसरण करना ही वह कौशल है जो प्रश्न जाँच रहा है, और सामान्य प्रतिरूप देखने योग्य है: fib(n) के भीतर fib(k) कितनी बार मूल्यांकित होता है यह स्वयं एक फिबोनाची संख्या है, इसीलिए अतिरेक इतनी तेज़ी से बढ़ता है। उसी गणना से fib(2) पाँच बार मूल्यांकित होता है।