Programming Lab

Variable भनेको नाम लेखिएको बाकस हो

Variable भनेको एउटा मान राख्ने नाम भएको बाकस हो; assignment ले दायाँपट्टिको हिसाब गरेर उत्तर बाकसमा राख्छ, पहिले भएको मान हटाउँछ, र प्रोग्रामले पछिल्लो मान प्रयोग गर्छ

Decimal बाट binary मा

कुनै सङ्ख्यालाई बारम्बार 2 ले भाग गर्दा आउने शेषहरू यसका binary अङ्क हुन्, अन्तिम bit देखि पहिलोसम्म; हरेक शेष एक स्थान बायाँ राखिन्छ

उल्टो लेखिएका शब्द: palindrome

String भनेको 0 बाट सुरु हुने index भएका character को सूची हो; loop ले हरेकलाई पालैपालो हेर्न सक्छ, र दुवै छेउबाट भित्र सर्ने दुई pointer ले आधा तुलनामा मात्र palindrome जाँच्छन्

बाहिर खेल्न पाइन्छ? AND, OR र NOT

NOT ले सत्यलाई असत्य बनाउँछ; AND दुवै भाग सत्य हुँदा मात्र सत्य हुन्छ; OR कम्तीमा एउटा भाग सत्य हुँदा सत्य हुन्छ, त्यसैले लामो condition लाई एक-एक भाग गरेर निकाल्न सकिन्छ

पानी परे छाता लैजाऊ

if / else ले एउटा condition जाँच्छ: त्यो सत्य भए प्रोग्रामले then भाग चलाउँछ, नत्र else भाग, दुवै कहिल्यै होइन

यो leap year हो कि होइन?

कुनै वर्ष 4 ले भाग जान्छ र 100 ले जाँदैन भने, वा 400 ले भाग जान्छ भने leap year हुन्छ; remainder % ले भाग जान्छ कि जाँच्छ र AND / OR ले नियमहरूलाई एउटै condition मा जोड्छ

PIN का लागि तीन प्रयास

AND ले जोडिएको loop condition कुनै एक भाग असत्य हुनेबित्तिकै रोकिन्छ: यहाँ PIN सही हुँदा वा तीन प्रयास सकिँदा

विद्यार्थी पास भयो कि भएन?

Condition हरूलाई AND (सबै सत्य हुनुपर्ने) र OR (एउटा भए पुग्ने) ले जोड्न सकिन्छ, र एउटा if / else अर्कोभित्र बस्न सक्छ, त्यसैले प्रोग्रामले एउटा सत्य नभेटेसम्म एकपछि अर्को प्रश्न सोध्छ

सङ्ख्याका अङ्क जोड्ने

n % 10 भनेको n को अन्तिम अङ्क हो र floor(n / 10) भनेको त्यो अङ्कबिनाको n, त्यसैले n, 0 नभएसम्म दुवै दोहोर्‍याउने while loop ले हरेक अङ्क एक पटक हेर्छ

FizzBuzz: loop, % र निर्णय

Loop ले हरेक पटक निर्णय गर्न सक्छ: 3 ले i लाई ठ्याक्कै भाग जाँदा i % 3 == 0 सत्य हुन्छ, र ELSE IF को लहरमा पहिलो सत्य जाँचले जित्छ, त्यसैले सबैभन्दा विशेष अवस्था पहिले आउनुपर्छ

Loop ले दोहोर्‍याउनुहोस्

Loop ले उही लाइनहरू दोहोर्‍याउँछ: for loop आफ्नो counter को हरेक मानका लागि एक पटक चल्छ, accumulator ले हरेक पटक केही जोड्छ, र while loop आफ्नो condition असत्य नभएसम्म दोहोरिन्छ

While loop ले पैसा जम्मा गर्ने

While loop ले आफ्नो condition सत्य भएसम्म भित्रको भाग दोहोर्‍याउँछ, त्यसैले भित्रको भागले कुनै दिन condition असत्य बनाउने कुरा बदल्नैपर्छ, नत्र loop कहिल्यै रोकिँदैन

Nested loop ले गुणन तालिका

Nested loop मा बाहिरी loop को हरेक पटकका लागि भित्री loop सुरुदेखि अन्त्यसम्म चल्छ, त्यसैले r लहर र c स्तम्भको तालिकामा r × c गुणनफल हुन्छन्

