👨‍💻 ◀️ 🤛🏼 उंगलियों पर हनोई का टॉवर 🤽🏻 👅 🔕

कुछ परिचित प्रोग्रामरों के साथ बात करने के बाद, मुझे अचानक पता चला कि हर कोई हनोई के टॉवर के बारे में नहीं जानता है, और जो लोग जानते हैं, उनमें से बहुत कम लोग समझते हैं कि यह कार्य कैसे हल किया जाता है।
विकिपीडिया विषय पर, मामले पर बहुत सख्ती से लिखता है, और कुछ भी नहीं समझाता है। जैसे, इसे एक ट्रिज्म के रूप में लें। इसलिए, यह समझना कि यह कैसे हल किया जाता है, तुरंत मुश्किल है। लेकिन कार्य बहुत सरल है, और अभी तक प्रोग्रामिंग और गणितीय रूप से दिलचस्प है।

लेख में कई चित्र होंगे। किसी समस्या को पुनरावर्ती रूप से कैसे हल करें और बाइनरी खोज द्वारा इसे कैसे हल किया जाए, इसका स्पष्टीकरण।
सामान्य तौर पर, लेख उन बहादुरों को समर्पित है जो अभी भी हनोई के टॉवर से डरते हैं, लेकिन इससे डरना बंद करना चाहते हैं।

खेल के नियम

वे बहुत सरल हैं। विभिन्न आकारों के डिस्क के साथ 1 पिरामिड है, और 2 और खाली पिरामिड हैं। डिस्क को एक पिरामिड से दूसरे में ले जाना आवश्यक है। आप केवल प्रति ड्राइव एक ड्राइव को स्थानांतरित कर सकते हैं। गुना डिस्क केवल छोटे से बड़े हो सकते हैं।
तो हमारे पास एक ऐसा पिरामिड है:

और हमें मध्य अक्ष पर कहने के लिए इसे स्थानांतरित करने की आवश्यकता है।
यदि आप शुरू से ही नहीं, बल्कि अंत से एक समस्या को हल करना शुरू करते हैं - तो यह बहुत सरल हो जाता है। इसे खत्म करने की सोचते हैं। पिरामिड को दूसरी धुरी पर स्थानांतरित करने के लिए, हमें सबसे कम डिस्क को स्थानांतरित करने की आवश्यकता है, और यह केवल तब किया जा सकता है जब 4 ऊपरी डिस्क तीसरे अक्ष पर हो:

4 डिस्क को तीसरे अक्ष पर स्थानांतरित करने के लिए, आपको अनिवार्य रूप से एक ही समस्या को हल करने की आवश्यकता है, लेकिन 4 डिस्क के लिए। अर्थात्, तीसरी धुरी पर हम 4 डिस्क को तभी स्थानांतरित कर सकते हैं जब हमारे पास दूसरी धुरी पर 3 डिस्क हों:

पुनरावृत्ति महसूस करते हैं?
5 डिस्क के ढेर को बदलना है:
1. एक स्वतंत्र अक्ष पर 4 डिस्क के ढेर को स्थानांतरित करना
2. 5 वीं डिस्क को उस अक्ष पर स्थानांतरित करना जिसकी हमें आवश्यकता है
3. 4 अक्ष के एक ढेर का स्थानांतरण उस अक्ष पर करना चाहिए जिसकी हमें ज़रूरत है

बदले में, 4 डिस्क के ढेर को बदलना है:
1. एक स्वतंत्र अक्ष पर 3 डिस्क के ढेर को स्थानांतरित करना
2. 4 डी डिस्क को उस अक्ष पर स्थानांतरित करना जो हमें चाहिए
3. अक्ष के लिए 3 डिस्कों का एक स्टैक स्थानांतरित करना जो हमें चाहिए

वह सब है।

पुनरावर्ती कार्यान्वयन

इस तरह के एक विस्तृत विवरण के बाद, इस एल्गोरिदम को लागू करना मुश्किल नहीं होगा।

डेल्फी कार्यान्वयन

इसलिए मैंने बुर्ज के प्रकारों के साथ एक मॉड्यूल का वर्णन किया:

unit untHTypes; interface const MaxRingCount = 5; type TTower = record RingCount: Integer; Rings: array [0..MaxRingCount-1] of Integer; procedure MoveRing(var AtTower: TTower); end; TTowers = array [0..2] of TTower; procedure InitTowers(var towers: TTowers); implementation procedure InitTowers(var towers: TTowers); var i: Integer; begin towers[0].RingCount := MaxRingCount; towers[1].RingCount := 0; towers[2].RingCount := 0; for i := 0 to MaxRingCount - 1 do begin towers[0].Rings[i] := MaxRingCount - i; towers[1].Rings[i] := 0; towers[2].Rings[i] := 0; end; end; { TTower } procedure TTower.MoveRing(var AtTower: TTower); begin Assert(RingCount > 0); Assert(AtTower.RingCount - 1 < MaxRingCount); if AtTower.RingCount > 0 then Assert(Rings[RingCount - 1] < AtTower.Rings[AtTower.RingCount - 1]); Dec(RingCount); AtTower.Rings[AtTower.RingCount] := Rings[RingCount]; Rings[RingCount] := 0; Inc(AtTower.RingCount); end; end.

