समस्या से एल्गोरिदम तक

सारांश

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

अधिगम उद्देश्य

किसी सरल समस्या को उसके इनपुट, उसके आउटपुट और उन शर्तों को बताकर विनिर्दिष्ट करना जिन्हें उन्हें पूरा करना है।
किसी एल्गोरिदम का क्रमांकित चरणों में, बिना अस्पष्टता के, स्पष्ट निर्णयों और पुनरावृत्तियों के साथ वर्णन करना।
ट्रेस तालिका के साथ किसी एल्गोरिदम को हाथ से चलाना और किसी दिए गए इनपुट के लिए उसका परिणाम ज्ञात करना।
किसी दी गई प्रक्रिया में अनुक्रम, निर्णय और पुनरावृत्ति को पहचानना, और यह सिद्ध करना कि कोई पुनरावृत्ति समाप्त होती है।

संगणनात्मक समस्या क्या है

संगणनात्मक समस्या दो प्रकार के डेटा के बीच एक संबंध है: वे जो प्राप्त होते हैं, जिन्हें इनपुट कहते हैं, और वे जो दिए जाने हैं, जिन्हें आउटपुट कहते हैं। उसे हल करने का अर्थ किसी एक स्थिति के लिए उत्तर पाना नहीं, बल्कि ऐसी विधि का होना है जो हर स्वीकार्य इनपुट के लिए ऐसा आउटपुट दे जो संबंध को पूरा करे। “17 को 5 से भाग देने पर कितना आता है?” एक प्रश्न है; “दो पूर्णांक दिए होने पर उनका भागफल और शेषफल ज्ञात करो” एक समस्या है, क्योंकि वह पूर्णांकों के सभी युग्मों के बारे में एक साथ बात करती है।

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

उदाहरणतीन संख्याओं का अधिकतम

रोज़मर्रा का कथन: “तीन संख्याओं में सबसे बड़ी ढूँढ़ो”। विनिर्देश:

इनपुट: तीन संख्याएँ $x$ , $y$ , $z$ (पूर्णांक या दशमलव, बिना किसी अन्य शर्त के)।
आउटपुट: एक संख्या $m$ ।
संबंध: $m$ तीनों डेटा में से एक है, और उनमें से कोई भी $m$ से बड़ा नहीं है; अर्थात $m \geq x$ , $m \geq y$ और $m \geq z$ ।

संबंध “तीनों में सबसे बड़ी” नहीं कहता, जो ठीक वही है जिसे सटीक करना था, बल्कि दो जाँचने योग्य शर्तें देता है। पहली शर्त माँगती है कि $m$ डेटा में से एक हो (इसके बिना संख्या 1000 लगभग किसी भी इनपुट के लिए दूसरी शर्त पूरी कर देती); दूसरी माँगती है कि कोई भी उससे आगे न निकले। और विनिर्देश साथ-साथ एक संदेह भी दूर कर देता है जिसे कथन ने खुला छोड़ दिया था: यदि दो डेटा अधिकतम पर बराबर हों, जैसे $(4, 9, 9)$ में, तो आउटपुट $9$ है, और इसमें कोई त्रुटि नहीं है।

एक ही कथन अलग-अलग विनिर्देशों की अनुमति देता है, और उनमें से चुनना एक निर्णय है, लापरवाही नहीं। सबसे शिक्षाप्रद स्थिति पूर्णांक विभाजन की है। पूर्णांकों $a \geq 0$ और $b > 0$ के लिए सब सहमत हैं: भागफल $q$ और शेषफल $r$ वे एकमात्र पूर्णांक हैं जो यह पूरा करते हैं

a = b \cdot q + r, \quad 0 \leq r < b

इस प्रकार, $a = 17$ और $b = 5$ के लिए $q = 3$ और $r = 2$ हैं, क्योंकि $17 = 5 \cdot 3 + 2$ । लेकिन कथन “दो पूर्णांकों का भाग करो” यह नहीं बताता कि यदि $a$ ऋणात्मक हो तो क्या करें, और यह प्रश्न व्यर्थ नहीं है: $a = -7$ और $b = 2$ के लिए दो उचित उत्तर हैं।

उदाहरणऋणात्मक भाज्य वाले विभाजन के दो विनिर्देश

पहला विनिर्देश: शेषफल कभी ऋणात्मक नहीं होता, $0 \leq r < b$ । तब $-7 = 2 \cdot (-4) + 1$ , और आउटपुट $q = -4$ , $r = 1$ है। गणित में यही पढ़ा जाता है, पाठ्यक्रम “बीजगणित और ज्यामिति I” के पाठ “विभाज्यता और शेषफल सहित विभाजन” में।

दूसरा विनिर्देश: भागफल दशमलव वाले विभाजन का परिणाम है, जिसका दशमलव भाग हटा दिया गया हो, अर्थात शून्य की ओर पूर्णांकित; शेषफल वह है जो कम पड़ता है, और उसका चिह्न भाज्य का होता है। तब $-7 / 2 = -3.5$ कटकर $-3$ हो जाता है, और $-7 = 2 \cdot (-3) + (-1)$ : आउटपुट $q = -3$ , $r = -1$ है।

दोनों $a = b \cdot q + r$ को पूरा करते हैं; वे शेषफल पर लगाई गई शर्त में भिन्न हैं। कोई भी त्रुटि नहीं है, लेकिन जो प्रोग्राम एक का उपयोग करते हुए यह मानता है कि वह दूसरे का उपयोग कर रहा है, वह ऋणात्मक संख्याओं के साथ गलत परिणाम देगा। एक बात पहले से बता दें: C++ दूसरा अपनाती है, जैसा कि पाठ अंकगणितीय संक्रियाएँ में दिखेगा; जो पहले की अपेक्षा करेगा, उसे आश्चर्य होगा।

