Chapter ke text par jao
Ganita ManjariCh 11 Algorithms ki Duniya

The World of Algorithms (Algorithms ki Duniya): Class 9 Maths Chapter 11 Hinglish mein

Ganita Manjari Part 2 · Hinglish notes, simulations aur practice · Official NCERT chapter PDF ↗

Published · Updated

  • 65 min
  • 22 practice questions
  • 20 MCQs

Is chapter mein aap kya seekhenge

  • Samjhao ki algorithm kya hota hai, aur uske basic steps, repeated steps aur conditional steps pehchaano.
  • Column addition ko carry ke saath ek precise algorithm ki tarah likho, use execute karo, aur place value se justify karo.
  • Do methods ke kaam ko compare karo: yeh dekho ki numbers bade hone par kaam kitna badhta hai.
  • Definition se shuru karke divisors ki lists se gcd algorithms banao, aur unhe step by step improve karo.
  • List ko ek data structure ki tarah samjhao aur is baat ka use karo ki list sorted hai.
  • Prove karo ki gcd(m, n) = gcd(n, m − n) aur gcd(m, n) = gcd(n, m mod n), aur inhe Euclid’s algorithm mein use karo.
  • Āryabhaṭa ke division method se bade numbers ka gcd nikaalo aur samjhao ki usmein itne kam steps kyun lagte hain.

NCERT Mathematics Class 9, Chapter 11, pp. 37–50 par based original companion text. Yeh NCERT se juda nahi hai aur NCERT ne ise endorse nahi kiya hai.

Map app se railway station ka sabse jaldi wala raasta poocho, aur woh ek second ke andar route bata deta hai. Music app agla gaana chun leta hai, aur shopping site andaaza laga leti hai ki tum kya khareed sakte ho. Log kandhe uchkaakar kehte hain, “algorithm ne decide kiya”. To yeh algorithm naam ki cheez hai kya, aur ismein mathematics kahan aata hai?

Socho ghar mein chai kaise banti hai. Paani ubaalo, chai patti daalo, phir doodh, phir cheeni “swaad anusaar”. Yeh steps ki ek list hai, lekin “swaad anusaar” decide karna cook par chhod deta hai. Mathematical procedure kuch bhi swaad par nahi chhodta. Har step bilkul saaf batata hai ki kya karna hai, isliye jo bhi use follow kare, same answer tak pahunchta hai. Is chapter mein hum aise do procedures ko dhyaan se padhenge: numbers jodna aur greatest common divisor nikaalna. Har ek ke liye hum teen sawaal poochhenge. Exact steps kya hain? Woh sahi answer kyun dete hain? Unmein kitna kaam lagta hai?

11.1 Numbers Jodna

Maan lo kisi ne tumhe kabhi column addition nahi sikhaya, aur koi 586 + 749 pooch le. Tum 586 dots bana sakte ho, phir 749 aur bana sakte ho, aur poori bheed gin sakte ho: poore 1335. Chhote bachche 6 + 8 sach mein aise hi jodte hain, sab kuch gin kar. Yeh method kabhi fail nahi hota, lekin bade numbers ke liye isme ek zamaana lag jaayega.

Tum pehle se ek kahin behtar tareeka jaante ho, aur Fig. 11.1 ek chhote sum ke liye use counting ke saath rakhta hai. Left mein har dot ginna padta hai. Right mein numbers place value ke hisaab se ek ke neeche ek rakhe hain, aur do single-digit sums kaam khatam kar dete hain. Jab kisi column ka total 10 ya usse zyada ho jaata hai, to ek carry agle column ko de diya jaata hai.

3/3Column method ko bas do one-digit sums chahiye.

Fig. 11.123 aur 14 ko jodne ke do tareeke.NCERT p. 37

Left panel: das-das ki rows mein 23 blue dots aur unke neeche 14 orange dots. Right panel: columns mein 23 ke neeche 14 likha hai. Pehle step mein sirf dots aur column sum rakhe gaye hain. Doosre step mein har dot gina jaata hai, aur ek label batata hai ki ismein 37 counts lagte hain. Teesre step mein column method units column mein 3 + 4 = 7 aur tens column mein 2 + 1 = 3 nikaalta hai, aur sirf do chhote additions se 37 milta hai.

11.1.1 Digit by Digit Numbers Jodna

Column addition ka apna ek naam hona chahiye: yeh ek algorithm (कलन-विधि) hai. Ise algorithm chaalaaki nahi, balki do aur qualities banati hain. Yeh general hai: wahi instructions 23 + 14 aur 586 + 749 dono ko ek jaise handle karte hain. Aur yeh exact hai: kisi instruction mein apni samajh ya swaad lagaane ki zaroorat nahi.

Definition
Algorithm

Exact steps ki ek finite list jo order mein follow karne par kisi diye gaye type ki har problem solve kar deti hai.

ExampleColumn addition kinhi bhi do whole numbers ko jodne ka ek algorithm hai.

Chalo instructions itne dhyaan se likhte hain ki jisne kabhi column addition nahi dekha, ya koi machine, bhi unhe follow kar sake. Is result ko hum ADD kehte hain. carry word ek aise number ka naam hai jiska hum kaam karte waqt hisaab rakhte hain; jaldi hi dikhega ki yeh hamesha 0 ya 1 kyun hota hai.

Jab hum do khaas numbers ke liye ADD ke steps follow karte hain, to kehte hain ki hum use execute (ya run) kar rahe hain. Fig. 11.2 586 + 749 par ADD execute karta hai. Step 2 ek baar mein ek column handle karta hai, aur Step 3 humein ek-ek column left bhejta rehta hai jab tak koi column nahi bachta.

5/5Koi column nahi bacha aur carry 1 hai, isliye sabse left mein 1 likho: 1335.

Fig. 11.2586+749 par ADD execute kiya gaya. Har column ek basic step hai.NCERT Do numbers jodne ka algorithm · p. 37

586 aur 749 columns mein likhe hain aur ek shaded box current column dikhata hai. Step 1: numbers line up kiye gaye hain aur carry 0 hai. Step 2: units column mein 6 + 9 + 0 = 15, isliye 5 likha jaata hai aur tens column ke upar 1 ka carry aata hai. Step 3: tens column mein 8 + 4 + 1 = 13, isliye 3 likha jaata hai aur hundreds ke upar 1 ka carry aata hai. Step 4: hundreds column mein 5 + 7 + 1 = 13, isliye 3 likha jaata hai, carry 1. Step 5: koi column nahi bacha, isliye carry 1 sabse left mein likha jaata hai, aur 1335 milta hai.

ExampleNCERT 11.1.1 · p. 38

ADD ko column by column execute karna

7058 + 2967 par ADD execute karo. Har column ke liye total s, likha gaya digit aur carry ki nayi value dikhao.

Pehle khud try karo. Phir solution ek-ek step karke kholo.

ADD kabhi nahi batata ki 8 + 7 kaise nikaalein. Woh bas bharosa karta hai ki tumhe single-digit sums yaad hain, jaise koi recipe bharosa karti hai ki tumhe paani ubaalna aata hai. Jin actions ko algorithm bina samjhaye use karta hai, woh uske basic steps hain. ADD ke liye ek column ek basic step hai: do digits aur ek carry jodo, ek digit likho, carry update karo. Har algorithm ko kahin na kahin samjhaana rokna padta hai, aur uske basic steps wahi point dikhate hain.

Practice · 7 questions

