ऐरे में क्रम से जाँच और संचायक का अर्थ

तत्वों तक जाएँ और अवस्था पर नज़र रखें

ऐरे के ट्रेस में हर तत्व दर्ज होता है। लूप से हम कई जगहों तक क्रम से जा सकते हैं, लेकिन पुराने नियम वही हैं: वर्तमान अवस्था लें, चुना इंडेक्स जाँचें और हर अपडेट को उसी जगह दर्ज करें जहाँ वह होता है।

इस पाठ में आप बताएँगे कि ऐरे का कौन-सा शुरुआती हिस्सा संसाधित हो चुका है, इंडेक्स को गिनती और योग से अलग रखेंगे तथा बाद के मिलान से पहला परिणाम बदले बिना पहली मेल खाती जगह खोजेंगे। आप चुने हुए खाली शुरुआती हिस्से को भी सुरक्षित ढंग से संभालेंगे।

पहले से आवश्यक बातें: शर्तें, शॉर्ट सर्किट, सीमित लूप, संचायक और वर्तमान अवस्था के ट्रेस वाले स्वीकृत बुनियादी पाठ, साथ में ऐरे के तत्व और सही इंडेक्स वाला पिछला पाठ। पॉइंटर, बीच में लूप छोड़ने वाले स्टेटमेंट या औपचारिक जटिलता-संकेत आवश्यक नहीं हैं।

पढ़ाने के लिए हम C11 का उपयोग करते हैं। ऐरे के आकार स्पष्ट धनात्मक स्थिरांक हैं और उनके int तत्व इनिशियलाइज़ हैं। अलग length बताता है कि शुरुआत से कितने तत्व संसाधित करने हैं। यह शून्य से वास्तविक तत्वों की संख्या तक, दोनों सिरों सहित, होना चाहिए। दिखाई गई हर पूर्णांक गणना −32767 से 32767 के भीतर है। हर पूरा प्रोग्राम अलग उदाहरण है; उन्हें जोड़कर एक प्रोग्राम न बनाएँ। गद्य में चर्चा की गई गलत सीमा-शर्तें केवल तर्क के लिए हैं, चलाने के लिए नहीं।

वास्तविक क्षमता, चुनी लंबाई और अगला इंडेक्स

int readings[5] = {3, 8, 0, 6, 2}; में पाँच तत्व हैं, जिनके इंडेक्स 0 से 4 हैं। इस पाठ में क्षमता का अर्थ वास्तविक तत्वों की यही संख्या है। यह बाइट की संख्या नहीं है।

length का चुना मान 3 हो, तो इंडेक्स 0, 1 और 2 संसाधित करें। इस शुरुआती हिस्से को prefix कहते हैं। इंडेक्स 3 और 4 के तत्व मौजूद रहते हैं, लेकिन चुने हिस्से के बाहर हैं। length = 5 पूरा ऐरे चुनता है। length = 0 कोई तत्व नहीं चुनता; उससे C में शून्य लंबाई का ऐरे घोषित नहीं होता और मौजूद स्टोरेज हटता भी नहीं।

आगे की ओर जाँच के लिए i को 0 से शुरू करें और i < length लें। जाँच से ठीक पहले i अगला संभावित इंडेक्स है। जाँच सही हो, तो body उस जगह तक पहुँच सकती है। लूप के i++ अपडेट चरण के बाद अगली जाँच नया इंडेक्स लेती है। यह अपडेट body के बाद होता है; यह body के भीतर छिपा कोई अतिरिक्त स्टेटमेंट नहीं है।

readings[length] को अंतिम चुना तत्व न समझें। गैर-खाली शुरुआती हिस्से का अंतिम तत्व length - 1 पर है। लंबाई शून्य हो, तो कोई अंतिम चुना तत्व है ही नहीं। हमारे लूप उस स्थिति में कोई body नहीं चलाते; वे इंडेक्स −1 निकालकर उस तक पहुँचने की कोशिश नहीं करते।

हल किया हुआ उदाहरण 1 चुने मानों की गिनती और योग

हमें कम-से-कम 5 वाले readings की गिनती और उनका योग चाहिए। इंडेक्स, गिनती और योग का काम अलग है। आउटपुट बताएँ, फिर हर संचायक का अर्थ समझाएँ।

#include <stdio.h>

int main(void)
{
    int readings[5] = {3, 8, 0, 6, 2};
    int length = 5;
    int count = 0;
    int total = 0;
    for (int i = 0; i < length; i++) {
        if (readings[i] >= 5) {
            count++;
            total += readings[i];
        }
    }
    printf("%d %d\n", count, total);
    return 0;
}