TTower एक संरचना है जो एक टॉवर का वर्णन करती है। इसमें, रिंगकाउंट टावर पर वास्तव में तैयार किए गए छल्ले की संख्या को संग्रहीत करता है। रिंगों का आकार 1 से मैक्सरिंगकाउंट के रिंग्स सरणी में संग्रहीत है। चूँकि हमारे पास 3 टावर हैं, TTT टाइप की TTowers = array [0..2] घोषित की गई थी;
इसके अलावा, टॉवर से, आप MoveRing फ़ंक्शन का उपयोग करके ऊपरी रिंग को दूसरे में स्थानांतरित कर सकते हैं। फ़ंक्शन Assert-s के माध्यम से ऑपरेशन की शुद्धता की जांच करता है।
टॉवर समाधान स्वयं प्रोजेक्ट फ़ाइल में है:

 program Hanoy; {$APPTYPE CONSOLE} uses SysUtils, untHTypes in 'untHTypes.pas'; {$R *.res} procedure SolveHanoy; var towers: TTowers; function GetThirdIndex(index1, index2: Integer): Integer; //        begin //      Assert(index1 <> index2); case index1 of 0: if index2 = 1 then Result := 2 else Result := 1; 1: if index2 = 2 then Result := 0 else Result := 2; 2: if index2 = 0 then Result := 1 else Result := 0; else Assert(False,'wrong indeces'); end; end; procedure MoveStack(stacksize: Integer; fromindex, atindex: Integer); //         var thirdindex: Integer; begin if stacksize = 0 then Exit; thirdindex := GetThirdIndex(fromindex, atindex); //   MoveStack(stacksize - 1, fromindex, thirdindex); //  ( 1 )    towers[fromindex].MoveRing(towers[atindex]); //       WriteLn(fromindex,'-',atindex); //      MoveStack(stacksize - 1, thirdindex, atindex); //        end; begin InitTowers(towers); MoveStack(MaxRingCount, 0, 1); end; begin SolveHanoy; end.

एल्गोरिथम जटिलता