Practice 11.1: answers ke saath

  1. Short answerEasyNCERT Exercise Set 11.1, Q1

    Aisi machine bano jo Algorithm ADD ke alawa kuch nahi jaanti. 6847 aur 5976 jodo, har column ke liye s aur carry likhte jao. Phir subtraction se apna answer check karo.

    Solution dikhao

    Answer12823

    1. Units: 7+6+0=13, 3 likho, carry 1.
    2. Tens: 4+7+1=12, 2 likho, carry 1.
    3. Hundreds: 8+9+1=18, 8 likho, carry 1.
    4. Thousands: 6+5+1=12, 2 likho, carry 1.
    5. Koi column nahi bacha aur carry 1 hai: sabse left mein 1 likho.

    Result 12823 sahi hai; ise 12823−5976=6847 se check kar sakte ho.

  2. Short answerMediumNCERT Exercise Set 11.1, Q2

    Ab 40382 + 976 par ADD try karo, jahan numbers ki lengths alag hain.

    1. Thousands column mein upar 0 hai aur uske neeche koi digit hai hi nahi. Shabd-shabd follow karein, to kya wahan Step 2 kiya ja sakta hai?

      Solution dikhao

      AnswerNahi: Step 2 ko do digits chahiye.

      Step 2 kehta hai “current column ke dono digits jodo”. Yahan sirf ek digit hai, isliye jo reader words ko bilkul waise hi follow karta hai, woh atak jaata hai. Algorithm, jaisa likha hai, sirf barabar length wale numbers handle karta hai.

    2. Step 1 ko aise badlo ki ADD alag-alag length ke numbers handle kar sake. Phir sum nikaalo.

      Solution dikhao

      Answer41358

      Step 1 mein jodo: “Agar ek number mein kam digits hain, to uski left ki khaali jagahon mein 0 likho.” To 976 ban jaata hai 00976, jiski value same hai.

      1. Units: 2+6=8, carry 0.
      2. Tens: 8+7=15, 5 likho, carry 1.
      3. Hundreds: 3+9+1=13, 3 likho, carry 1.
      4. Thousands: 0+0+1=1, carry 0.
      5. Ten-thousands: 4+0+0=4. Sum 41358 hai.
  3. Short answerEasyNCERT Exercise Set 11.1, Q3

    Riya 352 ke neeche 41 likhti hai, pehle digits ek line mein, yaani 3 ke neeche 4 aur 5 ke neeche 1, aur phir ADD chalaati hai. Use kya answer milta hai, aur galti kahan hui?

    Solution dikhao

    Answer762; sahi sum 393 hai.

    Har column mein same place value ke digits hone chahiye, taaki ones ke saath ones aur tens ke saath tens jude. Left se line up karne par 41 ka 4 hundreds column mein aur 1 tens column mein baith jaata hai. Tab ADD asal mein 410 jodta hai, aur 352+41=393 ki jagah 352+410=762 deta hai.

  4. Short answerMediumNCERT Exercise Set 11.1, Q4

    Kya ADD ko kabhi 2 ka carry chahiye ho sakta hai? Kisi bhi column ka sabse bada possible total nikaalo, aur usse decide karo.

    Solution dikhao

    AnswerHar total zyada se zyada 19 hai.

    Units column mein carry 0 hai, isliye s≤9+9+0=18 aur naya carry zyada se zyada 1 hai.

    Agar kisi column mein aane wala carry zyada se zyada 1 hai, to s≤9+9+1=19. Yeh 20 se kam hai, isliye s−10≤9 ek single digit hai aur naya carry phir se zyada se zyada 1 hai. Column dar column, carry 0 ya 1 hi rehta hai.

  5. Short answerMediumNCERT Exercise Set 11.1, Q5

    Printing ki ek galti se ADD ka Step 4 mit jaata hai.

    1. Aisa sum do jiske liye ADD phir bhi sahi answer deta hai.

      Solution dikhao

      AnswerJaise 314 + 452.

      314 + 452 mein hundreds column 3+4=7 deta hai aur carry 0 hai, isliye kuch nahi chhootta: answer 766 sahi hai.

    2. Aisa sum do jiske liye yeh fail hota hai, aur jo galat answer yeh deta hai woh bhi batao.

      Solution dikhao

      AnswerJaise 814 + 452 se 266 aata hai.

      814 + 452 mein hundreds column 8+4=12 deta hai: 2 likho, carry 1. Step 4 ke bina woh 1 kabhi likha hi nahi jaata, isliye result 1266 ki jagah 266 padha jaata hai.

    3. Step 4 ki zaroorat theek kab padti hai?

      Solution dikhao

      AnswerJab sabse left wale column ka total 10 ya usse zyada ho.

      Step 4 kuch likhta tabhi hai jab sabse left wale column ke baad carry 1 ho, yaani jab us column ka total 10 ya usse zyada ho.

  6. Quick answerEasy

    ADD mein ek column ka total s=10 hai. Kya hota hai?

    Answer dekho

    Answer (A) 0 likho aur carry ko 1 set karo

    10, “10 ya usse zyada” mein aata hai, isliye hum 10−10=0 likhte hain aur 1 carry karte hain. Agar rule “10 se zyada” kehta, to yeh case chhoot jaata; isiliye exact wording zaroori hai.
  7. Quick answerMedium

    Do 6-digit numbers jodte waqt ADD ka Step 2 kitni baar chalta hai?

    Answer dekho

    Answer 6

    Step 2 har column ke liye ek baar chalta hai. Step 4 ek saatvaan digit jod sakta hai, lekin woh Step 2 dobara nahi chalata.

Column method itna zyada tez kyun hai

Dono methods same answer dete hain, isliye asli sawaal yeh hai ki har ek mein kitna kaam lagta hai. Har number mein ek digit badha do, to numbers lagbhag das guna bade ho jaate hain, aur dots ka dher bhi. ADD mein bas ek extra column judta hai.

Chalo ispar mote-mote time lagaate hain. Maan lo tum ek second mein 2 dots gin sakte ho, aur ADD ke har column par dhyaan se 10 seconds lagaate ho. Table 11.1 numbers badhne ke saath dono methods ko compare karta hai.

Table 11.1Har extra digit par counting ka time lagbhag das guna badhta hai; ADD ka time bas ek column badhta hai (ek second mein 2 dots, ek column mein 10 s).
SumGinne wale dotsCounting se timeColumnsADD se time
48 + 368442 s220 s
486 + 365851lagbhag 7 min330 s
4862 + 36578519lagbhag 71 min440 s
48620 + 3657185191lagbhag 12 ghante550 s

Table ko uske columns mein neeche ki taraf padho. Counting ke times ek minute se kam se aadhe din tak phat padte hain, jabki ADD ke times har row mein bas 10 seconds dheere-dheere badhte hain. Achhe algorithm ki poori baat yahi hai: numbers bade hone par bhi uska kaam kam hi rehta hai. Ab se hum har algorithm ko isi tarah judge karenge, yeh poochh kar ki input badhne par uska kaam kaise badhta hai.

Column method sahi answer kyun deta hai

Agar answer galat ho to speed bekaar hai, isliye humein yeh reason bhi dena hai ki ADD hamesha counting se match kyun karta hai. 47 ko das cubes ki 4 rods aur 7 loose cubes socho, aur 38 ko 3 rods aur 8 loose cubes, jaisa Fig. 11.3 mein hai. Sab kuch ek dher mein ulat kar ginne se sahi total milta hai; 47 + 38 ka matlab yahi hai. ADD pehle loose cubes aur baad mein rods gin kar wahi total paata hai.

4/44+3+1=8 tens aur 5 ones: sum 85 hai.

Fig. 11.3Carry das ones ka ek bundle hai jo ek ten ban jaata hai.NCERT p. 39

Rods tens dikhati hain aur chhote cubes ones. Pehle step mein 47 ko 4 rods aur 7 cubes, aur 38 ko 3 rods aur 8 cubes ki tarah dikhaya gaya hai. Doosre step mein ones ek saath gine jaate hain: 7 + 8 = 15 cubes. Teesre step mein das cubes ek nayi rod mein bundle kiye jaate hain, yahi carry hai, aur 5 cubes bachte hain. Chauthe step mein rods gini jaati hain, 4 + 3 + 1 = 8 tens, isliye total 8 tens aur 5 ones hai, yaani 85.

Saat loose cubes aur aath loose cubes milkar pandrah bante hain: itne ki unmein se das ko jodkar ek nayi rod ban jaaye, aur paanch loose bach jaayein. Woh rod jodna hi exactly woh hai jo carry record karta hai. Ek hundred das rods ka bundle hai, isliye yahi jodna ek column aur left mein bhi ho sakta hai. Cubes ko group karne se koi cube na judta hai na hatta hai, isliye aakhir mein jo rods aur loose cubes bachte hain, woh exactly utne hi cubes ginte hain jitne se hum shuru hue the.

