#1
5
(Microsoft द्वारा अनुवादित)
-
- मुझे लगता है कि छल्ले ले जाने के लिए बुनियादी नियम अच्छी तरह से जाना जाता है ।
- यदि छल्ले की संख्या अजीब है आप केवल 1 कदम की जरूरत है अंगूठी आप चाहते है के शीर्ष पर सीधे शीर्ष अंगूठी जगह है ।
- अगर यह भी है, वहां दो कदम के लिए कदम बनाने की जरूरत है । चलो खूंटे ए, बी और सी बाएं से दाएं मान लेते हैं । यदि, उदाहरण के लिए, बी पर हमारे पास छल्ले 1,2,3,4 के साथ एक ढेर है और उन्हें सी पर रिंग 5 पर रखना चाहते हैं, तो पहला कदम 1 से ए और 2 से सी, और अगला, 1 से सी होगा। और कुल 15 चालों के साथ हमारे पास खूंटी सी पर 5 से अधिक 1,2,3,4 छल्ले होंगे।
- प्रारंभिक लेआउट में छोटे छल्ले के शीर्ष पर बड़े छल्ले हैं (जो इस खेल के संस्करण I से मुख्य अंतर है) लेकिन जब आप खेलना शुरू करते हैं तो आप हनोई के टॉवर में एक छोटे से एक के शीर्ष पर एक बड़ी अंगूठी नहीं डाल सकते हैं।
- मुझे लगता है कि खेल को हल करने के लिए सबसे अच्छा तरीका 9, 8 और 7 के छल्ले की स्थिति पर एक त्वरित नज़र के साथ शुरू हो रहा है । यह देखना महत्वपूर्ण है कि क्या रिंग 9 पहले से ही खूंटी के आधार पर है । और अगर ऐसा नहीं है, क्या सबसे अच्छा तरीका है (कम चालें) इसे वहां डाल दिया । इस मामले में यह अक्सर होता है (विशेष रूप से यदि 7 और 8 अलग खूंटे पर हैं) कि एक 8 से अधिक 7 जगह के लिए 9 के लिए एक मुक्त खूंटी की जरूरत है । इसके अलावा हम 9 पर 6 जगह हो सकती है, 7 6 और फिर 7 से अधिक 6 जाने के बाद मुक्त खूंटी में जा रहा है । परिणाम 1 से 7 तक एक ढेर होगा और 8,9 के शीर्ष पर इन 7 छल्ले को रखने के लिए 127 अतिरिक्त चालों की आवश्यकता होगी (हनोई I स्थिति के टॉवर में एक खेल को हल करने के लिए चालों की न्यूनतम संख्या है: न्यूनतम चालें = 2 ^n - 1 जहां एन छल्ले की संख्या है, 3 छल्ले 7 चालों की आवश्यकता होगी, 4 छल्ले 15 की आवश्यकता होगी ... 7 छल्ले 127 और इतने पर की आवश्यकता होगी) ।
- जो भी मामला है, उद्देश्य है, संभव चाल की ंयूनतम संख्या के साथ, हनोई मैं स्थिति के एक टॉवर के लिए प्रारंभिक लेआउट बदलने के लिए । इसका मतलब है कि आपको हमेशा पहले से पता चल जाएगा कि खेल को वास्तव में खत्म किए बिना हल किया जा सकता है। जब छल्ले हनोई मैं स्थिति के एक टॉवर में है (आरोही क्रम में एक ढेर छल्ले 1,2 के साथ शुरू.. । एक खूंटी पर, एक मुक्त खूंटी, और शेष छल्ले के साथ एक खूंटी, आरोही क्रम में भी, खूंटी के आधार पर परिष्करण जहां 9 है), बस पहले से ही आवश्यक आवश्यक चालों के लिए बनाया चालें जोड़ें और परिणाम की जरूरत ंयूनतम चाल के बराबर होना चाहिए (जब भी मैं करते है कि नियंत्रण सिर्फ पिछले अंक जोड़ें) ।
- तीन उदाहरण (सभी इस वेबसाइट से)।
- प्रारंभिक लेआउट (145 न्यूनतम चालें आवश्यक)
खूंटी ए - 1,8,2,9
खूंटी बी - 7,3
खूंटी सी - 6,5,4
चरण 1 - सबसे अच्छी रणनीति खूंटी सी के आधार पर 9 और खूंटी बी पर 7 के शीर्ष पर 6 जगह है।
पहला कदम है: एक पर 9 के शीर्ष पर 3 अंगूठी, तो बी पर 7 के शीर्ष पर 4.. ।
प्रारंभिक लेआउट से 18 चालों के बाद हमें मिलता है:
खूंटी ए - 1
खूंटी बी - 7,6,5,4,3,2 18 चालें
खूंटी सी - 9,8
चरण 2 - यदि हम इस लेआउट को ध्यान से देखते हैं, तो हम ध्यान देंगे कि यह बी पर 7 के शीर्ष पर 6 छल्ले के बराबर है, बशर्ते अगला कदम सी पर 8 के शीर्ष पर रिंग 1 रखें। हम 6 छल्ले की बात कर रहे हैं (6,5 ... 1 यानी खूंटी बी पर भी और 2 चरणों की आवश्यकता होती है)। तो एक हम एक पहले कदम की जरूरत है पर इन छह छल्ले जगह के लिए दूसरे खूंटी पर 1 जगह है, इस मामले में सी ।
जैसा कि हम पहले से ही जानते हैं, एक और खूंटी (खूंटी ए) के लिए 6 छल्ले स्थानांतरित करने के लिए हम ६३ चाल की जरूरत है । इन चालों के बाद 9,8 के शीर्ष पर 7, अब मुफ्त जगह के लिए एक अतिरिक्त है।
तो, इस चरण 2 में चालें 63 + 1 = 64 होंगी और हमें जो लेआउट मिलेगा वह है:
A - 6,5,4,3,2,1
बी - 63+1 = 64 चालें
C - 9,8,7
अब तक, हमारे पास चरण 2 पर चरण 1 प्लस 64 पर 18 चालें हैं
चरण 3 - उपरोक्त लेआउट उस बात से मेल खाता है जिसे मैं हनोई आई स्थिति का टावर कहता हूं।
खेल को खत्म करने के लिए हमें 6 छल्ले (6,5,... 1) खूंटी ए पर खूंटी सी पर 9,8,7 के शीर्ष पर। इसके लिए एक और 63 चालों की आवश्यकता होगी।
कुल चालें = 18 + 64 + 63 = 145 जो कि न्यूनतम चालें आवश्यक है। - प्रारंभिक लेआउट (256 न्यूनतम चालों की आवश्यकता)
A - 5,3,9
B - 8,1,6,4
C - 2,7
आधार पर 9 जगह के लिए, के रूप में 8 और 7 अलग खूंटे पर हैं, हम बी पर 8 के शीर्ष पर 7 जगह की जरूरत है ।
चरण 1 - हमारा लक्ष्य बी पर सी पर 9 और 8 के शीर्ष पर 7 जगह है। इस लक्ष्य को प्राप्त करने के लिए हमें पहले 9 को प्राप्त करने के लिए 6,4 को 9 से मुक्त सी पर 9 के शीर्ष पर ले जाने की आवश्यकता है।
पहली पांच चालें 9 के शीर्ष पर 7,6 के शीर्ष पर 4, ए पर 4 से 6,1 से 4 और खूंटी बी पर 7 से 8 हैं।
20 चालों के बाद लेआउट होगा
A - 5,3
B - 8,7,6,4,2,1 20 चालें
C - 9
चरण 2 खूंटी सी पर 9 से अधिक 6 जगह है। इस लक्ष्य को प्राप्त करने के लिए हम खूंटी ए पर 5,4,3,2,1 के साथ इस चरण 2 पर एक परिष्करण पर 5 के शीर्ष पर 4 की जरूरत है । यह 13 चालों के साथ किया जाता है और लेआउट है
A - 5,4,3,2,1
B - 8, 7 13 चालें
सी - 9,6
चरण 3 - खूंटी सी पर 6 के शीर्ष पर 5,4..., 1 (5 छल्ले) ले जाएँ। यह खूंटी ए पर 7 जगह करने के लिए 31 चालें प्लस 1 से मेल खाती है । तो, चरण 3 31 + 1 = 32 में चालों की संख्या और लेआउट होगा
A - 7
B - 8 32 चालें
C - 9,6,5,4,3,2,1
चरण 4 - 6,5 चल रहा है,... खूंटी पर 7 के शीर्ष करने के लिए 1 (6 छल्ले) ६३ चाल प्लस एक और एक सी पर 9 के शीर्ष पर 8 डाल करने के लिए कदम 4 63 + 1 = 64 और लेआउट पर कुल चालें
A - 7,6,5,4,3,2,1
बी - 63+1 = 64 चालें
C - 9,8
चरण 5
हमारे पास हनोई आई स्थिति का एक टॉवर है । अंतिम कदम खूंटी से 7 छल्ले बढ़ रहा है एक
खूंटी सी पर 9,8 के शीर्ष पर। इसका मतलब है 127 चालें।
कुल चालें- 20+13+32+64+ 127= 256 न्यूनतम चालों की जरूरत है। - प्रारंभिक लेआउट (303 न्यूनतम चालों की आवश्यकता)
A - 4,9,7,5,8
B - 6,2
C - 3,1
यह उदाहरण पिछले दो की तुलना में थोड़ा कठिन है।
ध्यान दें कि 9 शीर्ष पर तीन अंगूठियों (7,5,8) के साथ एक पर अटक गया है। इसके अलावा, बी और सी मुक्त खूंटे नहीं हैं। यह एक मुक्त खूंटी पर 8,7 जगह की जरूरत स्पष्ट है अन्यथा हम 9 के लिए एक मुक्त खूंटी नहीं होगा.
ऐसा करने का सबसे अच्छा तरीका खूंटी सी पर 8,7 जगह है और सी पर 8,7 के शीर्ष पर 6 कदम है।
इस के बाद किया जाता है खूंटी बी 9 प्राप्त करने के लिए स्वतंत्र हो जाएगा । हालांकि, 7 को मुक्त करने से पहले हमें बी पर 6 के शीर्ष पर 5 जगह की जरूरत है ।
चरण 1 - स्थान 8, सी पर और 6,5,3,2,1 बी पर
पहले सात चालें हैं:
2 पर एक
1 पर एक
शीर्ष बी पर 3 (6 के शीर्ष पर)
1 पर सी
2 पर बी
1 पर बी
8 पर सी
23 चालें शुरू होने के बाद हमें लेआउट मिलता है
A - 4,9
B - 6,5,3,2,1 23 चालें
C - 8,7
चरण 2 - 8,7 के शीर्ष पर सी पर 6,5,3,2,1 (5 छल्ले) रखें (खूंटी बी 9 जगह करने के लिए स्वतंत्र हो जाएगा)।
एक और खूंटी के लिए 5 छल्ले चलती 31 चाल प्लस एक और एक बी पर 9 जगह तो की आवश्यकता है, इस कदम में हम 31 + 1 = 32 चाल की जरूरत है ।
लेआउट है
A - 4
B - 9 31+1 = 32 चालें
C - 8,7,6,5,3,2,1
चरण 3 - अब उद्देश्य 7 प्राप्त करने के लिए खूंटी ए को मुक्त करना है (अन्यथा हम 8 को 9 के शीर्ष पर नहीं रख सकते हैं)। इस लक्ष्य को प्राप्त करने के लिए 9 के शीर्ष पर 6,5,3,2,1 से बी को स्थानांतरित करने की आवश्यकता है।
लेकिन के रूप में चालें बी पर 6 जगह के लिए वैकल्पिक है हम पहले एक और बी पर 4 पर 5 जगह की जरूरत है.. ।
चरण 2 पर शुरू से 57 चालों के बाद हमारे पास निम्नलिखित लेआउट होगा।
A - 7
B - 9,6,5,4,3,2,1 57 चालें
C - 8
यह स्पष्ट है इन ५७ चालों को एक तर्क का पालन करना चाहिए । वास्तव में वे निम्नलिखित कार्यों पर विघटित किया जा सकता है
मुक़दमा चालों की संख्या 4 पर बी 1 3,2,1 (3 छल्ले) बी पर शीर्ष 4 पर 7 5 से एक 1 4,3,2,1 (4 छल्ले) एक करने के लिए 15 6 से बी 1 5,4,3,2,1 (5 छल्ले) 6 के शीर्ष पर बी करने के लिए 31 7 से एक 1 कुल 57
चरण 4 - 6,5..... 2,1 (6 छल्ले) को 7 के शीर्ष पर ले जाएं। इसके लिए 63 चालों की जरूरत है। अब बी पर 9 के शीर्ष पर 8 जगह संभव है जिसका अर्थ है एक अतिरिक्त कदम।
तो इस चरण 4 में कुल 63+1 = 64 चालें हैं
इस के बाद लेआउट किया जाता है
A - 7,6,5,4,3,2,1
बी - 9,8, 63+1= 64 (टॉवर ऑफ हनोई आई स्थिति)
सी -
चरण 5 - अंतिम चरण 7,6 स्थानांतरित करना है,... 2,1 खूंटी बी 9,8 के शीर्ष करने के लिए .
7 छल्ले ले जाने के लिए, 127 चालों की आवश्यकता होगी।
इसलिए, कुल चालें 23 +32+57+64+127 = 303 चालें न्यूनतम चालें हैं
- प्रारंभिक लेआउट (145 न्यूनतम चालें आवश्यक)
(मूल) Solving Tower of Hanoi II
-
- I assume the basic rules for moving the rings are well known.
- If the number of rings is odd you only need 1 step to place the top ring straight on top of the ring you want.
- If it’s even, there is a need for two steps to make the move. Let’s assume pegs A,B and C from left to right. If, for example, on B we have a pile with rings 1,2,3,4 and want to place them over ring 5 on C , the first step will be 1 to A and 2 to C, and next, 1 to C.. .and with a total of 15 moves we will have the 1,2,3,4 rings over 5 on peg C.
- In the initial layout there are larger rings on top of smaller rings (that’s the main difference from version I of this game) but when you start playing you can’t put a larger ring on top of a smaller one as in Tower of Hanoi I.
- I think the best approach to solve the game is starting with a quick look at the positions of rings 9, 8 and 7. It’ s important to see if ring 9 is already on the base of a peg. And if it isn’t, what the best way is (less moves) to put it there. In this case it often happens (especially if 7 and 8 are on different pegs) that one needs to place 7 over 8 to have a free peg for 9. Moreover we may have to place 6 on 9, 7 moving to the free peg after moving 6 and then 6 over 7 . The result will be a pile from 1 to 7 and the need of 127 additional moves to place these 7 rings on top of 8,9 (the minimal number of moves to solve a game in Tower of Hanoi I situation is : minimal moves = 2^n - 1 where n is the number of rings so, 3 rings will need 7 moves, 4 rings will need 15… 7 rings will need 127 and so on).
- Whatever the case, the purpose is, with the minimal number of moves possible, to change the initial layout to a Tower of Hanoi I situation. This means you will always know in advance if the game can be solved without having to actually finish it. When the rings are in a Tower of Hanoi I situation (a pile in ascending order starting with rings 1,2… on one peg, a free peg, and a peg with the remaining rings, also in ascending order, finishing on the base of the peg where 9 is), just add the moves already made to the necessary moves given by the above equation and the result should be equal to the minimal moves needed (whenever I do that control just add the last digit).
- Three examples (all from this website).
- Initial layout (145 minimal moves needed)
Peg A - 1,8,2,9
Peg B - 7,3
Peg C - 6,5,4
Step 1 - The best strategy is to place 9 on the base of peg C and 6 on top of 7 on peg B.
First move is: ring 3 on top of 9 on A, then 4 on top of 7 on B…
After 18 moves from the initial layout we get:
Peg A - 1
Peg B - 7,6,5,4,3,2 18 moves
Peg C – 9,8
Step 2 – If we look at this layout carefully, we’ll note this is equivalent to 6 rings on top of 7 on B, provided the next move is to place ring 1 on top of 8 on C. We are speaking of 6 rings (6,5 …1 that is, even, on peg B and 2 steps are required). So to place these six rings on A we need a first move to place 1 on the other peg, in this case C.
As we already know, to move 6 rings to another peg (peg A) we need 63 moves. After these moves there is an addtional one to place 7, now free, on top of 9,8.
So, in this Step 2 the moves will be 63 + 1= 64 and the layout we get is:
A - 6,5,4,3,2,1
B - 63+1 = 64 moves
C - 9,8,7
So far, we have 18 moves on Step 1 plus 64 on Step 2
Step 3 – The above layout corresponds to what I call a Tower of Hanoi I situation.
To finish the game we need to move the 6 rings (6,5,…1) on peg A to the top of 9,8,7 on peg C. This will require another 63 moves.
Total moves= 18 + 64 + 63 = 145 which is the minimal moves needed. - Initial layout (256 minimal moves needed)
A - 5,3,9
B - 8,1,6,4
C - 2,7
To place 9 on the base, as 8 and 7 are on different pegs, we need to place 7 on top of 8 on B.
Step 1 - Our goal is to place 9 on C and 7 on top of 8 on B. To achieve this we first need to move 6,4 to the top of 9 on A to free C to receive the 9.
The first five moves are 4 on top of 7,6 on top of 9 on A ,4 to 6,1 to 4 and 7 to 8 on peg B.
After 20 moves the layout will be
A – 5,3
B – 8,7,6,4,2,1 20 moves
C – 9
Step 2 place 6 over 9 on peg C. To achieve this we need 4 on top of 5 on A finishing this Step 2 with 5,4,3,2,1 on peg A . This is done with 13 moves and the layout is
A – 5,4,3,2,1
B – 8, 7 13 moves
C - 9,6
Step 3 – Move 5,4…,1 (5 rings) to the top of 6 on peg C. This corresponds to 31 moves plus 1 to place 7 on peg A. So, the number of moves in Step 3 31+1=32 and the layout will be
A – 7
B – 8 32 moves
C – 9,6,5,4,3,2,1
Step 4 - Moving 6,5,…1 to the top of 7 on peg A will require (6 rings) 63 moves plus another one one to put 8 on top of 9 on C. Total moves on Step 4 63+1=64 and the layout
A – 7,6,5,4,3,2,1
B - 63+1 = 64 moves
C - 9,8
Step 5
We have a Tower of Hanoi I situation. The final step is moving the 7 rings from peg A
to the top of 9,8 on peg C. This means 127 moves.
Total moves- 20 + 13 + 32 + 64 + 127 = 256 minimal moves needed. - Initial layout (303 minimal moves needed)
A – 4,9,7,5,8
B – 6,2
C – 3,1
This example is a bit harder than the previous two.
Note that 9 is stuck on A with three rings on top (7,5,8). Also, B and C are not free pegs. It’s clear the need to place the 8,7 on a free peg otherwise we will not have a free peg for 9.
The best way to do this is to place 8,7 on peg C and move 6 to the top of 8,7 on C.
After this is done Peg B will be free to receive 9. Note however, before freeing 7 we need to place 5 on top of 6 on B.
Step 1 - Place 8, on C and 6,5,3,2,1 on B
The first seven moves are:
2 on A
1 on A
3 on top B (on top of 6)
1 on C
2 on B
1 on B
8 on C
23 moves after the start we get the layout
A – 4,9
B – 6,5,3,2,1 23 moves
C – 8,7
Step 2 – Place the 6,5,3,2,1 (5 rings) on C on top of 8,7 (peg B will be free to place the 9).
Moving 5 rings to another peg requires 31 moves plus another one to place 9 on B so, in this step we need 31+1 =32 moves .
The layout is
A – 4
B – 9 31+1= 32 moves
C – 8,7,6,5,3,2,1
Step 3 – The purpose now is to free peg A to receive 7 (otherwise we can’t place 8 on top of 9). To acheive this it’s needed to move 6,5,3,2,1 to B on top of 9.
But as the moves are alternate to place 6 on B we previously need to place the 5 on A and 4 on B…
After 57 moves from the start on Step 2 we will have the following layout.
A – 7
B – 9,6,5,4,3,2,1 57 moves
C – 8
It’s obvious these 57 moves must follow a logic. In fact they can be decomposed on the following actions
Action Number of moves 4 on B 1 3,2,1 (3 rings) on top 4 on B 7 5 to A 1 4,3,2,1 (4 rings) to A 15 6 to B 1 5,4,3,2,1 (5 rings) to B on top of 6 31 7 to A 1 Total 57
Step 4 - move 6,5…..2,1 (6 rings) to A on top of 7. This needs 63 moves. Now it’s possible to place 8 on top of 9 on B which means an additional move.
So in this Step 4 there is a total of 63+1 = 64 moves
After this is done the layout is
A – 7,6,5,4,3,2,1
B – 9,8, 63+1=64 (Tower of Hanoi I situation)
C –
Step 5 – The final step is to move 7,6,…2,1 to peg B to the top of 9,8 .
To move 7 rings, 127 moves will be needed.
So, the total moves are 23+32+57+64+127= 303 moves minimal moves needed
- Initial layout (145 minimal moves needed)
द्वारा Slb
2020-02-13 16:10:02
लाइक करें
उत्तर दें