एक तीसरा विकल्प भी है, जो व्यवहार में सबसे आम है: पूर्व-शर्त से उस स्थिति को बाहर कर देना। यदि विनिर्देश $a \geq 0$ माँगता है, तो ऋणात्मक संख्याओं की समस्या गायब हो जाती है, इसलिए नहीं कि वह हल हो गई, बल्कि इसलिए कि हल का उपयोग करने वाले ने उसे न उठाने का वचन दिया है। जो नहीं किया जा सकता, वह है प्रश्न को अनिर्णीत छोड़ देना। और इसी कारण विनिर्देश $b > 0$ माँगता है: $b = 0$ होने पर ऐसे $q$ और $r$ मौजूद नहीं हैं जो संबंध को पूरा करें, और अनुबंध को यह कहना चाहिए।

एक आम त्रुटि उदाहरण से विनिर्दिष्ट करना है: “17 और 5 का आउटपुट 3 और 2 है”। उदाहरण स्पष्ट करता है, पर विनिर्दिष्ट नहीं करता, क्योंकि वह नहीं बताता कि बाकी इनपुट के साथ क्या होता है; अनंत भिन्न संबंध एक स्थिति में मेल खाते हैं। विनिर्देश एक व्यापक शर्त के रूप में लिखा जाता है, और उदाहरण बाद में उसे जाँचने के काम आते हैं।

एल्गोरिदम

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

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

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

खाना पकाने की विधि एल्गोरिदम जैसी लगती है, और इसीलिए यह सामान्य तुलना है; लेकिन लगभग कोई भी विधि एल्गोरिदम नहीं होती। “एक चुटकी नमक डालें” सुनिश्चित नहीं है, क्योंकि चुटकी कोई मात्रा नहीं है; “सुनहरा होने तक सेंकें” एक ऐसे निर्णय पर निर्भर है जिसे दो लोग अलग-अलग ढंग से करेंगे; “कई बार फेंटें” नहीं बताता कि कितनी बार। रसोइया इन रिक्तियों को अपने अनुभव से भरता है; कंप्यूटर के पास कोई अनुभव नहीं होता। इससे वह अपेक्षा निकलती है जो पूरे पाठ्यक्रम को नियंत्रित करती है: एल्गोरिदम का पालन वह भी कर सके जो समस्या को नहीं समझता, बिना कुछ अनुमान लगाए। यदि किसी चरण को चलाने के लिए यह जानना पड़े कि वह किस काम आता है, तो वह चरण ठीक से नहीं लिखा गया है।

इस पाठ्यक्रम के एल्गोरिदम पहले क्रमांकित चरणों में, हिंदी में, कुछ परिपाटियों के साथ लिखे जाते हैं। जो डेटा एल्गोरिदम के दौरान बदलते हैं, उन्हें अक्षरों या शब्दों से नाम दिया जाता है, जैसे $q$ या $r$ , और उन्हें चर कहते हैं। “ $r$ का मान $r - b$ रखें” लिखा जाता है, यह कहने के लिए कि $r - b$ की गणना $r$ के वर्तमान मान से की जाती है और परिणाम $r$ का नया मान बन जाता है; पिछला मान खो जाता है। संक्षिप्त लेखन में, जो नोट्स लेते समय प्रयोग होता है, वही निर्देश बाईं ओर के तीर से लिखा जाता है, जो कीबोर्ड पर r <- r - b है। निर्देश अपनी संख्या के क्रम में चलाए जाते हैं, जब तक कि उनमें से कोई कुछ और न कहे।

उदाहरणक्रमिक घटाव द्वारा विभाजन

समस्या वही है जो पिछले अनुभाग में विनिर्दिष्ट की गई: इनपुट, दो पूर्णांक $a \geq 0$ और $b > 0$ ; आउटपुट, दो पूर्णांक $q$ और $r$ , जिनके लिए $a = b \cdot q + r$ और $0 \leq r < b$ । विचार बाँटने का है: जब तक संभव हो, $a$ में से $b$ के समूह निकाले जाते हैं, निकाले गए समूह गिने जाते हैं, और जो बचता है वह शेषफल है।

$q$ का मान $0$ रखें, और $r$ का मान $a$ रखें।
जब तक $r \geq b$ सत्य रहे, चरण 3 और 4 दोहराएँ; जब वह सत्य न रहे, तो चरण 5 पर जाएँ।
$r$ का मान $r - b$ रखें।
$q$ का मान $q + 1$ रखें; चरण 2 पर लौटें।
$q$ और $r$ आउटपुट करें, और समाप्त करें।

चरण 2 एक प्रश्न है जो हर बार पूछा जाता है: पहले चक्कर से पहले और हर चक्कर के बाद। चरण 3 और 4 पुनरावृत्ति की बॉडी बनाते हैं, यानी वह जो दोहराया जाता है। चलाने वाले के विवेक पर कुछ भी नहीं छोड़ा गया: हर क्षण केवल एक ही अगला निर्देश होता है।

यह एल्गोरिदम धीमा है (दस लाख को तीन से भाग देने में यह तीन लाख से अधिक चक्कर लगाता है), और विद्यालय की विभाजन-विधि कहीं तेज़ है; लेकिन यह सही है, और इसकी सरलता इसे एल्गोरिदमों पर विवेचन करना सीखने के लिए आदर्श बनाती है। पाठ्यक्रम सही और कुशल एल्गोरिदम के अंतर पर पाठ एल्गोरिदम की लागत में लौटेगा।

अंत में, एल्गोरिदम को उसके लेखन से अलग करना उचित है। घटाव द्वारा विभाजन का एल्गोरिदम वही रहता है चाहे उसे हिंदी में लिखा जाए, किसी आरेख में, C++ में या किसी अन्य प्रोग्रामिंग भाषा में: उसे संक्रियाओं का अनुक्रम परिभाषित करता है, शब्द नहीं। प्रोग्राम किसी एल्गोरिदम का ऐसी भाषा में लेखन है जिसे मशीन चला सके, और पाठ प्रोग्राम, कंपाइलर और C++ समझाएगा कि यह चलना कैसे होता है। यदि ऐसा है, तो कोई प्रोग्राम दो बहुत भिन्न तरीकों से गलत हो सकता है: क्योंकि एल्गोरिदम गलत है, और तब कोई भाषा उसे नहीं बचाती, या क्योंकि एल्गोरिदम सही है पर गलत लिखा गया। दोनों स्थितियों में भेद करना डिबग करने का आधा काम है, और इसीलिए पाठ्यक्रम हमेशा पहले एल्गोरिदम लिखता है।