Quick check
4 mein se 1
Inmein se kaun algorithm ko sabse achhe se describe karta hai?
Answer dekho

Answer (D) exact steps jo ek type ki har problem solve karte hain

ADD jaisa algorithm whole numbers ke har pair ke liye kaam karta hai, aur har step exact hota hai. Computers aane se bahut pehle se log haath se algorithms execute karte aaye hain.

11.2 Greatest Common Divisor

Ab ek doosri jaani-pehchaani problem. Ek tailor ke paas do ribbons hain, 84 cm aur 126 cm lambe. Woh dono ko ek barabar length ke pieces mein kaatna chahti hai, bina kuch bache. Sabse lamba piece kitna kaat sakti hai? Length ko 84 aur 126 dono ko divide karna chahiye, aur humein aisa sabse bada number chahiye. Yeh 84 aur 126 ka greatest common divisor hai, jise gcd⁡(84,126) likhte hain. Tum ise highest common factor, yaani HCF (महत्तम समापवर्तक) ke naam se jaante hoge.

Definition
Greatest common divisor (gcd)

Sabse bada whole number jo diye gaye do numbers mein se har ek ko exactly divide karta hai. Ise highest common factor (HCF) bhi kehte hain.

Examplegcd⁡(12,18)=6: 6 dono numbers ko divide karta hai, aur koi bada number nahi karta.

Tum ise pichhli classes ki tarah prime factorisation se nikaal sakte ho. Uski jagah, chalo maan lete hain ki hum greatest common divisor words ke matlab ke alawa kuch nahi jaante, aur seedhe unhi se ek algorithm banate hain. Naam ko peeche se padho. Divisor: woh numbers dhoondho jo divide karte hain. Common: woh rakho jo dono numbers mein hain. Greatest: sabse bada chuno. Do numbers m aur n ke liye isse teen hisson wala plan banta hai.

  1. m ke saare divisors nikaalo aur likh lo.
  2. n ke saare divisors nikaalo aur likh lo.
  3. Dono collections compare karo aur woh sabse bada number chuno jo dono mein aata hai.

Har hissa poori problem se chhota kaam hai, aur chhote kaamon ko exact steps mein badalna aasaan hota hai. Hum inhe ek-ek karke lete hain.

11.2.1 Kisi Number ke Divisors Nikaalna

n ka divisor (भाजक) woh whole number hai jo n ko remainder 0 ke saath divide karta hai. Saare divisors dhoondhna roll call lene jaisa hai. 1, 2, 3, aur aise hi n tak naam pukaaro, aur jo bhi number n ko exactly divide karta hai, woh “present” bolta hai. n ke aage koi answer nahi de sakta, kyunki n ka divisor kabhi n se bada nahi hota.

Answers kahin likhne padenge. Hum ek list use karte hain: square brackets ke andar values ki ek ordered row, jaise [2,5,9]. Roll call shuru hone se pehle kisi ne answer nahi diya, isliye list khaali shuru hoti hai, jise [  ] likhte hain. Har naya answer append kiya jaata hai, yaani end mein likha jaata hai.

Step 2 ko letter j ke bina zor se padh kar dekho: “1 se n tak har number ke liye, agar woh number n ko divide karta hai, to woh number append karo…”. Jaldi hi sab uljha-uljha lagta hai. j aur found jaise chhote labels steps ko saaf rakhte hain. Kisi aisi value ka label jo algorithm chalte waqt badalti rehti hai, variable kehlaata hai. Step 2 do nayi features bhi dikhata hai: ek step repeated ho sakta hai (har j ke liye ek baar), aur woh conditional ho sakta hai (j ko tabhi append karo jab woh n ko divide kare).

5/5Sirf 20 khud pass hota hai. List poori ho gayi.

Fig. 11.4DIVISORS(20): har candidate test hota hai; divisors badhte order mein found mein judte hain.NCERT p. 40

Numbers 1 se 20 boxes ki do rows mein hain, ek pointer j ki current value dikhata hai, aur list found neeche likhi hai. Step 1: found khaali list hai. Step 2: j = 1 aur j = 2 dono 20 ko divide karte hain, isliye found [1, 2] ban jaati hai. Step 3: j = 3 fail hota hai jabki 4 aur 5, 20 ko divide karte hain, aur [1, 2, 4, 5] milta hai. Step 4: 6 se 10 mein sirf 10, 20 ko divide karta hai. Step 5: 11 se 20 mein sirf 20, 20 ko divide karta hai, isliye final list [1, 2, 4, 5, 10, 20] hai.

Poori list [1,2,4,5,10,20] badhte order mein aati hai. Yeh sanyog nahi hai: roll call upar ki taraf chalta hai, isliye har divisor apne se chhote sabhi divisors ke baad list mein judta hai. Yeh baat yaad rakho, kyunki hum ise jaldi use karenge. Yahan basic step ek divisibility test hai, jise hum aisi cheez maante hain jo hum hamesha kar sakte hain, jaise long division se.

ExampleNCERT 11.2.1 · p. 41

63 ke divisors

DIVISORS(63) execute karo. Yeh kitne tests karta hai, aur kitne divisors dhoondhta hai?

Pehle khud try karo. Phir solution ek-ek step karke kholo.

11.2.2 Greatest Common Divisor Nikaalna

Table par do lists hain. Kaun sa number dono mein hai, aur sabse bada hai? 36 aur 60 ke liye answer, 12, lagbhag uchhal kar saamne aata hai, jaisa Fig. 11.5 dikhata hai. 1680 aur 2520 ke liye, jinke 40 aur 48 divisors hain, kuch bhi saamne nahi aata, aur thaki aankh aasaani se koi match chhod deti hai. (Inka gcd 840 hai; chapter mein aage ek kahin tez method ise do divisions mein nikaal leta hai.)

To hum comparison ek aur chhote algorithm ko saunp dete hain. Socho ek dukaandaar delivery check kar rahi hai: woh apni order list upar se neeche padhti hai aur har us item par tick lagaati hai jo delivery note par bhi hai. Isi tarah hum pehli divisor list left se right padhte hain aur har woh entry jo doosri list mein bhi hai, ek nayi list common mein copy karte hain. Kyunki 1 sabko divide karta hai, common mein kam se kam ek entry hamesha aati hai.

Ab ek achha surprise. Dono divisor lists sorted thi, aur humne pehli list left se right padhi, isliye common bhi sorted hai. Uski sabse badi entry right wale end par baithi hai. Isliye gcd bas common ki last entry hai, aur aage koi search nahi chahiye.

4/4common ki last entry sabse badi hai: gcd⁡(36,60)=12.

Fig. 11.5Common divisors ki list badhte order mein hai, isliye uski last entry gcd hai.NCERT p. 42

Boxes ki do rows 36 ke divisors (nau boxes) aur 60 ke divisors (baarah boxes) dikhati hain. Step 1 sirf dono lists dikhata hai. Step 2 pehli list ki woh entries highlight karta hai jo doosri mein bhi hain aur har ek ko uske match se jodta hai: 1, 2, 3, 4, 6 aur 12. Step 3 unhe order mein common naam ki teesri row mein copy karta hai. Step 4 common ke last box, 12, par gola lagata hai aur use 36 aur 60 ka gcd likhta hai.

11.2.3 gcd ke liye Pehla Algorithm

Teeno hisson ko jod do, aur humare paas ek poora gcd algorithm hai. Dhyaan do ki yeh DIVISORS ke instructions dohraata nahi. Yeh bas DIVISORS ko do baar bulaata hai, jaise biryani ki recipe kahe “chawal paka lo” bina bataye ki kaise. Ek bharosemand algorithm ko ek bade algorithm ke andar dobara use karna mathematics aur computing ki sabse kaam ki aadaton mein se ek hai.

ExampleNCERT 11.2.3 · p. 43