Nested loop ले ताराका ढाँचा

Nested loop मा बाहिरी loop को हरेक फन्कोमा भित्री loop पूरै चल्छ; भित्री loop 1 देखि row सम्म जाँदा लहर r मा r वटा तारा र n लहरमा n(n + 1)/2 वटा तारा print हुन्छन्

सूची र त्यसका स्थान

सूची (array) ले वस्तुलाई क्रममा राख्छ; हरेक वस्तुको 0 बाट गनिने index हुन्छ, त्यसैले n वटा वस्तु भएको सूचीका index 0 देखि n − 1 सम्म हुन्छन्

Linked list भनेको रेल हो

Linked list ले हरेक वस्तुलाई अर्को node को link सहितको node मा राख्छ; अगाडि थप्न तुरुन्तै हुन्छ, तर node i मा पुग्न head बाट i वटा link पछ्याउनुपर्छ

प्लेटको थाक (पछि आउने, पहिले जाने)

Stack ले वस्तुहरूलाई थाकमा राख्छ: push ले वस्तुलाई माथि राख्छ, pop ले माथिको वस्तु झिक्छ र peek ले मात्र हेर्छ, त्यसैले अन्तिममा राखेको वस्तु नै पहिले निस्कन्छ (LIFO)

टिकटको लाइन (पहिले आउने, पहिले जाने)

Queue ले वस्तुहरूलाई लाइनमा राख्छ: enqueue ले वस्तु पछाडि थप्छ, dequeue ले अगाडिको वस्तु निकाल्छ र front ले मात्र हेर्छ, त्यसैले पहिले आएको वस्तु नै पहिले निस्कन्छ (FIFO)

लहर र स्तम्भ: 2-D array

Two-dimensional array लहरहरूको सूची हो, हरेक लहर मानहरूको सूची; grid[row][col] ले एउटा मान छान्छ, लहरभरि वा स्तम्भभरि चल्ने loop ले तिनलाई जोड्छ, र दुईवटा nested loop ले हरेक कोठा हेर्छन्

Binary search tree

Binary search tree मा हरेक node को बायाँका सबै सङ्ख्या साना र दायाँका सबै ठूला हुन्छन्, त्यसैले खोजले हरेक चरणमा आधा tree फाल्छ, तर tree झ्याम्म र होचो रहुन्जेल मात्र

के bracket हरू मिल्छन्?

Bracket जाँच्न हरेक खुल्ने bracket लाई stack मा push गर्ने; बन्द गर्ने bracket माथिको bracket सँग मिल्नुपर्छ, जुन pop गरिन्छ; अन्तिममा stack खाली हुनुपर्छ

Hash table: नाम तुरुन्तै भेट्ने

Hash table ले hash function ले हरेक key लाई bucket नम्बरमा बदल्छ; key थप्दा र खोज्दा त्यही एउटा bucket हेरिन्छ, त्यसैले collision थोरै भएसम्म जति धेरै key भए पनि यी छिटो रहन्छन्

Tree हेर्ने तरिका: pre, in र post order

Traversal ले tree को हरेक node एक पटक हेर्छ; pre-order ले node लाई यसका छोराछोरीअघि, in-order ले बायाँ र दायाँ छोराछोरीबीच, post-order ले तिनपछि, र level order ले queue सँग लहरै-लहर हेर्छ

एक-एक गरेर खोज्नुहोस्

Linear search ले खोजेको सङ्ख्यालाई हरेक वस्तुसँग क्रमैसँग तुलना गर्छ; राम्रो अवस्थामा 1 पटक र नराम्रो अवस्थामा वा सङ्ख्या नभएमा जति वस्तु छन् त्यति पटक तुलना चाहिन्छ

Bubble sort, एक-एक swap गर्दै

Bubble sort ले छिमेकी सङ्ख्याका हरेक जोडी तुलना गर्छ र क्रम मिलेन भने swap गर्छ; हरेक pass ले बाँकीमध्ये सबैभन्दा ठूलो सङ्ख्यालाई अन्तिममा पुर्‍याउँछ, र कुनै swap नभएको pass ले सूची मिलिसकेको जनाउँछ