हर body के तुरंत बाद की अवस्था देखें:

आखिरी body के बाद अपडेट लूप के i को 5 करता है। जाँच 5 < 5 गलत है, इसलिए इंडेक्स 5 तक कोई अभिगम नहीं होता। आउटपुट 2 14 है, जिसके बाद नई पंक्ति आती है। ऐरे नहीं बदला: body उसके तत्व पढ़ती है और केवल संचायकों में लिखती है।

लूप की पाँच body, पाँच अपडेट और अंतिम गलत जाँच सहित छह लूप-शर्त जाँच हैं। भीतर की if शर्त पाँच बार जाँची जाती है। भीतर की दो चुनी शाखाएँ count और total को दो बार अपडेट करती हैं। लूप की body चलना और भीतर की चुनी शाखा चलना एक ही घटना नहीं है।

किसी चुने बिंदु पर संचायक का अर्थ बताएँ

हर लूप-जाँच से ठीक पहले वाला बिंदु चुनें। वहाँ:

• चुने शुरुआती हिस्से के i तत्व देखे जा चुके हैं, जिनके इंडेक्स 0 से i - 1 हैं
• count उन देखे तत्वों की संख्या है जिनका मान कम-से-कम 5 है
• total उन्हीं योग्य देखे मानों का योग है

i शून्य हो, तो कोई तत्व नहीं देखा गया है। इसलिए शुरुआती गिनती 0 और योग 0 सही हैं। इस बिंदु पर “0 से i - 1” खाली समूह का वर्णन है; यह इंडेक्स −1 तक पहुँचने का निर्देश नहीं है।

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

अंत में जाँच गलत होने पर i, length के बराबर है, इसलिए वर्णन पूरे चुने शुरुआती हिस्से पर लागू है। शुरुआती मान, हर बार एक की प्रगति और सीमित सही लंबाई यह भी समझाते हैं कि लूप क्यों रुकता है। length = 0 हो, तो पहली जाँच ही गलत है: शून्य body, एक लूप-जाँच, गिनती 0 और योग 0। वास्तविक पाँच तत्वों वाला ऐरे मौजूद रहता है।

5 19 हर reading को गिनता और जोड़ता है, यानी भीतर की शर्त छोड़ देता है। 2 2 योग को योग्य तत्वों की संख्या समझता है। हर body के भीतर total = 0 करने से पहले जोड़े गए मान खो जाएँगे। ये अलग गलतियाँ हैं, इसलिए व्याख्या में बताएँ कि हर चर को क्या बचाकर रखना है।

हल किया हुआ उदाहरण 2 पहली मेल खाती जगह बचाएँ

लक्ष्य एक से अधिक जगह हो सकता है। हम पूरा चुना शुरुआती हिस्सा जाँचेंगे, लेकिन केवल सबसे पहली मेल खाती जगह का इंडेक्स रखेंगे। −1 हमारा नहीं-मिला संकेत है, क्योंकि वह सही तत्व-इंडेक्स के बाहर है। यह संकेत है, पढ़ने का इंडेक्स कभी नहीं।

#include <stdio.h>

int main(void)
{
    int values[6] = {7, 2, 5, 2, 9, 2};
    int length = 6;
    int target = 2;
    int first = -1;
    for (int i = 0; i < length; i++) {
        if (first == -1 && values[i] == target) {
            first = i;
        }
    }
    printf("%d\n", first);
    return 0;
}

• इंडेक्स 0 देखने से पहले: first = -1; पहले देखी किसी जगह पर मिलान नहीं है
• इंडेक्स 0 पर first == -1 सही है, इसलिए मान 7 की तुलना लक्ष्य 2 से करें। मिलान नहीं है; first −1 रहता है
• इंडेक्स 1 पर अभी तक कोई मिलान दर्ज नहीं हुआ है। मान 2 मिलता है, इसलिए इंडेक्स रखें: first = 1
• इंडेक्स 2, 3, 4 और 5 पर first == -1 गलत है। && तत्व की तुलना छोड़ता है, असाइनमेंट नहीं होता और first 1 रहता है
• इंडेक्स 5 के बाद अपडेट इंडेक्स 6 तैयार करता है; लूप-जाँच गलत होती है। आउटपुट: 1, फिर नई पंक्ति