Tailor ke ribbons

GCD-LIST use karke woh sabse lambe barabar pieces nikaalo jo 84 cm aur 126 cm ke ribbons se bina kuch bache kaate ja sakte hain.

Pehle khud try karo. Phir solution ek-ek step karke kholo.

Quick check
4 mein se 1
DIVISORS(n) 1 se n tak har j test karta hai. Iski output list badhte order mein kyun hoti hai?
Answer dekho

Answer (B) yeh candidates ko sabse chhote se sabse bade tak test karta hai

Har divisor milte hi append ho jaata hai, aur candidates badhte order mein try kiye jaate hain. Koi alag sorting step nahi hai, aur 36 dikhata hai ki divisors ki ginti odd bhi ho sakti hai.

11.3 Data Structures

Lambi doori ki train ke ticket checker ke baare mein socho. Uska reservation chart coach-wise aur berth-wise print hota hai, isliye woh kisi bhi passenger ko seconds mein dhoondh leti hai. Agar naam us order mein print hote jismein tickets book hue the, to wahi information dhoondhne mein use kahin zyada mehnat lagti. Information kaise arrange hai, yahi decide karta hai ki hum use kitni jaldi use kar sakte hain.

Algorithms ke saath bhi yahi issue hai. GCD-LIST kuch working values rakhta hai jo khud answer nahi hain: lists A, B aur common. Har ek numbers ka poora collection hai, badhte order mein rakha hua. Working values ki aisi kisi bhi arrangement ko data structure kehte hain, aur sorted list sabse simple data structures mein se ek hai. Iske sorted hone ka fayda aakhir mein mila, jab gcd seedhe common ke right wale end se padha ja saka.

Har working value ko chhota naam dene se, jaise humne A, B aur common ke saath kiya, steps padhne mein aasaan rehte hain. Tumhare phone ki contact list bhi ek data structure hai jo tum roz use karte ho: naam ke hisaab se sorted hone ki wajah se tum har entry padhe bina kisi dost ko dhoondh lete ho. Badi classes mein aur bahut saare data structures padhte hain.

Definition
Data structure

Kisi algorithm ki values ko organise karne ka tareeka, jaise badhte order mein rakhi list, taaki uske steps unhe aasaani se use kar sakein.

ExampleKyunki common sorted hai, GCD-LIST gcd ko uski last entry ki tarah padh leta hai.

Practice · 3 questions

Practice 11.2: answers ke saath

  1. Short answerMediumNCERT Exercise Set 11.2, Q1

    Ek class teacher roll numbers ki do lists rakhti hain, dono badhte order mein: P un students ki jinhone Monday ko homework jama kiya, aur Q Tuesday walon ki.

    1. Ek algorithm likho jo woh roll numbers de jo P mein hain lekin Q mein nahi.

      Solution dikhao
      1. Ek khaali list onlyP banao.
      2. P ki har value x ke liye, left se right: agar x, Q mein nahi hai, to x ko onlyP mein append karo.
      3. onlyP report karo.

    2. Ise P = [2, 5, 8, 11, 14] aur Q = [1, 5, 9, 14, 20] ke liye execute karo.

      Solution dikhao

      Answer[2, 8, 11]

      2, Q mein nahi hai (append), 5 hai (skip), 8 nahi hai (append), 11 nahi hai (append), 14 hai (skip). Result: [2, 8, 11].

    3. Kisne sirf Tuesday ko jama kiya? Apna algorithm badlo aur unhi lists par chalao.

      Solution dikhao

      AnswerP aur Q ke roles swap karo: [1, 9, 20].

      Ab Q par chalo aur check karo ki value P mein hai ya nahi. 1, 9 aur 20, P mein nahi hain, jabki 5 aur 14 hain, isliye result [1, 9, 20] hai.

    4. Dono lists sorted hain. Har x ke liye poori Q mein search karne se kaise bach sakte ho?

      Solution dikhao

      Har list mein ek pointer rakho aur jin do values par pointers hain unhe compare karo. Agar P wali value chhoti hai, to woh Q mein aage nahi aa sakti, isliye use append karo aur P mein aage badho. Agar dono barabar hain, to dono pointers aage badhao. Agar Q wali value chhoti hai, to Q mein aage badho. Jab Q khatam ho jaaye, to P ki baaki values append kar do. Har list sirf ek baar padhi jaati hai.

  2. Short answerMediumNCERT Exercise Set 11.2, Q2

    Do buses ek depot se saath-saath subah 6 baje nikalti hain, ek har 12 minute mein aur ek har 18 minute mein. Woh agli baar lcm⁡(12,18) minute baad saath nikalti hain, yaani woh sabse chhota whole number jise 12 aur 18 dono divide karte hain.

    1. Ek algorithm likho jo kinhi bhi do whole numbers ke liye lcm⁡(m,n) nikaale.

      Solution dikhao
      1. Maan lo m aur n mein bada L hai, aur chhota S.
      2. k=1,2,3,… ko baari-baari lo: agar S, k×L ko divide karta hai, to k×L report karo aur ruko.

      Yeh zaroor rukega, zyada se zyada k=S par, kyunki S, S×L ko divide karta hai.

    2. Ise buses ke liye execute karo. Woh agli baar saath kab nikalti hain?

      Solution dikhao

      Answer36 minute baad, subah 6:36 baje.

      L=18 aur S=12. k=1 ke liye: 12, 18 ko divide nahi karta. k=2 ke liye: 12, 36 ko divide karta hai. 36 report karo, yaani buses agli baar 36 minute baad, subah 6:36 baje saath nikalti hain.

  3. Short answerHardNCERT Exercise Set 11.2, Q3

    Jab 36 ko do whole numbers ke product ki tarah likhte hain, to uske divisors do-do karke saamne aate hain: 1×36, 2×18, 3×12, 4×9 aur 6×6.

    1. Maan lo DIVISORS jab bhi kisi pair ka chhota number dhoondhta hai, to pair ke dono numbers append kar deta hai. n=36 ke liye use kis j tak test karna padega? General n ke liye?

      Solution dikhao

      Answer6 tak; general mein, jab tak j×j≤n ho.

      Agar kisi pair ke dono numbers 6 se bade hote, to unka product 36 se bada hota. Isliye har pair ka chhota number zyada se zyada 6 hai, aur j=1 se 6 tak test karne se har pair mil jaata hai. General mein hum sirf woh j test karte hain jinke liye j×j≤n: n ki jagah lagbhag n values.

    2. Isse 36 ke liye list [1, 36, 2, 18, 3, 12, 4, 9, 6] milti hai. Kya is order wali lists ke saath bhi GCD-LIST kaam karega? Tum kya badloge?

      Solution dikhao

      AnswerHamesha nahi; sabse badi entry report karo.

      Lists ab sorted nahi hain, isliye common ki last entry ka sabse bada hona zaroori nahi. m=36 aur n=18 ke liye: A = [1, 36, 2, 18, 3, 12, 4, 9, 6] aur B = [1, 18, 2, 9, 3, 6], isliye common = [1, 2, 18, 3, 9, 6]. Iski last entry 6 hai, lekin gcd⁡(36,18)=18.

      Fix: Step 3 ko badlo taaki woh common ki sabse badi entry report kare (ya pehle lists ko sort karo).

11.3.1 Algorithm ko Behtar Banana

GCD-LIST sahi hai, lekin bahut kaam bekaar karta hai. Ek achhi aadat hai algorithm ko dekh kar poochhna: kaun sa kaam answer ko kabhi badal hi nahi sakta? Har baar aisi barbaadi dikhe, hum use hata sakte hain. Table 11.2 m=36 aur n=60 ke liye trimming ke chaar rounds record karta hai. Yeh har version ko score karta hai: kitne candidates dekhe aur memory mein kitni values rakhi.