एल्गोरिदम को हाथ से चलाना

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

उपकरण है ट्रेस तालिका: चलाए जा रहे चरण की संख्या के लिए एक स्तंभ, हर चर के लिए एक स्तंभ और, यदि उपयोगी हो, जाँची जाने वाली शर्तों के लिए एक स्तंभ; और चलाए गए हर चरण के लिए एक पंक्ति। हर पंक्ति में उस चर का नया मान लिखा जाता है जो उस चरण में बदला, और जो नहीं बदला उसे खाली छोड़ा जाता है, ताकि किसी चर का वर्तमान मान उसके स्तंभ में अंतिम लिखा मान हो। शर्तें उनके परिणाम के साथ लिखी जाती हैं।

उदाहरण17 को 5 से भाग देने का ट्रेस

हम क्रमिक घटाव द्वारा विभाजन को $a = 17$ और $b = 5$ के साथ चलाते हैं। चित्र का तीर उस चरण को दिखाता है जो अभी-अभी चला है; बिंदुदार रेखा याद दिलाती है कि चरण 4 चरण 2 पर लौटता है।

प्रमाण

$(q, r) = (0, 17)$
चरण 1: प्रारंभिक मान दिए जाते हैं। इनपुट पूर्व-शर्त पूरी करता है, क्योंकि $17 \geq 0$ और $5 > 0$ ।
$(q, r) = (1, 12)$
पहला चक्कर। चरण 2 में जाँचा जाता है कि $17 \geq 5$ , इसलिए बॉडी चलती है: चरण 3 पाँच का एक समूह निकालता है और चरण 4 उसे गिनता है।
$(q, r) = (2, 7)$
दूसरा चक्कर: $12 \geq 5$ , और बॉडी फिर से चलती है।
$(q, r) = (3, 2)$
तीसरा चक्कर: $7 \geq 5$ , और बॉडी फिर से चलती है।
$17 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5$
चरण 2 में शर्त विफल होती है, क्योंकि $2 < 5$ : एल्गोरिदम चरण 5 पर जाता है और $q = 3$ और $r = 2$ देता है। आउटपुट पश्च-शर्त पूरी करता है।

पूरी तालिका में बारह पंक्तियाँ हैं: चरण 1, तीन-तीन पंक्तियों के तीन चक्कर (चरण 2, 3 और 4), विफल होने वाली जाँच और आउटपुट।

तालिका पर दो टिप्पणियाँ। पहली: चक्करों की संख्या भागफल, $3$ , के बराबर है, और चरण 2 बॉडी से एक बार अधिक, $4$ बार, चला; इस रूप की पुनरावृत्ति में ऐसा हमेशा होता है, क्योंकि अंतिम जाँच ही विफल होने वाली होती है। दूसरी: ट्रेस कुछ ऐसा दिखाता है जो एल्गोरिदम का लिखित रूप पहली नज़र में नहीं कहता; यदि $a < b$ , उदाहरण के लिए $a = 3$ और $b = 5$ , तो शर्त पहली बार में ही विफल हो जाती है, बॉडी एक भी बार नहीं चलती, और आउटपुट $q = 0$ , $r = 3$ है, जो सही है, क्योंकि $3 = 5 \cdot 0 + 3$ । उस स्थिति को भूल जाना जिसमें पुनरावृत्ति नहीं चलती, एल्गोरिदम बनाने में सबसे आम त्रुटियों में से एक है, और छोटे इनपुट के साथ ट्रेस इसे पकड़ लेता है।

एक स्थिति का ट्रेस यह सिद्ध नहीं करता कि एल्गोरिदम सही है: वह एक स्थिति की जाँच करता है। लेकिन अच्छी तरह चुना गया ट्रेस (एक सामान्य स्थिति, एक सीमांत स्थिति, वह स्थिति जिसमें पुनरावृत्ति नहीं चलती) अधिकांश त्रुटियाँ पकड़ लेता है, और जो विफल होता है वह बताता है कि वे कहाँ हैं। पाठ सही लूप की रचना सिखाएगा कि स्थितियों से उपपत्ति तक कैसे पहुँचें।

अनुक्रम, निर्णय और पुनरावृत्ति

पास से देखें तो एल्गोरिदम बहुत थोड़े पुर्ज़ों से बनते हैं। कुछ प्रारंभिक निर्देश होते हैं (किसी चर को मान देना, कोई परिणाम देना) और उन्हें जोड़ने के तीन तरीके।

अनुक्रम: एक निर्देश के बाद दूसरा, क्रम से। विभाजन के चरण 3 और 4 एक अनुक्रम हैं: पहले घटाया जाता है, फिर गिना जाता है।
निर्णय: कोई शर्त पूरी होती है या नहीं, इसके अनुसार एक भाग या दूसरा चलाया जाता है (या एक भाग या कुछ नहीं)। “यदि $y > m$ , तो $m$ का मान $y$ रखें” एक निर्णय है।
पुनरावृत्ति: जब तक कोई शर्त पूरी होती रहे, एक भाग बार-बार चलाया जाता है। विभाजन का चरण 2, अपनी बॉडी के साथ, एक पुनरावृत्ति है।