चर में जगह रखी जाती है, लक्ष्य का मान नहीं। उत्तर 1 है, 2 नहीं। बाद के मेल खाते इंडेक्स 3 और 5 सहेजी गई जगह को नहीं बदलते। first == -1 वाला गार्ड पहले परिणाम को बाद के असाइनमेंट से बचाता है; वह लूप नहीं रोकता। अभी भी छह body और सात लूप-जाँच हैं। इस निष्पादन में values[i] == target की तुलना केवल इंडेक्स 0 और 1 पर होती है।

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

किसी चुने तत्व का मिलान न हो, तो संकेत −1 रहता है। चुनी लंबाई शून्य हो, तो कोई जगह नहीं देखी जाती और तब भी वह −1 रहता है। दोनों ही स्थितियों में values[first] पढ़ना सही नहीं है। दर्ज जगह का उपयोग करने से पहले जाँचें कि मिलान मिला या नहीं। यहाँ के प्रोग्रामों में if (first != -1) पर्याप्त है, क्योंकि हमारा तरीका केवल −1 या कोई सही चुना इंडेक्स देता है; यह किसी और से मिले मनमाने पूर्णांक की सामान्य वैधता-जाँच नहीं है।

लूप से पहले उसकी शर्तें तय करें

यहाँ हर जाँच में इनिशियलाइज़ किया हुआ स्टोरेज और 0 <= length <= capacity माना गया है। लूप-शर्त चुनी हुई ऊपरी सीमा तभी लागू करती है जब ये शर्तें पहले से सही हों। पाँच तत्वों के ऐरे को length = 8 देने से वह बड़ा नहीं हो जाता और i < length उस गलत लंबाई से सुरक्षा नहीं दे सकता।

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

हल देखने से पहले अभ्यास

ये चार मौलिक प्रश्न सीखने के लिए हैं और इनके अंक नहीं हैं। अपने उत्तर को समझाने वाली अवस्था दर्ज करें। कोई प्रस्तावित गलत सीमा-शर्त इसलिए न चलाएँ कि उससे संयोग से कौन-सी संख्या निकलती है।

अभ्यास 1 अपडेट हुए तत्वों को जोड़ें

अंतिम ऐरे और आउटपुट दें। total में मूल मान जुड़ते हैं या अपडेट होने के बाद वाले मान?

#include <stdio.h>

int main(void)
{
    int a[4] = {2, 5, 1, 4};
    int total = 0;
    for (int i = 0; i < 4; i++) {
        a[i] = a[i] + i;
        total += a[i];
    }
    printf("%d %d %d\n", total, a[1], a[3]);
    return 0;
}

अभ्यास 2 चुना शुरुआती हिस्सा खाली है

body और लूप-जाँच की संख्या बताएँ और आउटपुट दें। क्या i < length की जगह i <= length रखना 0 से 3 तक हर अनुमत लंबाई के लिए सही है?

#include <stdio.h>

int main(void)
{
    int values[3] = {6, 1, 9};
    int length = 0;
    int count = 0;
    int total = 0;
    for (int i = 0; i < length; i++) {
        count++;
        total += values[i];
    }
    printf("%d %d %d\n", count, total, values[0]);
    return 0;
}

अभ्यास 3 नाम पहली जगह मिलने की गारंटी नहीं देता

प्रोग्राम का व्यवहार निश्चित है, लेकिन क्या यह पहली occurrence खोजता है? वास्तविक आउटपुट दें। फिर केवल भीतर की शर्त बदलें, ताकि पहली मेल खाती जगह बनी रहे।

#include <stdio.h>

int main(void)
{
    int a[5] = {4, 7, 4, 1, 4};
    int first = -1;
    for (int i = 0; i < 5; i++) {
        if (a[i] == 4) {
            first = i;
        }
    }
    printf("%d\n", first);
    return 0;
}

अभ्यास 4 केवल चुना शुरुआती हिस्सा खोजें

पूरे ऐरे में 6 मौजूद है। समझाएँ कि प्रोग्राम उसे बताता है या नहीं और क्यों। आउटपुट दें और बताएँ कि गार्ड के भीतर वाला तत्व-पठन होता है या नहीं।

#include <stdio.h>

int main(void)
{
    int a[5] = {4, 8, 6, 8, 1};
    int length = 2;
    int target = 6;
    int first = -1;
    for (int i = 0; i < length; i++) {
        if (first == -1 && a[i] == target) {
            first = i;
        }
    }
    int matched_value = 0;
    if (first != -1) {
        matched_value = a[first];
    }
    printf("%d %d\n", first, matched_value);
    return 0;
}