Table 11.2m=36 aur n=60 ke liye GCD-LIST ko trim karna: dekhe gaye candidates aur memory mein rakhi values.
VersionKya badlaDekheRakhe
1. GCD-LISTDo alag scans, phir lists compare hoti hain9627
2. Ek scanBade number tak har j ko m aur n dono ke against test kiya jaata hai6027
3. Sirf common listj seedha common mein jaata hai; A aur B kabhi bante hi nahi606
4. Min par rukoScan chhote number par ruk jaata hai, kyunki usse bada koi number use divide nahi kar sakta366
5. GCD-SCANSirf latest common divisor, best, rakha jaata hai361

Aakhri change ko dhyaan se dekhna chahiye. Scan upar ki taraf chadhta hai, isliye jo bhi common divisor milta hai woh pichhle sabhi divisors se bada hota hai, aur purane wale bas bojh hain. Ek variable, best, kaafi hai. Yeh 1 se shuru hota hai, jo har number ko divide karta hai, aur jab bhi koi bada common divisor milta hai, overwrite ho jaata hai. Fig. 11.6 ghatte kaam ko bars ki tarah dikhata hai.

5/5Abhi bhi 36 candidates, aur sirf ek number, best, store hota hai.

Fig. 11.6Har refinement kam candidates dekhta hai ya kam store karta hai (m=36, n=60).NCERT p. 44

Paanch labelled bars, m = 36 aur n = 60 ke liye algorithm ke har version ka ek, ek-ek karke aate hain. Step 1: do alag scans wala GCD-LIST 96 candidates dekhta hai. Step 2: bade number tak ek scan 60 dekhta hai. Step 3: common list seedhe banana abhi bhi 60 dekhta hai lekin kam numbers store karta hai. Step 4: chhote number par rukne se yeh 36 reh jaata hai. Step 5: ab tak ka sirf best divisor rakhna abhi bhi 36 candidates dekhta hai lekin sirf ek number store karta hai.

Practice · 2 questions

Practice 11.3: answers ke saath

  1. Short answerMediumNCERT Exercise Set 11.3, Q1

    Ek dost DIVISORS ko aise dobara likhta hai ki j neeche ki taraf gine: n, n−1, …, 1.

    1. Yeh 20 ke divisors kis order mein list karega?

      Solution dikhao

      Answer[20, 10, 5, 4, 2, 1]

      Sabse bada divisor sabse pehle milta hai, isliye list ghatte order mein hai: [20, 10, 5, 4, 2, 1].

    2. GCD-LIST ka kaun sa step badalna padega, aur kaise?

      Solution dikhao

      AnswerStep 3: pehli entry report karo.

      Ab common ghatte order mein hai, isliye uski sabse badi entry pehli wali hai. Step 3 ko common ki sabse right wali ki jagah sabse left wali entry report karni hogi.

  2. Short answerMediumNCERT Exercise Set 11.3, Q2

    GCD-SCAN ka scan ulta chalao: k ko min⁡(m,n) se neeche 1 tak jaane do.

    1. Samjhao ki tum us pehle k par kyun ruk sakte ho jo dono numbers ko divide karta hai.

      Solution dikhao

      Usse upar ka har k pehle hi test hokar fail ho chuka hai. Isliye neeche jaate hue jo pehla common divisor milta hai, wahi sabse bada hai, yaani gcd. Usse neeche ka koi bhi use beat nahi kar sakta.

    2. m=48, n=80 ke liye backward scan k ki kitni values dekhta hai? Forward scan kitni dekhta hai?

      Solution dikhao

      AnswerBackward 33, forward 47.

      gcd⁡(48,80)=16. Backward, k 48, 47, …, 16 tak chalta hai aur ruk jaata hai: 48−16+1=33 values. Forward, k 2 se 48 tak chalta hai: 47 values.

    3. Kin pairs ke liye backward scan kuch nahi bachata?

      Solution dikhao

      AnswerJin pairs ka gcd 1 hai.

      Agar gcd⁡(m,n)=1, to 1 se upar koi k kaam nahi karta, isliye backward scan poora 1 tak neeche jaata hai, aur min⁡(m,n) se neeche ki har value dekhta hai.

11.3.2 In Algorithms ka Analysis

Ab humare paas ek hi algorithm ke paanch versions hain. Kya sab sahi hain, aur kya inmein se koi tez hai? Har algorithm ke baare mein yahi do sawaal poochhne chahiye.

Correctness. Versions ko ek chain ki kadiyan socho. Pehli kadi, GCD-LIST, par bharosa kiya ja sakta hai kyunki yeh gcd ki definition hi hai jise steps mein badla gaya hai. Har agli kadi pichhli se sirf itni alag hai ki woh aisa kaam hata deti hai jo result par asar nahi daal sakta tha: aise candidates jo dono numbers ko divide karne ke liye bahut bade hain, ya aisi lists jo dobara kabhi padhi nahi gayi. Aisi kadiyon ki chain nahi tootti, isliye aakhir ka GCD-SCAN utna hi sahi hai jitna shuru ka GCD-LIST.

ExampleNCERT Example · p. 45

GCD-SCAN execute karna

m=20 aur n=8 ke liye GCD-SCAN execute karo. Har k ke baad best ki value dikhao.

Pehle khud try karo. Phir solution ek-ek step karke kholo.

Efficiency. Speed alag baat hai. GCD-SCAN ab bhi chhote number tak har candidate par jaata hai. Ise 9-digit numbers ka ek pair do, to yeh karodon candidates dekh sakta hai; computer to sambhaal leta hai, lekin pencil aur kaagaz wala insaan kabhi nahi. Table 11.1 ki bhasha mein, GCD-SCAN dots ginne jaisa behave karta hai, ADD jaisa nahi. Isse ek challenge khada hota hai: kya koi aisa gcd algorithm hai jiska kaam numbers ke size ki jagah unki length ke hisaab se chale?

Quick check
4 mein se 1
m=150 aur n=84 ke liye GCD-SCAN k ki kitni values dekhta hai?
Answer dekho

Answer 83

k 2 se min⁡(150,84)=84 tak chalta hai, yaani 84−2+1=83 values.

11.3.3 Euclid ka Subtraction Algorithm

Iska answer 2300 saal se bhi purana hai. Lagbhag 300 BCE mein, Alexandria ke Euclid ne apne zamaane ki mathematics ko Elements mein ikattha kiya, ek aisi kitaab jo do hazaar saal se zyada padhi gayi. Yeh method uski Book VII ki shuruaat ke paas aata hai. Shayad yeh unka apna invention nahi tha, kyunki lagta hai pehle ke Greek mathematicians bhi ise use karte the, lekin humare tak unka hi likha hua account pahuncha hai.

Problem ko chhota karna

Pehle ek chhota sa experiment karo. 30 aur 18 ke common divisors 1, 2, 3 aur 6 hain. Ab 30 ko 30−18=12 se badal do: 18 aur 12 ke common divisors phir se 1, 2, 3 aur 6 hain. Na kuch khoya, na kuch mila, phir bhi numbers chhote ho gaye. Euclid ka idea yeh hai ki aisa hamesha hota hai.

PropertyEuclid ka reduction

Agar m≥n, to gcd⁡(m,n)=gcd⁡(n,m−n).

Fig. 11.7 yeh idea number line par dikhata hai. Jo hop length exactly n aur m par girti hai, woh unke beech ka hissa, jiski length m−n hai, bhi poore hops mein cover karti hai. Euclid khud bhi lengths ke saath kuch aise hi reasoning karte the.

3/3Hissa m−n=12 exactly do hops hai: 6, 12 ko divide karta hai.

Fig. 11.7Agar d length ke hops n aur m par girte hain, to woh m−n ko bhi poore hops mein cover karte hain.NCERT Fig. 11.1 · p. 46

Ek number line 0 se 30 tak hai, har 6 units par marks hain. Step 1: 0 se d = 6 length ke teen hops exactly n = 18 par girte hain. Step 2: do aur hops exactly m = 30 par girte hain. Step 3: 18 se 30 tak ka hissa, jiski length m − n = 12 hai, highlight hota hai aur exactly do hops se cover hota hai, isliye 6, m − n ko bhi divide karta hai.