हर रूप का एक ही प्रवेश और एक ही निकास होता है, और उसका भीतरी भाग स्वयं तीनों में से कोई भी हो सकता है: पुनरावृत्ति की बॉडी में निर्णय हो सकते हैं, निर्णय की किसी शाखा में पुनरावृत्ति हो सकती है, और इसी प्रकार आगे। यदि ऐसा है, तो तीनों रूपों से किसी भी जटिलता के एल्गोरिदम बनाए जा सकते हैं, जैसे आपस में फिट होने वाले थोड़े-से पुर्ज़ों से कोई भी इमारत बनाई जा सकती है। कि ये हर एल्गोरिदम को व्यक्त करने के लिए पर्याप्त हैं, यह प्रोग्रामिंग के सिद्धांत का एक जाना-माना परिणाम है (इसे कोराडो बोहम और जुसेप्पे याकोपिनी ने 1966 में सिद्ध किया); यहाँ इसे सिद्ध नहीं किया जाता, लेकिन पूरा पाठ्यक्रम इसकी पुष्टि करता है: इसमें लिखे जाने वाले प्रोग्राम, चाहे कितने भी लंबे हों, इन तीन रूपों के अलावा कुछ उपयोग नहीं करेंगे, जो C++ में निर्णय के लिए if और पुनरावृत्ति के लिए while या for के रूप में लिखे जाते हैं, पाठ निर्णय और लूप में।

किसी एल्गोरिदम का रूप देखने के लिए एक उपयोगी संकेतन फ़्लोचार्ट है: हर निर्देश एक आयत है, हर शर्त दो निकासों वाला एक समचतुर्भुज (पूरी हुई, जिसे चित्र $1$ से अंकित करता है, और पूरी नहीं हुई, $0$ ), और तीर बताते हैं कि अगला चरण कौन-सा है। यह एक संकेतन है, लक्ष्य नहीं: यह किसी छोटे एल्गोरिदम को एक नज़र में देखने के काम आता है, पर बड़े पैमाने पर काम नहीं करता, और कोई भी बड़ा प्रोग्राम उसका चित्र बनाकर नहीं लिखता।

उदाहरणतीन रूप और उनकी संरचना

चित्र सामान्य निर्देशों $A$ और $B$ तथा एक शर्त $c$ के साथ तीनों रूप बनाता है, और फिर उन्हें क्रमिक घटाव द्वारा विभाजन के आरेख में जोड़ता है।

प्रमाण

$A ; B$
अनुक्रम: $A$ चलता है और फिर $B$ ; एक ही प्रवेश और एक ही निकास है।
$c = 1 \Rightarrow A, \quad c = 0 \Rightarrow B$
निर्णय: यदि $c$ पूरी होती है, तो $A$ चलता है; अन्यथा, $B$ । दोनों शाखाएँ एक ही निकास में मिलती हैं।
$c, A, c, A, \ldots, c$
पुनरावृत्ति: $c$ जाँची जाती है; यदि वह पूरी होती है, तो $A$ चलता है और $c$ फिर से जाँची जाती है; अन्यथा, बाहर निकलते हैं। शर्त बॉडी से एक बार अधिक जाँची जाती है।
$a = b \cdot q + r, \quad 0 \leq r < b$
संरचना: क्रमिक घटाव द्वारा विभाजन एक अनुक्रम है (प्रारंभिक मान, पुनरावृत्ति, आउटपुट) जिसकी पुनरावृत्ति की बॉडी एक और अनुक्रम है (घटाना, गिनना)।

रोज़मर्रा की भाषा में लिखी किसी प्रक्रिया में तीनों रूपों को पहचानना उसे प्रोग्राम में बदलने का पहला कदम है। निर्णय का संकेत है “यदि”, “की स्थिति में” या “के अनुसार”; पुनरावृत्ति का, “जब तक”, “तब तक जब तक कि”, “हर एक के लिए” या “उतनी बार जितनी बार”। जिस प्रक्रिया में इनमें से कोई शब्द नहीं, वह एक अनुक्रम है, और यदि उसे बदलते आकार के इनपुट (संख्याओं की सूची, कोई टेक्स्ट) संभालने हों, तो उसमें एक पुनरावृत्ति की कमी है।

क्या यह समाप्त होता है?

परिमितता एल्गोरिदम की परिभाषा का हिस्सा है, और पुनरावृत्ति ही एकमात्र स्थान है जहाँ वह खो सकती है: पाँच चरणों का अनुक्रम पाँच चरण चलाता है, और निर्णय अपनी शाखाओं में से एक चलाता है; लेकिन पुनरावृत्ति अपनी बॉडी उतनी बार चलाती है जितनी बार शर्त पूरी होती है, और कुछ भी पहले से गारंटी नहीं देता कि वह पूरी होना बंद हो जाएगी।

यह सिद्ध करने के लिए कि कोई पुनरावृत्ति समाप्त होती है, चरों से परिकलित ऐसी राशि खोजी जाती है जो दो शर्तें पूरी करे: जब तक पुनरावृत्ति चलती रहे, वह एक प्राकृत संख्या (पूर्णांक और अऋणात्मक) हो, और हर चक्कर में निरंतर घटे। यदि ऐसा है, तो पुनरावृत्ति समाप्त होती है: प्राकृत संख्याओं का निरंतर घटता अनुक्रम अनंत नहीं हो सकता, क्योंकि हर चक्कर उसे कम से कम एक घटाता है और किसी प्राकृत संख्या $n$ से शून्य तक $n$ से अधिक सीढ़ियाँ नहीं हैं। इस राशि को वैरिएंट या सीमा फलन कहते हैं, और पाठ सही लूप की रचना इसका व्यवस्थित उपयोग करेगा।

उदाहरणघटाव द्वारा विभाजन का वैरिएंट

क्रमिक घटाव द्वारा विभाजन में वैरिएंट $r$ है। जब तक पुनरावृत्ति चलती रहती है, $r \geq b > 0$ , इसलिए $r$ एक प्राकृत संख्या है। हर चक्कर में $r$ का मान $r - b$ हो जाता है, और क्योंकि $b > 0$ (पूर्व-शर्त), नया मान निश्चित रूप से छोटा है। अतः पुनरावृत्ति समाप्त होती है, और अधिक से अधिक $a$ चक्करों के बाद (वास्तव में ठीक $q$ चक्करों के बाद, यानी भागफल जितने)।