हम आसानी से गणना कर सकते हैं कि पिरामिड को स्थानांतरित करने के लिए हमें कितनी क्रियाओं की आवश्यकता है।
यदि हम स्टैक को एक डिस्क से स्थानांतरित करते हैं, तो हमें 1 कार्रवाई की आवश्यकता है।
यदि दो का ढेर है, तो 1 * 2 (एक डिस्क से दो बार स्टैक ले जाएँ) + 1 (अंतिम डिस्क को स्थानांतरित करें)
यदि तीन में से ((1 * 2) + 1) * 2 + 1
पाँच में से: (((((((1 * 2) + 1) * 2 + 1) * 2 + 1) * 2 + 1)
तो, प्रत्येक ऑपरेशन आंदोलनों के 2 गुना + 1 नंबर से बढ़ता है। N संचालन के लिए कोष्ठक खोलना - हमें मिलता है:
$छवि$
आप राशि से छुटकारा पा सकते हैं, क्योंकि यह इसके बराबर है:
$छवि$
पी एस मैं अपने सिर में राशि से छुटकारा पा लिया, एक ज्यामितीय प्रगति को कम करने वाले सदस्यों के योग को याद करते हुए, लेकिन मुझे उम्मीद है कि गणितज्ञ यह बताएंगे कि इन परिवर्तनों को सही ढंग से कैसे लिखा जाए
कुल मिलाकर, सभी परिवर्तनों के बाद, यह निकला:
$छवि$

यही है, अगर हम कुछ अजीब चाहते हैं, उदाहरण के लिए, 64 डिस्क के लिए हनोई के टॉवर का समाधान रिकॉर्ड करने के लिए, तो हमारे पास पर्याप्त आधुनिक भंडारण मीडिया नहीं होगा। वास्तव में, हमें कहीं भी कुछ भी लिखना नहीं है। यह 0 से + अनंत तक सभी संख्याओं को लिखने के समान है, ताकि आप उन्हें बाद में उपयोग कर सकें, क्योंकि हनोई के टॉवर का समाधान एक भग्न है।

भग्न प्रकृति

हाँ, हाँ। हनोई के टॉवर का समाधान प्रकृति में भग्न है। आइए देखते हैं। मान लें कि हमारे पास एक स्ट्रिंग को लिखी गई प्रत्येक क्रिया है। फिर 6 डिस्क के टॉवर के लिए, आप इसे कुछ इस तरह से लिख सकते हैं:

खैर, चूंकि यह एक भग्न है, हम आसानी से किसी भी ऑपरेशन को केवल उसके सीरियल नंबर को जानते हुए नाम दे सकते हैं। और इससे भी अधिक, हम किसी भी ऑपरेशन के समय सभी डिस्क की स्थिति को ठीक कर सकते हैं।

बाइनरी एल्गोरिदम

इसलिए, हम संचालन की सही संख्या जानते हैं, और हम उस ऑपरेशन के सूचकांक को भी जानते हैं जिसके लिए हम राज्य को पुनर्स्थापित करना चाहते हैं।
मान लें कि हमारे पास 6 डिस्क का टॉवर है (हम हमेशा की तरह, 1 से मध्य अक्ष तक चलते हैं), जिसका मतलब है कि हमारे पास 2 ^ 6-1 = 63 ऑपरेशन हैं। मान लीजिए कि हमें 49 वें ऑपरेशन के लिए राज्य को पुनर्स्थापित करने की आवश्यकता है।
पूर्णांक 63 को 2 से विभाजित करें। यह 31 को बदल जाता है। यह ऑपरेशन का सूचकांक है जिस पर 6 वीं डिस्क को स्थानांतरित किया जाएगा:

हमारे पास 49 वाँ संचालन सूचकांक है। इसका मतलब है कि 6 वीं डिस्क पहले से ही मध्य अक्ष पर स्थित है। इसके अलावा, चूंकि हम दाईं ओर हैं, पांचवीं डिस्क या तो 3 अक्ष पर या 2 पर स्थित है। हमें उसी एल्गोरिदम का उपयोग करके टॉवर के साथ काम करने के लिए, हम 49 वें ऑपरेशन से 32 को घटाते हैं और सबऑपरेशन इंडेक्स पाते हैं। यह 17 है। 5 डिस्क के ढेर को स्थानांतरित करने के लिए, 31 ऑपरेशन की आवश्यकता होती है, 5 वीं डिस्क 16 वें ऑपरेशन में और 3 अक्ष से 2 वें तक चलती है।
तो संख्या 17 सही है:

और इसका मतलब है कि ड्राइव 5 पहले से ही दूसरे अक्ष पर ले जाया गया है।
सादृश्य द्वारा, हम शेष डिस्क की स्थिति को पुनर्स्थापित करते हैं।

कार्यान्वयन (द्विआधारी तरीका)

मैंने बुर्ज का एक सुंदर प्रतिपादन जोड़ा। सहमति दें, कंसोल लॉग को देखना उबाऊ है। इसलिए, कार्यान्वयन बढ़ गया है, और मैं लेख के अंत में पूर्ण परियोजना (स्रोत + बाइनरी) संलग्न करूंगा। मैं तुम्हें यहाँ दूंगा

डेल्फी में पुनरावर्ती फ़ंक्शन कोड

 procedure TfrmView.RestoreDisk(size, actionIndex, actionCount, fromAxe, atAxe: Integer); var pivot: Integer; i: Integer; thirdAxe: Integer; begin pivot := actionCount div 2; thirdAxe := GetThirdIndex(fromAxe, atAxe); if actionIndex = pivot then //  ,       begin //       .   FTowers[fromAxe].PutRing(size); for i := size - 1 downto 1 do FTowers[thirdAxe].PutRing(i); FAction.FromIndex := fromAxe; FAction.AtIndex := atAxe; end else if actionIndex < pivot then begin //        FTowers[fromAxe].PutRing(size); //      RestoreDisk(size - 1, actionIndex, actionCount - pivot - 1, fromAxe, thirdAxe); end else begin //          FTowers[atAxe].PutRing(size); //     RestoreDisk(size - 1, actionIndex - pivot - 1, actionCount - pivot - 1, thirdAxe, atAxe); end; end; procedure TfrmView.RestoreTowers; var index: Integer; begin ClearTowers(FTowers); index := tbOperation.Position; RestoreDisk(MaxRingCount, index, 2 shl (MaxRingCount - 1) - 1, 0, 1); Invalidate; end;

सीरपिन्स्की ट्रायंगल

मैं एक दिलचस्प विशेषता को पारित करने में उल्लेख करना चाहूंगा। यदि रिंग के सभी संभावित आंदोलनों को एक ग्राफ में एकत्र किया जाता है, तो प्रत्येक नोड के लिए सबसे अधिक बार 3 कनेक्शन होंगे। सभी नोड्स और कनेक्शन को त्रिकोण के आकार में अच्छी तरह से व्यवस्थित किया जा सकता है। Sierpinski त्रिकोण:

विकिपीडिया पर इसके बारे में यहाँ और अधिक पढ़ें। जो सामान्य रूप से आश्चर्य की बात नहीं है, क्योंकि हम पहले से ही समाधान के भग्न प्रकृति को जानते हैं;)

कुल मिलाकर

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

उदाहरण बाइनरी एल्गोरिथ्म (exe + स्रोत कोड, डेल्फी)

उंगलियों पर हनोई का टॉवर