Har subtraction total m+n ko chhota karta hai, isliye yeh process hamesha nahi chal sakta: der-sawer chhota number 0 par pahunch jaata hai. gcd⁡(m,0) kya hai? Har whole number d, 0 ko divide karta hai, kyunki 0=0×d. Isliye m aur 0 ke common divisors bas m ke divisors hain, aur inmein sabse bada m khud hai. Isliye gcd⁡(m,0)=m: jab 0 aa jaaye, to doosra number hi answer hai. Jaise, (9,9) ban jaata hai (9,0), aur answer 9 hai.

ExampleNCERT 11.3.3 · p. 47

Subtraction se Euclid

EUCLID-SUB se gcd⁡(91,35) nikaalo. Yeh kitne subtractions karta hai?

Pehle khud try karo. Phir solution ek-ek step karke kholo.

EUCLID-SUB ki ek pyaari si picture hai. m by n ka ek rectangle banao. Har subtraction end se n by n ka ek square kaat deta hai, aur ek chhota rectangle bachta hai jiski sides naya pair hain. Jab kisi cut ke baad kuch nahi bachta, to aakhri square ki side gcd hai. Fig. 11.8 42 by 24 ke rectangle ke liye yahi karta hai.

4/4Teen subtractions baaki hissa exactly khatam kar dete hain. Kul 5 cuts: gcd 6 hai.

Fig. 11.8Har subtraction ek square kaat deta hai; jo sabse chhota square exactly fit hota hai, uski side gcd⁡(42,24)=6 hai.NCERT p. 47

Ek rectangle jo 42 units chauda aur 24 units ooncha hai. Step 1 poora rectangle aur pair (42, 24) dikhata hai. Step 2 left mein 24 by 24 ka square kaat deta hai, aur 18 by 24 ki strip bachti hai: pair (24, 18). Step 3 strip se 18 by 18 ka square kaatta hai, aur 18 by 6 ka piece bachta hai: pair (18, 6). Step 4 piece ko 6 by 6 ke teen squares mein kaatta hai aur kuch nahi bachta, isliye gcd 6 hai.

EUCLID-SUB ek bada kadam hai, lekin ise ek bada aur ek chhota number do, to yeh reng-reng kar chalta hai. gcd⁡(1000,3) ke liye yeh ek baar mein 3 ghatata hai: (1000,3), (997,3), (994,3), … poora (3,1) tak, aur phir teen aur steps chahiye. Yeh 336 subtractions hain. 3 ke saath 7-digit number ko das lakh se zyada chahiye honge. Kaam ab bhi numbers ke size ke hisaab se chalta hai, unki length ke hisaab se nahi.

Quick check
4 mein se 1
Pairs ko us order mein rakho jismein EUCLID-SUB unhe (40,15) se shuru karke paata hai (pairs swap ke baad dikhaye gaye hain).
  1. (40,15)
  2. (25,15)
  3. (15,10)
  4. (5,0)
  5. (5,5)
  6. (10,5)
Answer dekho
Answer
  1. (40,15)
  2. (25,15)
  3. (15,10)
  4. (10,5)
  5. (5,5)
  6. (5,0)
40−15=25, 25−15=10, 15−10=5, 10−5=5, 5−5=0. Paanch subtractions, aur answer 5 hai.

11.3.4 Āryabhaṭa ka Division Algorithm

gcd⁡(1000,3) ko phir dekho. 1000 mein se 3 baar-baar, 333 baar ghatane par 1 bachta hai. Ek division yahi kaam ek jhatke mein kar deta hai: 1000=333×3+1. Bacha hua 1 remainder hai.

Indian mathematicians bilkul isi tarah kaam karte the. 499 CE mein poore hue Āryabhaṭīya mein Āryabhaṭa ek method describe karte hain, jise aaj kuṭṭaka (“the pulveriser”, yaani peesne wala) kehte hain, jo whole numbers mein kuch equations solve karta hai. Iska pehla stage do numbers ko baar-baar ek doosre se divide karta hai, har baar sirf remainder rakhta hai. Yahi repeated division gcd nikaalta hai, aur Indian place-value numerals ke saath yeh ek compact long-division method ban gaya.

Definition
m mod n

m mod n woh remainder hai jo m ko n se divide karne ke baad bachta hai. Yeh hamesha n se kam hota hai.

Example23 mod 4=3, kyunki 23=5×4+3; aur 50 mod 7=1.

Isse EUCLID-SUB ka ek one-line upgrade sujhta hai. Jahan bhi yeh m mein se n baar-baar ghatata, wahan ise ek baar divide karne do aur remainder rakhne do, taaki pair (m,n) seedha (n,m mod n) par kood jaaye. Neeche ka theorem dikhata hai ki is jump se gcd same rehta hai.

PropertyRemainder se reduction

Agar n>0, to gcd⁡(m,n)=gcd⁡(n,m mod n).

Ab Step 1 sirf bilkul shuru mein matter karta hai, kyunki remainder hamesha divisor se chhota hota hai. Slow case phir se chalao: gcd⁡(1000,3) ban jaata hai gcd⁡(3,1), phir gcd⁡(1,0), aur answer 1, 336 subtractions ki jagah 2 divisions ke baad aa jaata hai. Sach to yeh hai ki gcd⁡(m,3) ko kabhi 3 se zyada divisions nahi chahiye, m chahe kitna bhi bada ho.

Long-division layout

Haath se karne par EUCLID-DIV divisions ki ek chain hai. Har divisor agla divide hone wala number ban jaata hai, aur har remainder agla divisor. Chain remainder 0 par rukti hai, aur aakhri divisor, jo aakhri non-zero remainder hai, gcd hai. Indian texts ise compact tareeke se likhte the: har naya division pichhle wale ke thoda neeche aur right mein. Fig. 11.9 gcd⁡(1155,546) ke liye chain follow karta hai.

5/5Aakhri non-zero remainder gcd hai: gcd⁡(1155,546)=21.

Fig. 11.9Har divisor left jaata hai aur har remainder divisor ki jagah aata hai, jab tak remainder 0 na ho jaaye.NCERT Long division ka layout · p. 49

Ek table jiske columns divide, by, quotient aur remainder hain. Step 1: 1155 ko 546 se divide karne par quotient 2 aur remainder 63. Step 2: arrows 546 ko agli row ke divide column mein aur 63 ko by column mein le jaate hain: 546 ko 63 se divide karne par 8, remainder 42. Step 3: 63 ko 42 se divide karne par 1, remainder 21. Step 4: 42 ko 21 se divide karne par 2, remainder 0. Step 5: aakhri non-zero remainder, 21, par gcd ki tarah gola lagta hai.

Isi pair ko EUCLID-SUB mein 13 subtractions lagte hain, lekin yahan sirf 4 divisions.

ExampleNCERT 11.3.4 · p. 49

Division se Euclid

EUCLID-DIV se gcd⁡(2585,44) nikaalo, aur kaam ko EUCLID-SUB se compare karo.

Pehle khud try karo. Phir solution ek-ek step karke kholo.

InteractiveAlgorithm stepper

Ek algorithm stepper. Buttons is chapter ke paanch algorithms mein se ek chunte hain: ADD, DIVISORS, GCD-SCAN, EUCLID-SUB aur EUCLID-DIV. Number boxes mein tum apne inputs daal sakte ho. Step button ek basic step karta hai aur use ek numbered log mein likhta hai, Run to end algorithm poora kar deta hai (lambe runs ka summary dikhta hai), aur Reset phir se shuru karta hai. Ek panel current state dikhata hai: ADD ke liye columns, digits aur carry, DIVISORS ke liye j ki value aur list found, GCD-SCAN ke liye k aur best, aur dono Euclid algorithms ke liye current pair. Ek counter dikhata hai ki kitne basic steps use hue, aur gcd algorithms ke liye ek comparison line batati hai ki usi pair ke liye teeno gcd methods mein se har ek ko kitne steps chahiye.

Fig. 11.10Apne numbers ke saath ADD, DIVISORS, GCD-SCAN, EUCLID-SUB aur EUCLID-DIV ko step by step chalao, aur compare karo ki har ek mein kitne steps lagte hain.NCERT p. 49