Degrees of separation: साथीबीचको दूरी

साथीहरूको network एउटा graph हो; हरेक link लाई 1 गन्दा shortest path भनेको सबैभन्दा कम link हो, जुन मान्छेहरूलाई कति link टाढा छन् त्यस क्रममा, नजिकको पहिले, पक्का गर्दै भेटिन्छ

सबैभन्दा कम नोटले खुद्रा फिर्ता दिने

Greedy algorithm ले हरेक चरणमा अहिलेलाई सबैभन्दा राम्रो देखिने छनोट गर्छ: खुद्राका लागि, केही बाँकी नरहेसम्म अझै अटाउने सबैभन्दा ठूलो नोट बारम्बार दिन्छ

Insertion sort: तास मिलाएजस्तै

Insertion sort ले बायाँ मिलेको भाग राख्छ र अर्को सङ्ख्यालाई हरेक ठूलो सङ्ख्या नाघ्दै सारेर त्यसभित्र राख्छ; लगभग मिलेको सूचीमा यसले धेरै कम काम गर्छ

के यो रूढ सङ्ख्या हो?

1 र आफैँले मात्र भाग जाने सङ्ख्या रूढ हुन्छ; प्रोग्रामले % ले भाजक जाँच्छ, भाग जाने पहिलोमा रोकिन्छ, र वर्गमूलसम्मका भाजक मात्र जाँचे पुग्छ, किनकि कुनै ठूलो गुणनखण्डसँग सानो जोडी पनि हुन्छ

Selection sort: सबैभन्दा सानो खोज

Selection sort ले नमिलेको भागमा सबैभन्दा सानो सङ्ख्या खोज्छ र अगाडिको अर्को ठाउँमा swap गर्छ; यसले सधैँ उत्तिकै तुलना गर्छ, तर हरेक pass मा बढीमा एउटा मात्र swap गर्छ

BFS र DFS: भूलभुलैया खोज्ने

Breadth-first search (BFS) ले queue प्रयोग गरेर दूरीको क्रममा कोठा हेर्छ, त्यसैले यसको बाटो सधैँ सबैभन्दा छोटो हुन्छ; depth-first search (DFS) ले stack प्रयोग गरेर एउटै बाटो जतिसक्दो टाढासम्म पछ्याउँछ, त्यसैले यसको बाटो लामो हुन सक्छ

Linear कि binary search?

Binary search ले खोजेको सङ्ख्यालाई मिलाइएको सूचीको बीचको वस्तुसँग तुलना गरेर, त्यो हुन नसक्ने आधा भाग फाल्छ, त्यसैले 16 वटा वस्तुमा 16 पटकको सट्टा बढीमा 5 पटक तुलना चाहिन्छ; यो मिलाइएको input मा मात्र चल्छ

Merge sort: टुक्राऊ अनि जिताऊ

Merge sort ले हरेक भागमा एउटा सङ्ख्या नबचेसम्म सूचीलाई आधा गर्छ, अनि सधैँ अगाडिको सानो सङ्ख्या लिँदै मिलेका भाग जोड्छ; यसको तुलना n log n जस्तो बढ्छ, bubble sort को n² भन्दा धेरै ढिलो

शहरहरूबीचको सबैभन्दा छोटो सडक

Dijkstra को algorithm ले शहरहरूलाई सुरुबाटको दूरीको क्रममा पक्का गर्छ; पक्का भएको हरेक शहरको दूरी अन्तिम हो, र त्यहाँबाट जाने सडकले अरू शहरको दूरी छोटो मात्र बनाउन सक्छन्

तापक्रम बदल्ने function

Function ले नियमलाई एकै ठाउँमा राख्छ: to_fahrenheit(c) ले c × 9 ÷ 5 + 32 फर्काउँछ, र हरेक call ले यसको parameter c लाई नयाँ argument दिन्छ

Recursion ले युक्लिडको GCD

युक्लिडको नियम gcd(a, b) = gcd(b, a % b) ले हरेक call मा सङ्ख्या सानो बनाउँछ, त्यसैले recursive function आफ्नो base case, b = 0, मा पुग्छ, जहाँ उत्तर a हो

Function: क्षेत्रफल निकाल्ने मेसिन