देखिए कि पूर्व-शर्त $b > 0$ का उपयोग कहाँ हुआ। यदि एल्गोरिदम को $b = 0$ के साथ चलाया जाए, तो चरण 3 $r$ को वैसा ही छोड़ देता है, शर्त $r \geq 0$ हमेशा पूरी होती है और पुनरावृत्ति कभी समाप्त नहीं होती: एल्गोरिदम गलत नहीं है, बल्कि उसे ऐसा इनपुट दिया गया जिसे अनुबंध बाहर रखता था। और यदि $b$ ऋणात्मक होता, तो $r$ हर चक्कर में बढ़ता। पूर्व-शर्त कोई सजावट नहीं है: यह ठीक वही है जो विवेचन के काम करने के लिए आवश्यक है।

वैरिएंट की दोनों शर्तें आवश्यक हैं, और किसी में भी गलती करना आसान है। इस प्रक्रिया पर विचार करें, जिसका उद्देश्य यह तय करना है कि कोई प्राकृत संख्या $n$ सम है या नहीं: “जब तक $n \neq 0$ , $n$ का मान $n - 2$ रखें; यदि शून्य पर पहुँचें, तो $n$ सम था”। राशि $n$ हर चक्कर में घटती है, फिर भी यदि $n$ विषम है तो प्रक्रिया समाप्त नहीं होती: $n = 5$ के साथ वह $3$ , $1$ , $-1$ , $-3$ से होकर गुज़रती है, और शर्त $n \neq 0$ कभी विफल नहीं होती। जो पूरी नहीं होती, वह दूसरी शर्त है: $n$ प्राकृत संख्या नहीं रहती, क्योंकि पुनरावृत्ति की शर्त उसे शून्य से नीचे जाने से नहीं रोकती। सुधार यह है कि तब तक दोहराया जाए जब तक $n \geq 2$ , और अंत में बचे मान, $0$ या $1$ , के अनुसार निर्णय लिया जाए; अब $n$ हर चक्कर में प्राकृत संख्या है, क्योंकि घटाया केवल तब जाता है जब $n \geq 2$ , और वह घटती है: प्रक्रिया समाप्त होती है।

यह तय करना कि कोई पुनरावृत्ति समाप्त होती है या नहीं, हमेशा आसान नहीं होता। एक प्रसिद्ध उदाहरण: किसी प्राकृत संख्या $n \geq 1$ से शुरू करके, जब तक $n \neq 1$ , यदि $n$ सम है तो उसे दो से भाग दिया जाता है, और यदि विषम है तो उसके स्थान पर $3n + 1$ रखा जाता है। $n = 6$ के साथ अनुक्रम $6, 3, 10, 5, 16, 8, 4, 2, 1$ है, और समाप्त होता है। किसी को ऐसा $n$ नहीं मिला जिसके लिए यह समाप्त न हो, और कंप्यूटरों से इसकी जाँच बहुत बड़ी संख्या में मानों के लिए की जा चुकी है; लेकिन कोई यह सिद्ध नहीं कर पाया कि यह हमेशा समाप्त होता है: यह कोलाट्ज़ अनुमान है, गणित की एक खुली समस्या। कोई ज्ञात राशि हर चक्कर में नहीं घटती। प्रोग्राम लिखने वाले के लिए सीख विनम्र और दृढ़ है: जिस एल्गोरिदम की समाप्ति सिद्ध करना हम नहीं जानते, वह पूरा नहीं हुआ है।

आम त्रुटियाँ

अस्पष्ट चरण। “कई बार दोहराएँ”, “जब तक ठीक न हो जाए”, “कोई उपयुक्त संख्या लें”। हर चरण को समस्या समझे बिना चलाया जा सकना चाहिए; अन्यथा वह ठीक से नहीं लिखा गया है।
उस स्थिति को भूल जाना जिसमें पुनरावृत्ति नहीं चलती। जिस पुनरावृत्ति की शर्त आरंभ में हो, वह अपनी बॉडी शून्य बार चला सकती है। हमेशा पूछना चाहिए कि उस स्थिति में एल्गोरिदम क्या देता है, और न्यूनतम इनपुट के साथ ट्रेस इसका उत्तर देता है।
उदाहरण से विनिर्दिष्ट करना। “17 और 5 के लिए 3 और 2 देता है” विनिर्देश नहीं है; संबंध एक व्यापक शर्त के रूप में लिखा जाता है, और उदाहरण उसे स्पष्ट करता है।
एल्गोरिदम को उसके प्रोग्राम से भ्रमित करना। विफल होने वाले प्रोग्राम में एल्गोरिदम गलत हो सकता है या उसका लेखन गलत हो सकता है। जिसने पहले एल्गोरिदम नहीं लिखा, वह नहीं जानता कि दोनों में से क्या खोजे।
समाप्ति को मान लेना। किसी राशि का घटना पर्याप्त नहीं: जब तक दोहराव चलता है, उसे प्राकृत संख्या भी रहना चाहिए।

हल किए गए प्रश्न

हल किया गया प्रश्न 1तीन संख्याओं में सबसे बड़ी, बराबरी के साथ

पहले अनुभाग के तीन संख्याओं के अधिकतम का विनिर्देश पूरा करने वाला एल्गोरिदम लिखिए, और उसे इनपुट $(7, 2, 5)$ और $(4, 9, 9)$ के लिए हाथ से चलाइए।

हल

