Programming Lab

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

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

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 सँग लहरै-लहर हेर्छ

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 ले शहरहरूलाई सुरुबाटको दूरीको क्रममा पक्का गर्छ; पक्का भएको हरेक शहरको दूरी अन्तिम हो, र त्यहाँबाट जाने सडकले अरू शहरको दूरी छोटो मात्र बनाउन सक्छन्

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

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

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²) चार गुणा