General mein EUCLID-DIV itna tez kyun hai? Remainder hamesha apne divisor se chhota hota hai. Thoda aur dhyaan dene par isse bhi strong baat dikhayi ja sakti hai: kinhi bhi do divisions ke baad pair ka bada number apni purani value ke aadhe se neeche aa jaata hai. Kisi number ka har digit lagbhag 313 baar aadha hone tak hi tikta hai, isliye divisions ki ginti digits ki ginti ke saath badhti hai. Poora proof aage ki class mein aayega; abhi ke liye is claim ko stepper mein test karo.

Quick check
4 mein se 1
47 mod 6=
Answer dekho

Answer 5

47=7×6+5, isliye remainder 5 hai.
Timeline

Samay ke saath algorithms

  1. c. 300 BCE

    Euclid’s Elements

    Baar-baar subtraction se gcd nikaala gaya.

  2. 499 CE

    Āryabhaṭa’s Āryabhaṭīya

    Kuṭṭaka method mein remainders ke saath repeated division.

  3. c. 820 CE

    al-Khwārizmī, Baghdad

    Indian numerals aur unse calculation karne par ek kitaab.

  4. 12th century

    Latin mein translation

    Indian arithmetic, jise algorismus kaha gaya, poore Europe mein phailti hai.

  5. 1844

    Gabriel Lamé

    Prove karte hain ki Euclid’s division algorithm ko kam steps chahiye.

Recap

Summary aur key points

  1. Algorithm exact steps ki ek finite list hai jo kisi diye gaye type ki har problem solve karti hai. Yeh basic steps se banta hai jo hum pehle se kar sakte hain (Section 11.1.1).
  2. ADD do numbers ko right se column by column jodta hai, ek carry ke saath jo hamesha 0 ya 1 hota hai (Algorithm ADD).
  3. ADD sahi hai kyunki yeh ones, tens aur hundreds ko alag-alag jodta hai; carry das ka ek bundle hai (ADD kyun kaam karta hai).
  4. Dots ginne mein har extra digit par lagbhag das guna zyada time lagta hai; ADD ko bas ek column zyada chahiye (ADD tez kyun hai).
  5. Steps repeat ho sakte hain (ADD har column ke liye Step 2 ek baar chalata hai) aur conditional ho sakte hain (GCD-SCAN best tabhi badalta hai jab k dono numbers ko divide kare) (Section 11.2.1).
  6. DIVISORS(n) 1 se n tak har candidate test karta hai aur divisors badhte order mein deta hai (Section 11.2.1).
  7. GCD-LIST dono lists ke common divisors rakhta hai; us sorted list ki last entry gcd hai (Section 11.2.3).
  8. Data structure, jaise sorted list, un values ko organise karta hai jinke saath algorithm kaam karta hai (Section 11.3).
  9. Ek baar scan karna, min⁡(m,n) par rukna aur sirf best rakhna kaam kam karte hain, lekin kaam ab bhi numbers ke size ke saath badhta hai (Section 11.3.1, Section 11.3.2).
  10. Euclid: m≥n ke liye gcd⁡(m,n)=gcd⁡(n,m−n), aur gcd⁡(m,0)=m (Section 11.3.3).
  11. Āryabhaṭa ka division method gcd⁡(n,m mod n) use karta hai; iske steps ki ginti sirf digits ki ginti ke saath badhti hai (Section 11.3.4).
  12. Har algorithm ke liye hum do sawaal poochhte hain: kya yeh correct hai, aur iska kaam input ke size ke saath kaise badhta hai (Section 11.3.2)?
  13. Algorithm word al-Khwārizmī se aaya hai, jinki kitaab Indian arithmetic ko baaki duniya tak le gayi (history).
Practice · 10 questions

Practice questions answers ke saath (NCERT “Chapter ke end ki exercises”)

  1. NumericalMediumNCERT End-of-chapter Exercises Q1

    Har gcd EUCLID-DIV se nikaalo. Har division dikhao.

    1. gcd⁡(1365,1001)

      Solution dikhao

      Answer91

      Har row m ko n se divide karti hai; agli row n ko remainder se divide karti hai.

      mnremainderquotient
      136510013641
      10013642732
      364273911
      2739103

      Aakhri non-zero remainder 91 hai, isliye gcd 91 hai.

    2. gcd⁡(43200,75600)

      Solution dikhao

      Answer10800

      Step 1 numbers ko swap karta hai, kyunki 43200<75600.

      Har row m ko n se divide karti hai; agli row n ko remainder se divide karti hai.

      mnremainderquotient
      7560043200324001
      4320032400108001
      324001080003

      Aakhri non-zero remainder 10800 hai, isliye gcd 10800 hai.

    3. gcd⁡(5162157,956241)

      Solution dikhao

      Answer1287

      Har row m ko n se divide karti hai; agli row n ko remainder se divide karti hai.

      mnremainderquotient
      51621579562413809525
      9562413809521943372
      3809521943371866151
      19433718661577221
      1866157722128724
      7722128706

      Aakhri non-zero remainder 1287 hai, isliye gcd 1287 hai. 7-digit numbers ke liye chhah divisions kaafi the.

    4. gcd⁡(2114112,945945)

      Solution dikhao

      Answer3003

      Har row m ko n se divide karti hai; agli row n ko remainder se divide karti hai.

      mnremainderquotient
      21141129459452222222
      945945222222570574
      22222257057510513
      570575105160061
      51051600630038
      6006300302

      Aakhri non-zero remainder 3003 hai, isliye gcd 3003 hai.

  2. ProofMediumNCERT End-of-chapter Exercises Q2

    Maan lo m≥n>0, aur m=qn+r likho, jahan r=m mod n. Prove karo ki m aur n ke common divisors bilkul wahi hain jo n aur r ke common divisors hain.

    Solution dikhao

    m aur n ka har common divisor n aur r ka common divisor hai. Agar d, m aur n ko divide karta hai, to m=ad aur n=bd likho. Tab r=m−qn=ad−qbd=(a−qb)d, isliye d, r ko divide karta hai (aur n ko to pehle se karta hai).

    n aur r ka har common divisor m aur n ka common divisor hai. Agar d, n aur r ko divide karta hai, to n=bd aur r=cd likho. Tab m=qn+r=qbd+cd=(qb+c)d, isliye d, m (aur n) ko divide karta hai.

    Dono directions sahi hain, isliye dono pairs ke common divisors same hain. Isiliye EUCLID-DIV (m,n) ko (n,m mod n) se badal sakta hai.

  3. Long answerMediumNCERT End-of-chapter Exercises Q3

    Kya 221 prime hai? Kya 223 hai? Haath se check karna thakaane wala hai, isliye yeh kaam ek algorithm ko karne do.

    1. Ek algorithm PRIME(n) likho jo prime n ke liye “yes” aur baaki ke liye “no” report kare. (Prime ka 1 aur khud ke alawa koi divisor nahi hota.)

      Solution dikhao
      1. Maan lo D list DIVISORS(n) hai.
      2. Agar D mein exactly 2 entries hain, to “yes” report karo; warna “no” report karo.

      Yeh n=1 ko sahi handle karta hai: DIVISORS(1) = [1] mein ek hi entry hai, aur 1 prime nahi hai. 221 ke liye D = [1, 13, 17, 221], isliye answer “no” hai; 223 ke liye D = [1, 223], isliye “yes” hai.

    2. n=223 ke liye tumhara algorithm kitne tests karta hai? Ek tez version suggest karo.

      Solution dikhao

      Answer223 tests; jaise hi j×j>n ho, ruk jao.

      DIVISORS(223) 1 se 223 tak har j test karta hai: 223 tests.

      Tez version: j=2,3,… tab tak test karo jab tak j×j≤n ho, aur jo pehla j, n ko divide kare, wahin “no” report karo. Agar kisi number ka 1 aur khud ke alawa koi divisor hai, to uska ek aisa divisor hai jismein j×j≤n (Practice 11.2, Q3). 223 ke liye iska matlab j=2 se 14, sirf 13 tests, aur koi pass nahi hota, isliye 223 prime hai.

  4. Long answerHardNCERT End-of-chapter Exercises Q4

    84 ko divide karne wale primes 2, 3 aur 7 hain. Ek algorithm PRIME-DIVISORS(n) likho jo kisi bhi n ke liye aisi list de, DIVISORS aur PRIME ko building blocks ki tarah use karke. Phir ise n=90 ke liye execute karo.

    Solution dikhao

    Answer[2, 3, 5]

    1. Maan lo D list DIVISORS(n) hai, aur ek khaali list P banao.
    2. D ke har x ke liye: agar PRIME(x) “yes” report kare, to x ko P mein append karo.
    3. P report karo.

    90 ke liye D = [1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90]. Sirf 2, 3 aur 5 prime hain, isliye result [2, 3, 5] hai.

  5. Long answerHardNCERT End-of-chapter Exercises Q5

    Prime factors gcd tak pahunchne ka ek aur raasta dete hain.

    1. 360=23×32×5. Prime factorisation ko list ki tarah store karne ka ek tareeka suggest karo.

      Solution dikhao

      Answer[(2, 3), (3, 2), (5, 1)]

      Pairs (prime, power) ki list use karo, primes badhte order mein: [(2, 3), (3, 2), (5, 1)].

    2. Ek algorithm FACTORISE(n) describe karo jo yeh list banaye.

      Solution dikhao
      1. Ek khaali list F banao, aur p ko 2 set karo.
      2. Jab tak n>1: gino ki p, n ko kitni baar divide karta hai, har baar n ko p se divide karte hue. Agar count 0 se zyada hai, to (p,count) ko F mein append karo. Phir p ko 1 badhao.
      3. F report karo.

      Koi non-prime p bache hue number ko kabhi divide nahi karta, kyunki uske prime factors pehle hi divide karke nikaal diye gaye hain.

    3. 360 aur 756=22×33×7 ki lists use karke unka gcd nikaalo. Apna rule batao.

      Solution dikhao

      Answer36

      Rule: jo prime dono lists mein hai, uski chhoti power lo; jo prime sirf ek list mein hai, use chhod do. [(2, 3), (3, 2), (5, 1)] aur [(2, 2), (3, 3), (7, 1)] se humein 22×32=36 milta hai. EUCLID-DIV se check karo: 756=2×360+36 aur 360=10×36.

  6. Short answerMedium

    Ek dukaan ke paas 1428 red beads aur 1092 blue beads hain. Woh ek jaise gift packets banana chahti hai, har packet mein red aur blue beads ki same ginti ho, aur har bead use ho jaaye. Woh zyada se zyada kitne packets bana sakti hai, aur har ek mein kya hoga?

    Solution dikhao

    Answer84 packets, har ek mein 17 red aur 13 blue.

    mnremainderquotient
    142810923361
    1092336843
    3368404

    To gcd⁡(1428,1092)=84 packets. Har packet mein 1428÷84=17 red aur 1092÷84=13 blue beads hain.

  7. Quick answerMedium

    Kaun sa pair EUCLID-SUB se sabse zyada subtractions karwaata hai?

    Answer dekho

    Answer (D) (100,3)

    Counts 2, 4, 6 aur 36 hain. 100 se sirf 3 ghatate hue 1 tak pahunchne mein hi 33 steps lagte hain.
  8. Quick answerEasy

    Algorithm ke baare mein kaun sa statement false hai?

    Answer dekho

    Answer (B) yeh same input par alag-alag answers de sakta hai

    Order mein follow kiye gaye exact steps same input par hamesha same result dete hain.
  9. Quick answerEasy

    Har whole number m>0 ke liye, gcd⁡(m,0)= .

    Answer dekho

    Answer m

    Har number 0 ko divide karta hai, isliye common divisors m ke divisors hain, aur sabse bada m hai.
  10. Quick answerMedium

    Agar gcd⁡(m,n)=1, to Practice 11.3, Q2 ka backward scan min⁡(m,n) se neeche 1 tak har value dekhta hai.

    Answer dekho

    Answer Sahi

    1 se upar koi value dono numbers ko divide nahi karti, isliye scan tabhi rukta hai jab woh 1 tak pahunchta hai.