पूरे हल और गलत उत्तरों का कारण

अभ्यास 1 का हल

इंडेक्स 0 पर 2 + 0 = 2 रखें; अपडेट हुआ 2 जोड़ने से total = 2 मिलता है। इंडेक्स 1 पर 5 + 1 = 6 रखें; योग 8 हो जाता है। इंडेक्स 2 पर 1 + 2 = 3 रखें; योग 11 होता है। इंडेक्स 3 पर 4 + 3 = 7 रखें; योग 18 होता है।

अंतिम ऐरे {2, 6, 3, 7} है। अंतिम अपडेट के बाद लूप 4 < 4 जाँचता है, जो गलत है। चार body और पाँच लूप-जाँच हैं। आउटपुट: 18 6 7, फिर नई पंक्ति।

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

योग 12 केवल मूल मान जोड़ता है। योग 6 केवल इंडेक्स जोड़ता है। आउटपुट 18 5 4 अपडेट हुए मानों का योग सही निकालकर भी ऐरे के बदलाव भूलता है। अवस्था के रिकॉर्ड में रखे हुए ऐरे और संचायक, दोनों का हिसाब चाहिए।

अभ्यास 2 का हल

इनिशियलाइज़ेशन i = 0 करता है। पहली जाँच 0 < 0 गलत है। शून्य body, शून्य अपडेट और एक लूप-जाँच हैं। दोनों संचायक शून्य रहते हैं। बाद में printf का values[0] वास्तविक ऐरे के पहले तत्व तक अलग, सही अभिगम है, जिसका मान अभी भी 6 है। आउटपुट: 0 0 6, फिर नई पंक्ति।

खाली चुने शुरुआती हिस्से से पूरा ऐरे गायब नहीं होता और शून्य लंबाई की घोषणा भी आवश्यक नहीं है। दूसरी ओर, मान 6 मौजूद होने से गलत पहली जाँच वाला लूप एक बार चलने नहीं लगता।

प्रस्तावित i <= length गलत है। लंबाई 0 पर वह इंडेक्स 0 संसाधित करेगा, जबकि कोई तत्व चुना ही नहीं गया। लंबाई 3 पर वह अंततः इंडेक्स 3 तक पहुँचने की कोशिश करेगा, जो तीन तत्वों वाले ऐरे के बाहर है। उस पूरी लंबाई वाली स्थिति में अपरिभाषित व्यवहार है; कोई निश्चित संख्यात्मक आउटपुट नहीं दिया जा सकता। गलत सीमा को चलाए बिना उसका वर्गीकरण करें। तत्वों की संख्या और इंडेक्स के सही संबंध के लिए ऊपरी जाँच में < चाहिए।

अभ्यास 3 का हल

मेल खाते इंडेक्स 0, 2 और 4 हैं। हर जगह असाइनमेंट होता है: first पहले 0, फिर 2, फिर 4 बनता है। बीच के तत्व मेल नहीं खाते, इसलिए उसे नहीं बदलते। प्रोग्राम 4 और फिर नई पंक्ति प्रिंट करता है: first नाम होने पर भी उसने अंतिम मेल खाता इंडेक्स रखा।

भीतर की शर्त first == -1 && a[i] == 4 लें। पूरा सुधरा हुआ प्रोग्राम है:

#include <stdio.h>

int main(void)
{
    int a[5] = {4, 7, 4, 1, 4};
    int first = -1;
    for (int i = 0; i < 5; i++) {
        if (first == -1 && a[i] == 4) {
            first = i;
        }
    }
    printf("%d\n", first);
    return 0;
}

सुधरी शर्त इंडेक्स 0 पर first = 0 दर्ज करती है। बाद की body देखती हैं कि संकेत अब −1 नहीं है और उसे वैसे ही रहने देती हैं। सुधरा आउटपुट 0 है, फिर नई पंक्ति। दोनों संस्करणों में पाँच body और छह लूप-जाँच हैं; केवल भीतर की शर्त अलग है।

सुधरे संस्करण का उत्तर 4 बताना नया गार्ड भूलना है। शुरुआती मान को 0 कर देना सामान्य सुधार नहीं है: इससे किसी तुलना के पहले ही इंडेक्स 0 पर मिलान का दावा होगा, चाहे लक्ष्य ऐरे में न हो। चर का नाम बदलने से भी निष्पादन नहीं बदलता।

अभ्यास 4 का हल

