एक लिंक्ड सूची में साइकिल का पता लगाने: संपूर्ण सिद्धांत

Question

famous हरे और कछुआ विधि का उपयोग करके एक लिंक्ड सूची में चक्र का पता लगाने में समस्या नहीं है।

हरे & टोर्टोइज़ विधि में हमारे पास 1x और 2x गति में चलने वाले पॉइंटर्स हैं जो यह निर्धारित करने के लिए हैं कि वे मिलते हैं और मुझे विश्वास है कि इसका सबसे प्रभावी तरीका और उस प्रकार की खोज का क्रम ओ (एन) है।

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

यह हाल ही में भाग लेने वाले साक्षात्कारों में से एक में पूछा गया था और मैं इसे अपने आप को साबित करने में सक्षम नहीं था कि उपरोक्त संभव है या नहीं। किसी भी मदद की सराहना की।

Answer 1

मान लीजिए कि एक लूप है, लंबाई L का कहना है।

आसान मामला पहले

इसे आसान बनाने के लिए, पहले मामले पर विचार जहां दो कणों एक ही समय में पूरे पाश। n*A = n*B (mod L) कुछ सकारात्मक पूर्णांक n के लिए ये कण एक ही स्थिति में हैं, जो कि फिर से मिलने तक चरणों की संख्या है। n=L लेना एक समाधान देता है (हालांकि एक छोटा समाधान हो सकता है)। तो L समय की इकाइयों के बाद, कण A ने शुरुआत में वापस आने के लिए A लूप के चारों ओर भ्रमण किया है और कण B ने B लूप के चारों ओर भ्रमण शुरू किया है, जहां वे खुशी से टकराते हैं।

जनरल प्रकरण

अब क्या होता है जब वे एक ही समय में पाश में प्रवेश नहीं करते? A धीमी कण हो, यानी A<B, और मान लें कि A समय m पर लूप में प्रवेश करता है, और चलिए A लूप 0 में प्रवेश करते हैं (क्योंकि वे लूप में हैं, वे इसे कभी नहीं छोड़ सकते हैं, इसलिए मैं ' एम A*m घटाकर पदों का नाम बदलकर, A की दूरी m समय इकाइयों के बाद यात्रा की गई है)।फिर, उस समय, B पहले से ही m*(B-A) पर स्थित है (m के बाद यह वास्तविक स्थिति B*m है और इसकी नाम बदलकर B*m-A*m है)। फिर हमें यह दिखाने की ज़रूरत है कि n ऐसा समय है जैसे n*A = n*B+m*(B-A) (mod L)। जो है, हम मॉड्यूलर समीकरण

(n+m) * (A-B) = 0 (mod L) 

k पर्याप्त है कि k*L>m काम कर देता है बड़े के लिए n = k*L-m ले रहा है के लिए एक समाधान की जरूरत है, हालांकि फिर से, तो किसी छोटे समाधान हो सकता है।

इसलिए, हाँ, वे हमेशा मिलते हैं।

Answer 2

यदि आपके दो चरण आकारों में एक सामान्य कारक है x: मान लें कि चरण आकार एक्स और बीएक्स हैं, तो बस मूल अनुक्रम लेने और प्रत्येक x'th तत्व लेने से प्राप्त अनुक्रम पर विचार करें। इस नए अनुक्रम में एक चक्र है यदि केवल मूल अनुक्रम होता है, और आकार ए और बी के चरणों को लेना मूल अनुक्रम पर आकार एक्स और बीएक्स के चरणों को लेने के बराबर है।

इस कमी का मतलब है कि यह साबित करने के लिए पर्याप्त है कि ए और बी coprime जब एल्गोरिदम काम करता है।

Answer 3

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

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