Function भनेको एक पटक लेखेर धेरै पटक प्रयोग गरिने नाम दिइएको चरणहरूको समूह हो: यसका parameter ले हरेक call का argument पाउँछन्, र return ले उत्तरलाई call गरेको ठाउँमा फर्काउँछ

Fibonacci: recursion आफैँलाई दोहोर्‍याउँदा

fib(n) = fib(n − 1) + fib(n − 2), fib(0) = 0 र fib(1) = 1 सहित; हरेक call ले थप दुईवटा call गर्ने भएकाले call को सङ्ख्या निकै छिटो बढ्छ, र उही उत्तर धेरै पटक निकालिन्छ

Recursion: आफैँलाई call गर्ने function

Recursive function ले समस्याको सानो रूपमा आफैँलाई call गरेर समस्या हल गर्छ; base case ले सबैभन्दा सानो रूपको उत्तर सिधै दिन्छ, त्यसैले call रोकिन्छन् र उत्तरहरू call stack हुँदै फर्कन्छन्

Tower of Hanoi

n वटा disk सार्न, माथिका n − 1 वटा पन्छाउने, सबैभन्दा ठूलो सार्ने, अनि n − 1 वटा फेरि माथि राख्ने; उही योजनाले साना थुप्रा हल गर्छ, त्यसैले हरेक पटक चाल दोब्बर भएर एक थपिन्छ: 2ⁿ − 1

Traffic light एउटा state machine हो

State machine सधैँ केही state मध्ये एउटामा हुन्छ र नियमअनुसार अर्को state मा सर्छ; traffic light ले आफ्नो state एउटा variable मा राख्छ र (state + 1) % 3 ले रातो, हरियो, पहेँलो हुँदै घुम्छ

रोबोटलाई ब्याट्रीसम्म पुर्‍याउनुहोस्

Algorithm भनेको क्रमैसँग गरिने ठ्याक्कै चरणहरूको सूची हो; क्रम वा एउटा चरण बदल्दा नतिजा बदलिन्छ, र योजना बिग्रिएको चरण खोज्नुलाई debugging भनिन्छ

गोप्य code: Caesar cipher

Caesar cipher ले हरेक अक्षरलाई वर्णमालामा निश्चित ठाउँ (shift) अगाडिको अक्षरले बदल्छ, Z बाट फेरि A मा घुम्दै; उत्तिकै सङ्ख्या पछाडि सार्दा यो खुल्छ

भूलभुलैयाबाट बाटो बनाउनुहोस्

ठूलो समस्यालाई साना भागमा टुक्र्याउँदा (decomposition) सजिलो हुन्छ; हरेक भाग केही चरण बन्छ, र एउटा भागको गल्ती, जस्तै एक चाल बढी, ले पूरै योजना बिगार्छ

सात पटकमा मेरो सङ्ख्या अनुमान गर

हरेक पटक दायरा आधा गर्दा 1 देखि 100 सम्मको जुनसुकै सङ्ख्या बढीमा 7 अनुमानमा भेटिन्छ, किनकि 7 पटक आधा गर्दा 100 वटा सङ्ख्या 1 मा झर्छन् (2⁷ = 128): binary search को आधार यही हो

सिँढी चढ्ने: सम्झ, नदोहोर्‍याऊ

Dynamic programming ले ठूलो समस्या साना समस्याका उत्तरबाट हल गर्छ र ती उत्तर सम्झेर राख्छ: n खुड्किला चढ्ने तरिका, n − 1 का तरिका र n − 2 का तरिकाको योग हो

काम कति छिटो बढ्छ?

प्रोग्रामले गर्ने काम input अनुसार बढ्छ: n वटा वस्तुमा एउटा loop ले करिब n चरण लिन्छ, loop भित्रको loop ले n × n, र हरेक पटक n आधा गर्दा करिब log₂ n मात्र; Big O ले यो बढोत्तरीलाई नाम दिन्छ

Big O दौड

Big O ले input को आकार n अनुसार algorithm का चरण कसरी बढ्छन् भन्छ: n दोब्बर हुँदा O(1) उस्तै रहन्छ, O(log n) एकले बढ्छ, O(n) दोब्बर हुन्छ, O(n log n) दोब्बरभन्दा अलि बढी, र O(n²) चार गुणा