केवल जगह 0 और 1 चुने शुरुआती हिस्से में हैं। इंडेक्स 0 पर मान 4, लक्ष्य 6 के बराबर नहीं है, इसलिए first −1 रहता है। इंडेक्स 1 पर मान 8 भी 6 के बराबर नहीं है। अपडेट से इंडेक्स 2 होने के बाद 2 < 2 गलत है और खोज समाप्त होती है। इंडेक्स 2 के मान से तुलना कभी नहीं होती।

जाँच first != -1 गलत है, इसलिए a[first] का मूल्यांकन नहीं होता। matched_value का स्पष्ट शुरुआती वैकल्पिक मान 0 बना रहता है। आउटपुट: -1 0, फिर नई पंक्ति। −1 वाला संकेत नहीं मिलने की जानकारी देता है; साथ में 0 प्रिंट करना इस प्रोग्राम की चुनी व्यवस्था है, वह नहीं-मिले तत्व का कोई सार्वभौमिक मान नहीं है।

2 6 चुने शुरुआती हिस्से के बाहर खोजता है। -1 6 गलत गार्ड के बावजूद किसी न चुने तत्व को पढ़ता है। केवल matched_value में शून्य देखकर शून्य मान वाला मिला तत्व और कोई मिलान न होना अलग नहीं किए जा सकते; जगह/संकेत की जाँच को व्याख्या का हिस्सा रखें।

आगे बढ़ने से पहले

केवल अंत में छपने वाला मान नहीं, बल्कि अगली लूप-जाँच से पहले हर चर का अर्थ समझाएँ। आप खाली शुरुआती हिस्से, अनुपस्थित लक्ष्य और बाद के दोहराए मिलान में अंतर कर सकें। अगला पाठ पॉइंटर का लक्ष्य बताएगा और एक ही पूर्णांक ऑब्जेक्ट तक दो रास्तों का ट्रेस करेगा; यहाँ इस्तेमाल हुआ वर्तमान अवस्था का तरीका नहीं बदलेगा।

स्रोत टिप्पणी

व्याख्याएँ, प्रोग्राम, ट्रेस और अभ्यास मौलिक हैं। C के तथ्यों की जाँच WG14 N1570 C11 समिति-ड्राफ्ट से की गई: इंडेक्स वाले तत्व और सीमाएँ §§6.5.2.1p2, 6.5.6p8; for का क्रम §6.8.5.3p1; लूप का रुकना §6.8.5p4; चुनी शाखाएँ §6.8.4.1p2; शॉर्ट सर्किट §6.5.13p4; असाइनमेंट और अपडेट §§6.5.16.1p2, 6.5.16.2p3, 6.5.2.4p2। संदर्भ: https://open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

C11 इस पाठ्यक्रम में पढ़ाने के लिए चुना गया संस्करण है। ये जाँचें ऐरे का तर्क और सरल खोज शुरू करती हैं; इनसे GATE की पूरी searching, complexity या Programming and Data Structures की तैयारी पूरी नहीं होती।

सूत्र और नियम

• क्षमता वास्तविक तत्वों की संख्या है; length शून्य से उस क्षमता तक का शुरुआती हिस्सा चुनता है
• आगे की जाँच में i = 0; i < length; i++ ठीक चुनी हुई जगहों तक जाता है
• जाँच से ठीक पहले देखे हुए शुरुआती हिस्से और हर संचायक का अर्थ बताएँ
• गिनती बताती है कि कितने तत्व नियम पूरा करते हैं; योग उनके मान जोड़ता है; इंडेक्स जगह का नाम देता है
• संचायक लूप से पहले इनिशियलाइज़ करें, ताकि पहले जोड़े गए मान बने रहें
• लंबाई 0 में शून्य body और एक शुरुआती गलत जाँच होती है, शून्य आकार का C ऐरे नहीं
• पहली जगह खोजते समय −1 का संकेत बताता है कि अभी मिलान नहीं मिला; संकेत −1 होने पर ही इंडेक्स दर्ज करें
• पहले मिलान का गार्ड लूप नहीं रोकता; वह बाद के असाइनमेंट से पहले परिणाम को बचाता है
• इंडेक्स के उपयोग से पहले मिलान मिलने की जाँच करें; −1 संकेत को ऐरे पढ़ने के लिए कभी न लें
• चुनी लंबाई वास्तविक ऐरे में समानी चाहिए; लूप-शर्त क्षमता के गलत दावे को ठीक नहीं कर सकती