$m = x$
विचार: इनपुट पर क्रम से चलते हुए अब तक देखी गई सबसे बड़ी संख्या एक चर $m$ में रखी जाती है। पहला चरण: $m$ का मान $x$ रखें। इसके बाद $m$ देखे गए डेटा का अधिकतम है, जो केवल $x$ है।
$m = \max(x, y, z)$
दूसरा चरण: यदि $y > m$ , तो $m$ का मान $y$ रखें। तीसरा चरण: यदि $z > m$ , तो $m$ का मान $z$ रखें। चौथा चरण: $m$ आउटपुट करें। ये अनुक्रम में तीन निर्देश हैं, जिनमें से दो बिना वैकल्पिक शाखा वाले निर्णय हैं।
$(x, y, z) = (7, 2, 5) \Rightarrow m = 7$
$(7, 2, 5)$ के लिए ट्रेस: पहले चरण के बाद $m = 7$ ; दूसरे में $2 > 7$ असत्य है और $m$ नहीं बदलता; तीसरे में $5 > 7$ असत्य है और $m$ नहीं बदलता। $7$ दिया जाता है।
$(x, y, z) = (4, 9, 9) \Rightarrow m = 9$
$(4, 9, 9)$ के लिए ट्रेस: पहले चरण के बाद $m = 4$ ; दूसरे में $9 > 4$ , और $m$ का मान $9$ हो जाता है; तीसरे में $9 > 9$ असत्य है और $m$ नहीं बदलता। $9$ दिया जाता है, जो सही है: बराबरी के लिए अलग से कुछ करने की ज़रूरत नहीं।
$m \geq x, \quad m \geq y, \quad m \geq z$
औचित्य: हर चरण के बाद $m$ देखे गए डेटा में से एक है और उनमें से कोई उससे आगे नहीं निकलता। पहले चरण के बाद यह सत्य है, और हर निर्णय इसे बनाए रखता है: यदि नया डेटा बड़ा है, तो वही $m$ बन जाता है; अन्यथा, वह $m$ से आगे नहीं निकलता। अंत में तीनों देखे जा चुके हैं, और $m$ पश्च-शर्त पूरी करता है।
$(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}$
यदि $y \geq m$ लिखा होता, $y > m$ के स्थान पर, तो परिणाम वही रहता, क्योंकि बराबरी की स्थिति में बराबर मान दिया जाता है। $>$ और $\geq$ के बीच का चुनाव तब मायने रखता जब अधिकतम का स्थान भी माँगा जाता: $>$ के साथ बराबर स्थानों में से पहला दिया जाता है, और $\geq$ के साथ अंतिम, जिसे सूत्र $p$ कहता है।

हल किया गया प्रश्न 2लीप वर्ष, एक प्रति-उदाहरण से सुधारा गया

ग्रेगोरियन कैलेंडर में कोई वर्ष लीप वर्ष होता है यदि वह $4$ से विभाज्य हो, सिवाय उनके जो $100$ से विभाज्य हैं, जो तभी लीप वर्ष होते हैं जब वे $400$ से भी विभाज्य हों। एक विद्यार्थी एल्गोरिदम प्रस्तावित करता है: “यदि वर्ष $4$ से विभाज्य है, तो हाँ दें; अन्यथा नहीं दें”। ऐसा वर्ष ढूँढ़िए जिसमें यह विफल होता है, और एक सही एल्गोरिदम उसके विनिर्देश के साथ लिखिए।

हल

$(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n$
विनिर्देश। इनपुट: एक पूर्णांक $n \geq 1583$ (ग्रेगोरियन कैलेंडर अक्टूबर 1582 से लागू है)। आउटपुट: हाँ या नहीं। संबंध: आउटपुट हाँ ठीक तब है जब $n$ , $4$ से विभाज्य हो और $100$ से नहीं, या $400$ से विभाज्य हो।
$1900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300$
प्रस्तावित एल्गोरिदम अधिकांश वर्षों में सही बैठता है, और इसीलिए सही लगता है। इसका खंडन करने के लिए एक ऐसा वर्ष काफ़ी है जो $100$ से विभाज्य हो और $400$ से नहीं: $1900$ , $4$ से विभाज्य है, और एल्गोरिदम हाँ कहता है; लेकिन $1900$ लीप वर्ष नहीं था।
$400 \mid n, \quad 100 \mid n, \quad 4 \mid n$
सुधारा गया एल्गोरिदम, तीन शृंखलाबद्ध निर्णयों में। चरण 1: यदि $n$ , $400$ से विभाज्य है, तो हाँ दें और समाप्त करें। चरण 2: यदि $n$ , $100$ से विभाज्य है, तो नहीं दें और समाप्त करें। चरण 3: यदि $n$ , $4$ से विभाज्य है, तो हाँ दें; अन्यथा नहीं दें।
$2000, \quad 1900, \quad 2024, \quad 2023$
प्रश्नों का क्रम आवश्यक है: वे सबसे विशेष नियम से सबसे व्यापक नियम की ओर जाते हैं। यदि पहले $4$ के बारे में पूछा जाता, तो वर्ष $1900$ को अपवाद तक पहुँचने से पहले ही हाँ मिल जाता। चार वर्षों के लिए ट्रेस, हर स्थिति से एक: $2000$ (चरण 1: हाँ), $1900$ (चरण 2: नहीं), $2024$ (चरण 3: हाँ), $2023$ (चरण 3: नहीं)।
$4 \mid 1900 \wedge \neg (400 \mid 1900)$
सीख केवल कैलेंडरों की नहीं है: एल्गोरिदम का खंडन एक ही प्रति-उदाहरण से होता है, और प्रति-उदाहरण नियमों की सीमाओं पर खोजे जाते हैं, सामान्य स्थितियों में नहीं। $2024$ , $2020$ और $2016$ से परखने पर कुछ भी पता न चलता।

हल किया गया प्रश्न 3घटाव द्वारा विभाजन कितने चक्कर लगाता है

क्रमिक घटाव द्वारा विभाजन को $a = 20$ और $b = 5$ के साथ, और $a = 0$ और $b = 7$ के साथ हाथ से चलाइए। फिर सिद्ध कीजिए कि हर स्वीकार्य इनपुट के लिए एल्गोरिदम ठीक $q$ चक्करों के बाद समाप्त होता है और उसका आउटपुट पश्च-शर्त पूरी करता है।

हल

$20 = 5 \cdot 4 + 0$
$a = 20$ , $b = 5$ के साथ ट्रेस: $r$ क्रम से $20$ , $15$ , $10$ , $5$ , $0$ होता है, और $q$ क्रम से $0$ , $1$ , $2$ , $3$ , $4$ । पाँचवीं जाँच, $0 \geq 5$ , विफल होती है। आउटपुट: $q = 4$ , $r = 0$ । यहाँ सीमांत स्थिति पूर्ण विभाजन की है: चौथा चक्कर इसलिए लगता है कि $5 \geq 5$ , और इसीलिए शर्त $\geq$ होनी चाहिए, $>$ नहीं।
$0 = 7 \cdot 0 + 0$
$a = 0$ , $b = 7$ के साथ ट्रेस: पहली जाँच, $0 \geq 7$ , विफल होती है; बॉडी एक भी बार नहीं चलती। आउटपुट: $q = 0$ , $r = 0$ , जो सही है।
$\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}$
एक संबंध जो बना रहता है। पहले चक्कर से पहले, $b \cdot q + r = b \cdot 0 + a = a$ । हर चक्कर में $r$ , $b$ घटता है और $q$ , $1$ बढ़ता है, इसलिए $b \cdot q + r$ नहीं बदलता। अतः यह समता हर चक्कर के बाद सत्य रहती है।
$r_0 > r_1 > r_2 > \cdots \geq 0$
समाप्ति। जब तक दोहराव चलता है, $r \geq b > 0$ , और $r$ एक प्राकृत संख्या है; हर चक्कर में वह $b \geq 1$ घटता है। प्राकृत संख्याओं का निरंतर घटता अनुक्रम परिमित होता है: पुनरावृत्ति समाप्त होती है।
$a = b \cdot q + r, \quad 0 \leq r < b$
समाप्त होने पर शर्त विफल हुई: $r < b$ । इसके अतिरिक्त $r \geq 0$ , क्योंकि $b$ तभी घटाया जाता है जब $r \geq b$ । बने रहने वाले संबंध के साथ मिलकर, आउटपुट पश्च-शर्त पूरी करता है; और क्योंकि $q$ चक्करों को गिनता है, चक्करों की संख्या भागफल है।

