algorithm - यह कैसे काम करता है? हनोई समाधान के अजीब टावर्स




language-agnostic bit-manipulation (2)

जब मैंने हनोई के टावरों के लिए this असामान्य, पुनरावृत्ति समाधान की खोज की तो मैं इंटरनेट पर खो गया

for (int x = 1; x < (1 << nDisks); x++)
{
     FromPole = (x & x-1) % 3;
     ToPole = ((x | x-1) + 1) % 3;
     moveDisk(FromPole, ToPole);
}

इस पोस्ट में भी उत्तरों में से एक में डेल्फी कोड समान है।

हालाँकि, मेरे जीवन के लिए, मैं यह क्यों काम करता है के लिए एक अच्छा स्पष्टीकरण नहीं मिल सकता है।

क्या कोई मुझे इसे समझने में मदद कर सकता है?


antti.huima का समाधान अनिवार्य रूप से सही है, लेकिन मैं कुछ अधिक कठोर चाहता था, और यह एक टिप्पणी में फिट होने के लिए बहुत बड़ा था। यहाँ जाता हैं:

पहला नोट: इस एल्गोरिथ्म के मध्य चरण x = 2 N-1 पर, "से" खूंटी 0 है, और "से" खूंटी 2 N % 3 है। यह 2 (N-1) % 3 के लिए छोड़ देता है " स्पेयर "खूंटी। यह एल्गोरिथम के अंतिम चरण के लिए भी सही है, इसलिए हम देखते हैं कि वास्तव में लेखकों का एल्गोरिथ्म एक मामूली "धोखा" है: वे डिस्क को खूंटी 0 से खूंटी 2 एन % 3 तक ले जा रहे हैं, बजाय एक निश्चित, पूर्व -सीपे किए गए "से" खूंटी यह बहुत काम नहीं के साथ बदला जा सकता है।

मूल हनोई एल्गोरिथ्म है:

hanoi(from, to, spare, N):
    hanoi(from, spare, to, N-1)
    move(from, to)
    hanoi(spare, to, from, N-1)

"" = 0, "से" = 2 N % 3, "स्पेयर" = 2 N-1 % 3 में प्लग करना, हमें मिलता है (% 3 का दमन):

hanoi(0, 2**N, 2**(N-1), N):
(a)   hanoi(0, 2**(N-1), 2**N, N-1)
(b)   move(0, 2**N)
(c)   hanoi(2**(N-1), 2**N, 0, N-1)

यहाँ मौलिक अवलोकन यह है: लाइन (c) में, खूंटी हनोई के खूंटे (0, 2 N-1 , 2 N , N-1) 2 N-1 % 3 द्वारा स्थानांतरित किए गए हैं, अर्थात वे बिलकुल खूंटे हैं (क) इस राशि के साथ उन्हें जोड़ा गया

मैं यह दावा करता हूं कि जब हम लाइन (सी), "से" और "से" खूंटे को लाइन के संगत खूंटे (ए) 2 एन -1 % द्वारा स्थानांतरित कर देते हैं, तो यह आसान, अधिक सामान्य लेम्मा से इस प्रकार है। कि hanoi(a+x, b+x, c+x, N) , "से और" से "खूंटे hanoi(a, b, c, N) में बिल्कुल x स्थानांतरित किए जाते हैं।

अब कार्यों पर विचार करें
f(x) = (x & (x-1)) % 3
g(x) = (x | (x-1)) + 1 % 3

यह साबित करने के लिए कि दिए गए एल्गोरिदम काम करते हैं, हमें केवल यह दिखाना है:

  • f (2 एन -1 ) == 0 और जी (2 एन -1 ) == 2 एन
  • 0 <i <2 N के लिए , हमारे पास f (2 N - i) == f (2 N + i) + 2 N % 3, और g (2 N - i) == g (2 N + i) + है 2 एन % 3।

इन दोनों को दिखाना आसान है।


यह सीधे सवाल का जवाब नहीं दे रहा है, लेकिन यह एक टिप्पणी में डालने के लिए बहुत लंबा था।

मैंने हमेशा डिस्क के आकार का विश्लेषण करके ऐसा किया था जिसे आपको आगे बढ़ना चाहिए। यदि आप चले गए डिस्क को देखते हैं, तो यह सामने आता है:

1 disk  : 1
2 disks : 1 2 1
3 disks : 1 2 1 3 1 2 1
4 disks : 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

अजीब आकार हमेशा लोगों की विपरीत दिशा में चलते हैं, अगर खूंटे (0, 1, 2, दोहराना) या (2, 1, 0, दोहराना)।

यदि आप पैटर्न पर एक नज़र डालते हैं, तो स्थानांतरित करने की अंगूठी चालों की संख्या के xor और चालों की संख्या का उच्चतम बिट सेट है + 1।





towers-of-hanoi