Apna NCERT exercise question dhoondo

Hamare practice questions ncert.ai ke liye likhe gaye hain aur NCERT exercises ko follow karte hain. Apni textbook ke question se match karne wala question dhoondo; uska answer uske saath hai.

Tumhari NCERT textbook meinYahan practice question
NCERT Exercise Set 11.1, Q1Practice 11.1 · Q1
NCERT Exercise Set 11.1, Q2Practice 11.1 · Q2
NCERT Exercise Set 11.1, Q3Practice 11.1 · Q3
NCERT Exercise Set 11.1, Q4Practice 11.1 · Q4
NCERT Exercise Set 11.1, Q5Practice 11.1 · Q5
NCERT Exercise Set 11.2, Q1Practice 11.2 · Q1
NCERT Exercise Set 11.2, Q2Practice 11.2 · Q2
NCERT Exercise Set 11.2, Q3Practice 11.2 · Q3
NCERT Exercise Set 11.3, Q1Practice 11.3 · Q1
NCERT Exercise Set 11.3, Q2Practice 11.3 · Q2
NCERT End-of-chapter Exercises Q1Chapter ke end ki exercises · Q1
NCERT End-of-chapter Exercises Q2Chapter ke end ki exercises · Q2
NCERT End-of-chapter Exercises Q3Chapter ke end ki exercises · Q3
NCERT End-of-chapter Exercises Q4Chapter ke end ki exercises · Q4
NCERT End-of-chapter Exercises Q5Chapter ke end ki exercises · Q5

Quick check: MCQs

  1. Column method sahi answer kyun deta hai4 questions
  2. 11.2.3 gcd ke liye Pehla Algorithm4 questions
  3. 11.3.2 In Algorithms ka Analysis4 questions
  4. Problem ko chhota karna4 questions
  5. Long-division layout4 questions
Glossary · 10

Key terms (English + Hindi)

algorithmकलन-विधिkalan-vidhi
Exact steps ki ek finite list jo order mein follow karne par kisi diye gaye type ki har problem solve karti hai.Chapter mein pehli baar yahan aaya →
basic stepमूल चरणmool charan
Aisa action jo algorithm bina samjhaye use karta hai, kyunki hum use pehle se kar sakte hain, jaise do digits jodna.Chapter mein pehli baar yahan aaya →
data structureडेटा संरचनाdata sanrachna
Algorithm jin values ke saath kaam karta hai unhe organise karne ka tareeka, jaise sorted list.Chapter mein pehli baar yahan aaya →
divisorभाजकbhajak
Woh whole number jo diye gaye number ko remainder 0 ke saath divide karta hai.Chapter mein pehli baar yahan aaya →
efficiencyदक्षताdakshata
Algorithm ko kitna kaam chahiye, yeh is baat se judge hota hai ki input ka size badhne par uske basic steps ki ginti kaise badhti hai.Chapter mein pehli baar yahan aaya →
executeनिष्पादित करनाnishpadit karna
Kisi khaas input ke liye algorithm ke steps ek-ek karke karna.Chapter mein pehli baar yahan aaya →
greatest common divisorमहत्तम समापवर्तकmahattam samapavartak
Sabse bada whole number jo diye gaye do numbers mein se har ek ko exactly divide karta hai.Chapter mein pehli baar yahan aaya →
listसूचीsoochi
Square brackets mein values ki ek ordered row, jaise [1,3,9]; nayi values end mein append hoti hain.Chapter mein pehli baar yahan aaya →
modशेषफलsheshphal
m mod n woh hai jo m mein se n ke jitne poore hisse nikal sakein, nikaalne ke baad bachta hai.
variableचरchar
Kisi aisi value ka naam jiska algorithm hisaab rakhta hai aur jo badal sakti hai, jaise carry ya best.Chapter mein pehli baar yahan aaya →

Tum chapter ke end tak pahunch gaye