ऑनलाइन अभ्यास

अभ्यास 1चक्कर गिनना

नीचे दिए गए एल्गोरिदम को हाथ से चलाइए और खाने में वह मान लिखिए जो वह देता है, केवल अंक।

$n$ का मान $29$ रखें, और $k$ का मान $0$ रखें।
जब तक $n > 1$ सत्य रहे, चरण 3 और 4 दोहराएँ; जब वह सत्य न रहे, तो चरण 5 पर जाएँ।
यदि $n$ सम है, तो $n$ का मान $n / 2$ रखें; यदि विषम है, तो $n$ का मान $n + 1$ रखें।
$k$ का मान $k + 1$ रखें; चरण 2 पर लौटें।
$k$ आउटपुट करें।

ब्राउज़र आपके उत्तर को तुरंत जाँचता है, पर अंक नहीं देता।

अपना उत्तर यहाँ लिखें

संकेत

तालिका बनाओ: पहले चक्कर में $n$ , $29$ से $30$ हो जाता है। $n$ के हर बदलाव पर एक चक्कर गिनो, जब तक $n$ का मान $1$ न हो जाए।

अभ्यास 2छूटी हुई शर्त

नीचे दिया गया एल्गोरिदम, जो संक्षिप्त रूप में लिखा है, क्रमिक घटाव द्वारा विभाजन का भागफल और शेषफल निकालने वाला है, लेकिन उसमें पुनरावृत्ति की शर्त छूटी हुई है। अंडरस्कोर वाली रेखा को सही शर्त से बदलिए, बाकी कुछ बदले बिना।

ब्राउज़र आपके उत्तर को तुरंत जाँचता है, पर अंक नहीं देता।

अपना उत्तर यहाँ लिखें

संकेत

एल्गोरिदम को $a = 10$ और $b = 5$ के साथ हाथ से चलाओ: दूसरा चक्कर लगना ही चाहिए, भले ही शेषफल ठीक $5$ हो।

हल देखें

इनपुट: a (पूर्णांक, a >= 0), b (पूर्णांक, b > 0)1. q <- 02. r <- a3. जब तक r >= b दोहराएँ:     r <- r - b     q <- q + 14. आउटपुट q, r

अभ्यास प्रश्न

हर प्रश्न के साथ एक संकेत है, जिसे स्वयं प्रयास करने के बाद ही खोलना अच्छा है, और एक उत्तर है, जो संकेत खोलने के बाद दिखता है।

अभ्यास प्रश्न 1तीन संख्याओं के क्रम का विनिर्देश

समस्या “तीन संख्याओं को क्रम में लगाओ” का विनिर्देश (इनपुट, आउटपुट और संबंध) लिखिए और बताइए कि वह कौन-से ऐसे निर्णय लेने को बाध्य करता है जो कथन ने नहीं लिए थे। फिर जाँचिए कि विनिर्देश इनपुट $(5, 2, 5)$ के लिए ये दो आउटपुट अस्वीकार करता है: $(2, 5, 6)$ और $(2, 5, 5, 5)$ , और $(2, 5, 5)$ को स्वीकार करता है।

संकेत

एक “क्रमबद्ध” आउटपुट का इनपुट से कोई लेना-देना न हो, ऐसा हो सकता है। कौन-सी शर्त आउटपुट की संख्याओं को इनपुट की संख्याओं से जोड़ती है, दोहराई गई संख्याओं सहित? आरोही या अवरोही? सख़्त या नहीं?

उत्तर

इनपुट: तीन संख्याएँ $x$ , $y$ , $z$ । आउटपुट: तीन संख्याएँ $u$ , $v$ , $w$ । संबंध: $u \leq v \leq w$ , और $(u, v, w)$ , $(x, y, z)$ का एक पुनर्विन्यास है, अर्थात उसमें वही मान उतनी ही पुनरावृत्तियों के साथ हैं। निर्णय जो कथन ने नहीं लिए थे: दिशा (यहाँ, छोटे से बड़े की ओर); यह कि क्रम सख़्त नहीं है ( $\leq$ और $<$ नहीं, क्योंकि दोहराए गए मानों के साथ सख़्त क्रम असंभव है); और यह कि आउटपुट एक पुनर्विन्यास होना चाहिए। $(2, 5, 6)$ क्रमबद्ध है पर उसमें एक $6$ है जो पहले नहीं था; $(2, 5, 5, 5)$ में चार मान हैं; $(2, 5, 5)$ दोनों शर्तें पूरी करता है। पुनर्विन्यास की शर्त के बिना $(0, 0, 0)$ किसी भी इनपुट के लिए सही आउटपुट होता।

