Tower of Hanoi
Disk को थुप्रोलाई peg A बाट peg C मा सार्नुहोस्, एक पटकमा एउटा disk, सानोमाथि ठूलो कहिल्यै होइन। Recursive योजनाले जतिसुकै disk भए पनि हल गर्छ: call र चाल हेर्नुहोस्, र 2ⁿ − 1 भन्ने ढाँचा पत्ता लगाउनुहोस्।
मूल अवधारणा
n वटा disk सार्न, माथिका n − 1 वटा पन्छाउने, सबैभन्दा ठूलो सार्ने, अनि n − 1 वटा फेरि माथि राख्ने; उही योजनाले साना थुप्रा हल गर्छ, त्यसैले हरेक पटक चाल दोब्बर भएर एक थपिन्छ: 2ⁿ − 1
पाठ: Function र recursion
Tower of Hanoi तीनवटा peg र disk को थुप्रो भएको पहेली हो, हरेक disk आफूमुनिको भन्दा सानो हुन्छ। Disk हरू peg A बाट peg C मा सार्नुपर्छ, एक पटकमा एउटा, र ठूलो disk सानोमाथि कहिल्यै बस्न पाउँदैन। गाह्रो देखिन्छ, तर recursion ले यसलाई सजिलो बनाउँछ। n वटा disk को थुप्रो A बाट C मा सार्न: पहिले माथिका n − 1 वटा disk लाई खाली peg B मा सार्ने (उसैगरी हल हुने सानो थुप्रो), त्यसपछि सबैभन्दा ठूलो disk लाई C मा सार्ने, अनि n − 1 वटालाई B बाट त्यसमाथि सार्ने। एउटा disk को थुप्रो base case हो: सिधै सार्ने। हरेक थप disk ले सानो थुप्रो दुई पटक हल गर्नुपर्छ र एउटा चाल थप्छ, त्यसैले चाल 1, 3, 7, 15, 31 हुन्छन्: सधैँ 2ⁿ − 1।
के सिक्नुहुनेछ
- Tower of Hanoi को recursive योजना बताउनुहोस्।
- Recursive function को base case पत्ता लगाउनुहोस्।
- n वटा disk लाई किन 2ⁿ − 1 चाल लाग्छ, व्याख्या गर्नुहोस्।
- Disk थप्दा चाल कति छिटो बढ्छ, अनुमान गर्नुहोस्।
सुरु गर्नुअघि
- Function भनेको के हो, र function ले आफैँलाई call गर्न सक्छ (recursion) थाहा हुनुपर्छ।
सामग्री
- हातैले खेल्न फरक आकारका तीनवटा सिक्का र तीनवटा चिह्न लगाइएका ठाउँ
उपकरण
- केही पनि चाहिँदैन
विधि
- 3 वटा disk को थुप्रो हल गरेर चाल गन्नुहोस्।
- 4 वटा disk सँग हल गर्नुहोस्।
- सानो थुप्रोमा Step गरेर call हेर्नुहोस्।
- अभ्यासका challenge हरूको उत्तर दिनुहोस्।