#1
5
(تمت الترجمة بواسطة Microsoft)
-
- أفترض أن القواعد الأساسية لتحريك الحلقات معروفة جيدا.
- إذا كان عدد الحلقات غريبا ، فستحتاج فقط إلى خطوة واحدة لوضع الحلقة العلوية مباشرة على قمة الحلبة التي تريدها.
- إذا كان حتى، هناك حاجة لخطوتين لجعل هذه الخطوة. لنفترض أن الوتد A وB وC من اليسار إلى اليمين. إذا، على سبيل المثال، على B لدينا كومة مع حلقات 1،2،3،4 وتريد وضعها على حلقة 5 على C، فإن الخطوة الأولى ستكون 1 إلى A و 2 إلى C، وبعد ذلك، 1 إلى C.. ومع ما مجموعه 15 التحركات سيكون لدينا 1،2،3،4 حلقات أكثر من 5 على ربط C.
- في التخطيط الأولي هناك حلقات أكبر على رأس حلقات أصغر (وهذا هو الفرق الرئيسي من الإصدار الأول من هذه اللعبة) ولكن عندما تبدأ اللعب لا يمكنك وضع حلقة أكبر على رأس أصغر واحد كما هو الحال في برج هانوي الأول.
- أعتقد أن أفضل نهج لحل اللعبة هو البدء مع نظرة سريعة على مواقف الحلقات 9 و 8 و 7. من المهم معرفة ما إذا كان الخاتم 9 بالفعل على قاعدة الربط. وإذا لم يكن كذلك ، ما هي أفضل طريقة (أقل التحركات) لوضعها هناك. في هذه الحالة غالبا ما يحدث (خاصة إذا 7 و 8 على أوتاد مختلفة) أن المرء يحتاج إلى وضع 7 أكثر من 8 أن يكون ربط الحرة لمدة 9. وعلاوة على ذلك قد يكون لدينا لوضع 6 على 9، 7 الانتقال إلى ربط الحرة بعد نقل 6 ثم 6 أكثر من 7 . والنتيجة ستكون كومة من 1 إلى 7 والحاجة إلى 127 تحركات إضافية لوضع هذه الحلقات 7 على رأس 8،9 (الحد الأدنى من عدد التحركات لحل لعبة في برج هانوي الأول الوضع هو : الحد الأدنى من التحركات = 2 ^ ن - 1 حيث ن هو عدد الحلقات لذلك، 3 حلقات سوف تحتاج إلى 7 تحركات، 4 حلقات سوف تحتاج إلى 15 ... 7 حلقات سوف تحتاج إلى 127 وهلم جرا).
- مهما كان الأمر، فإن الغرض هو، مع الحد الأدنى من عدد التحركات الممكنة، لتغيير التخطيط الأولي إلى برج هانوي الأول الوضع. وهذا يعني أنك سوف تعرف دائما مقدما إذا كان يمكن حل اللعبة دون الحاجة إلى الانتهاء من ذلك فعلا. عندما تكون الحلقات في برج هانوي أنا الوضع (كومة في ترتيب تصاعدي بدءا من حلقات 1،2... على ربط واحد ، وربط الحرة ، وربط مع الحلقات المتبقية ، وأيضا في ترتيب تصاعدي ، والانتهاء من قاعدة الربط حيث 9 هو) ، مجرد إضافة التحركات التي اتخذت بالفعل إلى التحركات اللازمة التي قدمتها المعادلة أعلاه ، والنتيجة ينبغي أن تكون مساوية للحد الأدنى من التحركات اللازمة (كلما أفعل ذلك التحكم فقط إضافة الرقم الأخير).
- ثلاثة أمثلة (كلها من هذا الموقع).
- التخطيط الأولي (145 نقلة بسيطة مطلوبة)
ربط A - 1,8,2,9
الوتد B - 7,3
الوتد C - 6,5,4
الخطوة 1 - أفضل استراتيجية هي وضع 9 على قاعدة ربط C و 6 على رأس 7 على ربط B.
الخطوة الأولى هي: حلقة 3 على رأس 9 على A، ثم 4 على رأس 7 على B ...
بعد 18 نقلة من التخطيط الأولي نحصل على:
ربط A - 1
الوتد B - 7,6,5,4,3,2 18 حركة
الوتد C – 9,8
الخطوة 2 - إذا نظرنا إلى هذا التخطيط بعناية ، فسنلاحظ أن هذا يعادل 6 حلقات فوق 7 على B ، شريطة أن تكون الخطوة التالية هي وضع الحلقة 1 فوق 8 على C. نحن نتحدث عن 6 حلقات (6،5 ... 1 وهذا هو، حتى، على ربط B و 2 الخطوات المطلوبة). حتى لوضع هذه الحلقات الست على A نحن بحاجة إلى الخطوة الأولى لوضع 1 على ربط أخرى، في هذه الحالة C.
كما نعلم بالفعل، لنقل 6 حلقات إلى ربط آخر (ربط A) نحن بحاجة إلى 63 التحركات. بعد هذه التحركات هناك واحد إضافي لوضع 7، مجانا الآن، على رأس 9،8.
لذلك، في هذه الخطوة 2 التحركات ستكون 63 + 1 = 64 والتخطيط نحصل على:
أ - 6,5,4,3,2,1
ب - 63+1 = 64 حركة
جيم - 9,8,7
حتى الآن، لدينا 18 حركة في الخطوة 1 زائد 64 في الخطوة 2
الخطوة 3 - التخطيط أعلاه يتوافق مع ما أسميه برج هانوي الأول الوضع.
لإنهاء اللعبة نحن بحاجة إلى نقل 6 حلقات (6،5,... 1) على ربط ألف إلى أعلى من 9،8،7 على ربط C. وهذا يتطلب 63 حركة أخرى.
مجموع التحركات = 18 + 64 + 63 = 145 وهو الحد الأدنى من التحركات اللازمة. - التخطيط الأولي (256 نقلة بسيطة مطلوبة)
أ - 5,3,9
باء - 8,1,6,4
جيم - 2,7
لوضع 9 على القاعدة، كما 8 و 7 على أوتاد مختلفة، ونحن بحاجة إلى وضع 7 على رأس 8 على B.
الخطوة 1 - هدفنا هو وضع 9 على C و 7 على رأس 8 على B. لتحقيق ذلك نحن بحاجة أولا إلى نقل 6،4 إلى أعلى من 9 على ألف إلى C مجانا لتلقي 9.
التحركات الخمس الأولى هي 4 على رأس 7،6 على رأس 9 على A ، 4 إلى 6،1 إلى 4 و 7 إلى 8 على ربط B.
بعد 20 نقل سيكون التخطيط
أ – 5,3
ب – 8,7,6,4,2,1 20 حركة
جيم – 9
الخطوة 2 مكان 6 على 9 على ربط C. لتحقيق ذلك نحن بحاجة إلى 4 على رأس 5 على الانتهاء من هذه الخطوة 2 مع 5،4،3،2،1 على ربط A . ويتم ذلك مع 13 التحركات والتخطيط
أ – 5,4,3,2,1
ب – 8, 7 13 التحركات
جيم - 9,6
الخطوة 3 - نقل 5،4...،1 (5 حلقات) إلى أعلى 6 على ربط C. وهذا يتوافق مع 31 نقلة زائد 1 لوضع 7 على ربط A. لذلك، فإن عدد التحركات في الخطوة 3 31 +1 = 32 والتخطيط سيكون
أ – 7
ب – 8 32 نقلة
جيم - 9,6,5,4,3,2,1
الخطوة 4 - نقل 6,5,... 1 إلى أعلى 7 على ربط A سوف تتطلب (6 حلقات) 63 التحركات بالإضافة إلى واحد آخر لوضع 8 على رأس 9 على جيم مجموع التحركات على الخطوة 4 63 +1 = 64 والتخطيط
أ – 7,6,5,4,3,2,1
ب - 63+1 = 64 حركة
جيم - 9,8
الخطوة الخامسة
لدينا برج هانوي 1 الوضع. الخطوة الأخيرة هي تحريك الحلقات السبع من ربط A
إلى أعلى 9,8 على ربط C. وهذا يعني 127 حركة.
مجموع التحركات - 20 + 13 + 32 + 64 + 127 = 256 الحد الأدنى من التحركات اللازمة. - التخطيط الأولي (303 نقلة بسيطة مطلوبة)
أ – 4,9,7,5,8
ب – 6,2
جيم – 3,1
هذا المثال هو أصعب قليلا من السابقتين.
لاحظ أن 9 عالقة على A مع ثلاث حلقات على رأس (7,5,8). أيضا ، B و C ليست أوتاد مجانية. من الواضح أن الحاجة إلى وضع 8،7 على ربط الحرة وإلا فإننا لن يكون ربط الحرة لمدة 9.
أفضل طريقة للقيام بذلك هو وضع 8،7 على ربط C ونقل 6 إلى أعلى من 8،7 على C.
بعد أن يتم ذلك الوتد B سيكون حرا في الحصول على 9. علما مع ذلك، قبل تحرير 7 نحن بحاجة إلى وضع 5 على رأس 6 على B.
الخطوة 1 - المكان 8، على C و 6,5,3,2,1 على B
التحركات السبع الأولى هي:
2 على A
1 على A
3 على أعلى B (على رأس 6)
1 على C
2 على B
1 على B
8 على C
23 يتحرك بعد البداية نحصل على تخطيط
أ – 4,9
ب – 6,5,3,2,1 23 حركة
جيم - 8,7
الخطوة 2 - ضع 6,5,3,2,1 (5 حلقات) على C على رأس 8,7 (سيكون الربط B حرا في وضع 9).
نقل 5 حلقات إلى ربط آخر يتطلب 31 التحركات بالإضافة إلى واحد آخر لوضع 9 على B لذلك، في هذه الخطوة نحن بحاجة 31 +1 = 32 التحركات .
التخطيط هو
أ – 4
ب – 9 31+1= 32 حركة
جيم - 8,7,6,5,3,2,1
الخطوة 3 - والغرض الآن هو ربط الحرة A لتلقي 7 (وإلا فإننا لا يمكن وضع 8 على رأس 9). لتحقيق ذلك هناك حاجة لنقل 6,5,3,2,1 إلى B على رأس 9.
ولكن كما التحركات هي بديلة لوضع 6 على B نحن بحاجة سابقا لوضع 5 على A و 4 على B...
بعد 57 نقل من البداية في الخطوة 2 سيكون لدينا التخطيط التالي.
أ – 7
ب – 9,6,5,4,3,2,1 57 حركة
جيم – 8
من الواضح أن هذه التحركات ال 57 يجب أن تتبع منطقا. في الواقع يمكن أن تتحلل على الإجراءات التالية
فعل عدد الحركات 4 على B 1 3,2,1 (3 حلقات) على أعلى 4 على B 7 5 إلى A 1 4,3,2,1 (4 حلقات) إلى A 15 6 إلى B 1 5,4,3,2,1 (5 حلقات) إلى B فوق 6 31 7 إلى A 1 مجموع 57
الخطوة 4 - نقل 6,5.....2,1 (6 حلقات) إلى A على رأس 7. هذا يحتاج إلى 63 حركة. الآن من الممكن وضع 8 على رأس 9 على B مما يعني خطوة إضافية.
حتى في هذه الخطوة 4 هناك ما مجموعه 63 +1 = 64 التحركات
بعد أن يتم ذلك التخطيط
أ – 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
أعجبني
الرد