अभ्यास प्रश्न 2किसी संख्या के अंक, दाएँ से बाएँ

क्रमांकित चरणों में एक एल्गोरिदम लिखिए जो एक प्राकृत संख्या $n$ ले और उसके अंक अंतिम से पहले की ओर दे ( $4072$ के लिए $2$ , $7$ , $0$ , $4$ देता है), केवल $10$ से भाग देने के भागफल और शेषफल का उपयोग करते हुए। इसे $4072$ और $0$ के लिए हाथ से चलाइए, और सिद्ध कीजिए कि यह हर $n$ के लिए समाप्त होता है।

संकेत

$10$ से भाग देने का शेषफल अंतिम अंक है, और भागफल उस अंक के बिना की संख्या है। तय करो कि शर्त अंक देने से पहले पूछी जाए या बाद में, और देखो कि $n = 0$ के साथ क्या होता है, जिसमें एक अंक है।

उत्तर

एक सही एल्गोरिदम: (1) $n$ को $10$ से भाग देने का शेषफल दें; (2) $n$ का मान $n$ को $10$ से भाग देने का भागफल रखें; (3) यदि $n > 0$ , तो चरण 1 पर लौटें; अन्यथा समाप्त करें। प्रश्न बॉडी के बाद आता है, इसलिए बॉडी कम से कम एक बार चलती है: $n = 0$ के लिए $0$ दिया जाता है, जो उसका एकमात्र अंक है। यदि प्रश्न आरंभ में पूछा जाता (“जब तक $n > 0$ ”), तो $n = 0$ के लिए कुछ भी न दिया जाता; यह उस स्थिति को भूलने की त्रुटि है जिसमें पुनरावृत्ति नहीं चलती। $4072$ के लिए ट्रेस: $2$ , $7$ , $0$ , $4$ दिए जाते हैं, और $n$ क्रम से $407$ , $40$ , $4$ , $0$ होता है। समाप्ति: वैरिएंट $n$ है, एक प्राकृत संख्या; यदि चरण 1 पर लौटा जाता है तो इसलिए कि $n > 0$ , और $n \geq 1$ के लिए $10$ से भागफल $n$ से छोटा है, इसलिए $n$ हर चक्कर में निरंतर घटता है।

अभ्यास प्रश्न 3सिक्कों में रेज़गारी

$50$ , $10$ और $1$ के सिक्के असीमित संख्या में उपलब्ध हैं। विनिर्देश: इनपुट, एक प्राकृत संख्या $m$ ; आउटपुट, तीन प्राकृत संख्याएँ $c_{50}$ , $c_{10}$ , $c_1$ , जिनके लिए $50 c_{50} + 10 c_{10} + c_1 = m$ और सिक्कों की संख्या, $c_{50} + c_{10} + c_1$ , न्यूनतम संभव हो। कोई व्यक्ति नीचे दिया गया एल्गोरिदम प्रस्तावित करता है। ऐसा इनपुट ढूँढ़िए जिसमें यह विफल होता है, हर दोष समझाइए और उसे सुधारिए।

$c_{50}$ , $c_{10}$ और $c_1$ का मान $0$ रखें।
यदि $m \geq 50$ , तो $c_{50}$ का मान $c_{50} + 1$ रखें और $m$ का मान $m - 50$ रखें।
जब तक $m > 10$ : $c_{10}$ का मान $c_{10} + 1$ रखें और $m$ का मान $m - 10$ रखें।
जब तक $m > 0$ : $c_1$ का मान $c_1 + 1$ रखें और $m$ का मान $m - 1$ रखें।
$c_{50}$ , $c_{10}$ और $c_1$ आउटपुट करें।

संकेत

सिक्कों का योग हमेशा $m$ होता है; जो विफल हो सकती है, वह उनकी संख्या है। $10$ का कोई सटीक गुणज और $100$ से अधिक की कोई राशि आज़माओ, और स्वयं से पूछो कि चरण 2 चरणों को जोड़ने का कौन-सा तरीका प्रयोग करता है और उसे कौन-सा प्रयोग करना चाहिए।

उत्तर

दो दोष हैं। पहला, चरण 3 $m > 10$ का प्रयोग करता है: $m = 10$ होने पर वह $10$ का एक भी सिक्का नहीं देता और $1$ के दस सिक्के देता है, एक के स्थान पर। दूसरा, चरण 2 एक निर्णय है जहाँ पुनरावृत्ति चाहिए: $m = 120$ होने पर, जैसा लिखा है वैसा एल्गोरिदम $50$ का एक सिक्का, $10$ के छह और $1$ के दस (सत्रह सिक्के) देता है, और चरण 3 सुधारने के बाद भी $50$ का एक और $10$ के सात (आठ) देता, जबकि $50$ के दो और $10$ के दो (चार) चाहिए। इनपुट $m = 100$ दोनों दोष दिखाता है: एल्गोरिदम $50$ का एक, $10$ के चार और $1$ के दस, कुल पंद्रह सिक्के देता है, दो के स्थान पर। सुधार: चरण 2, “जब तक $m \geq 50$ , …”; चरण 3, “जब तक $m \geq 10$ , …”। इस प्रकार सुधारने पर एल्गोरिदम हमेशा वह सबसे बड़ा सिक्का लेता है जो समा सके, और इन तीन सिक्कों के साथ इससे न्यूनतम संख्या मिलती है: $m$ का अंतिम अंक केवल $1$ के सिक्कों से चुकाया जा सकता है, और जो बचता है उसे जितना संभव हो $50$ के सिक्कों से चुकाना लाभदायक है, क्योंकि $10$ के पाँच सिक्के $50$ के एक सिक्के के बराबर हैं। दूसरे सिक्कों के साथ, उदाहरण के लिए $1$ , $3$ और $4$ के सिक्के $m = 6$ के लिए, हमेशा सबसे बड़ा लेने से न्यूनतम नहीं मिलता ( $4 + 1 + 1$ बनाम $3 + 3$ )।